Pascal语言编译器的方案设计书与实现 .docx

《Pascal语言编译器的方案设计书与实现 .docx》由会员分享，可在线阅读，更多相关《Pascal语言编译器的方案设计书与实现 .docx（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结封面可编辑资料 - - - 欢迎下载精品名师归纳总结作者： PanHongliang仅供个人学习Pascal 语言编译器的设计与实现我们设计的编译程序涉及到编译五个阶段中的三个，即词法分析器、语法分析器和中间代码生成器。编译程序的输出结果包括词法分析后的二元式序列、变量名表、状态栈分析过程显示及四元式序列程序，整个编译程序分为三部分：(1) 词法分析部分可编辑资料 - - - 欢迎下载精品名师归纳总结(2) 语法分析处理及四元式生成部分(3) 输出显示部分一词法分析器设计由于我们规定的程序语句中涉及单词较少，故在词法分析阶段忽视了单词输入错误的检查，而将编译程序的重点放在中间代

2、码生成阶段。词法分析器的功能是输入源程序，输出单词符号。我们规定输出的单词符号格式为如下的二元式：单词种别，单词自身的值 #defineACC-2#define sy_if0#define sy_then1#define sy_else2#define sy_while3#define sy_begin4#define sy_do5#define sy_end6#define a7#define semicolon8#define e9#define sharp10#define S11#define L12#define tempsy15#define EA18 /E and#define

3、EO19 /E or#define plus34#define subtract35#define times36#define divide37#define becomes38#define op_and39#define op_or40#define op_not41#define rop42#define lparent48#define rparent49#define ident56#define intconst57函数说明1. 读取函数 readline 、readchar 词法分析包含从源文件读取字符的操作，但频繁的读文件操作会影响程序执行效率，故实际上是从源程序文件 ”PA

4、S.dat ”中读取一行到输入缓冲区，而词法分析过程中每次读取一个字符时就是通过执行 readchar 从输入缓冲区获得的。如缓冲区已被读空，就再执行 readline 从 PAS.dat 中读取下一行至输入缓冲区。2. 扫描函数 scan 可编辑资料 - - - 欢迎下载精品名师归纳总结扫描函数scan 的功能是滤除余外空格并对主要单词进行分析处理，将分析得到的二元式存入二元式结果缓冲区。3. 变量处理 find （ ）变量处理中第一把以字母开头的字母数字串存到spelling 数组中，然后进行识别。识别过程是先让它与保留关键字表中的全部关键字进行匹配，如获得胜利就说明它为保留关键字，即将其

5、内码值写入二元式结果缓冲区。否就说明其为变量，这时让它与变量名表中的变量进行匹配（ 变量匹配函数 find （ ） ），假如胜利，就说明该变量已存在并在二元式结果缓冲区中标记为此变量（ 值填为该变量在变量名表中的位置）， 否就将该变量登记到变量名表中，再将这个新变量存入二元式缓存数组中。4. 数字识别 number 数字识别将识别出的数字填入二元式结果缓存数组。5. 显示函数显示函数的功能在屏幕上输出词法分析的结果（即二元式序列程序），同时给出二元式个数及源程序行数统计。二语法分析器设计语法分析器的核心是三张SLR 分析表以及针对这三张SLR 分析表进行语义加工的语义动作。编译程序中语法分析处

6、理及四元式生成部分主要是以二元式作为输入，并通过 SLR 分析表对语法分析处理过程进行掌握，使四元式翻译的工作有条不紊的进行，同时识别语法分析中的语法错误。在处理if 和 while 语句时，需要进行真值或假值的拉链和返填工作，以便转移目标的正确填入。1. 掌握语句 的 SLR 分析表 1 设计过程如下： 将扩展文法 G0） S S1） Sif e then S else S 2） Swhile e do S 3） Sbegin L end 4） Sa5） LS6） LS。L用 _CLOSURE 方法构造 LR0 工程规范簇为：I0： S SS if e then S else SSwhile

7、edoS S begin L endS a 。I1 : S SI2 : Sif e then S else S I3 : Swhile e do SI4 : Sbegin L end L SL S。LS if e then S else SSwhileedoS可编辑资料 - - - 欢迎下载精品名师归纳总结S begin L end S aI5 : SaI6 : Sif e then S else S I7 : Swhile e do SI8 : Sbegin L end I9 : LSLS。 LI10: Sif e then S else SS if e then S else S S wh

8、ile e do SS begin L end I11: Swhile e do SS if e then S else S S while e do SS begin L end S aI 12: Sbegin L end I13: LS。 LL SL S。 LS if e then S else S S while e do SS begin L end S aI14: Sif e then S else S I15: Swhile e do S I16: LS。LI17: Sif e then S else SS if e then S else S S while e do SS be

9、gin L end S aI18: Sif e then S else S构造文法 G中非终结符的 FOLLOW 集如下：FOLLOWL = end FOLLOWS = else ,。 ,end,#在（）工程规范簇中，只有 9 有“移进归约”冲突，LSL S L由于 FOLLOWL FIRSTL= 所以可以用方法解决以上冲突，最终我们得到IfS2thenelsewhileS3beginS4ACTIONdoGOTOendaS5。e#S1L01ACC的分析表如下：可编辑资料 - - - 欢迎下载精品名师归纳总结2S63S74S2S3S4S5985R4R3R4R46S107S118S129R5S13

10、10S2S3S4S51411S2S3S4S51512R3R3R3R313S2S3S4S591614S1715R2R2R2R216R617S2S3S4S51818R1R1R1R1static int/*0*/*1*/action1913=2,-1,-1,3,4,-1,-1,5,-1,-1,10,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,ACC,-1,-1,/*2*/-1,-1,-1,-1,-1,-1,-1,-1,-1,6,-1,-1,-1,/*3*/-1,-1,-1,-1,-1,-1,-1,-1,-1,7,-1,-1,-1,/*4*/2,-1,-1,3,4,-1,-1

11、,5,-1,-1,-1,9,8,/*5*/-1,-1,104,-1,-1,-1,104,-1,104,-1,104,-1,-1,/*6*/-1,10,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/*7*/-1,-1,-1,-1,-1,11,-1,-1,-1,-1,-1,-1,-1,/*8*/-1,-1,-1,-1,-1,-1,12,-1,-1,-1,-1,-1,-1,/*9*/-1,-1,-1,-1,-1,-1,105,-1,13,-1,-1,-1,-1,/*10*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,14,-1,/*11*/2,-1,-1,3,4,

12、-1,-1,5,-1,-1,-1,15,-1,/*12*/-1,-1,103,-1,-1,-1,103,-1,103,-1,103,-1,-1,/*13*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,9,16,/*14*/-1,-1,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/*15*/-1,-1,102,-1,-1,-1,102,-1,102,-1,102,-1,-1,/*16*/-1,-1,-1,-1,-1,-1,106,-1,-1,-1,-1,-1,-1,/*17*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,18,-1,/*18*/-

13、1,-1,101,-1,-1,-1,101,-1,101,-1,101,-1,-1。其中，前9 列为 action 值，后 2 列为 goto 值。 016 表示17 个移进状态（ 即 Si）。 -1 表示出错。2. 算术表达式ACC 表示分析胜利。而100 106 对应归约产生式： 的 LR 分析表 2 设计如下：0SE1EE+E2EE*E3EE4Ei（过程略）ACTIONGOTOI+-*/#E0S3S21可编辑资料 - - - 欢迎下载精品名师归纳总结1S4S11S5S10ACC2S3S263R4R4R4R4R4R44S3S275S3S286S4S11S5S10S97R1R1S5S10R1

14、R18R2R2R2R2R2R29R3R3R3R3R3R310S3S21211S3S21312R6R6R6R6R6R613R5R5S5S10R5R5static int action1149=/*0*/3,-1,-1,-1,-1,2,-1,-1,1,/*1*/-1,4,11,5,10,-1,-1,ACC,-1,/*2*/3,-1,-1,-1,-1,2,-1,-1,6,/*3*/104,104,104,104,104,104,104,104,-1,/*4*/3,-1,-1,-1,-1,2,-1,-1,7,/*5*/*6*/3,-1,-1,-1,-1,2,-1,-1,8,-1,4,11,5,10,-

15、1,9,-1,-1,/*7*/101,101,101,5,10,101,101,101,-1,/*8*/102,102,102,102,102,102,102,102,-1,/*9*/103,103,103,103,103,103,103,103,-1,/*10*/3,-1,-1,-1,-1,2,-1,-1,12,/*11*/3,-1,-1,-1,-1,2,-1,-1,13,/*12*/106,106,106,106,106,106,106,106,-1,/*13*/3.布尔表达式的105,105,105,5,10,105,105,105,-1。SLR 分析表 3 设计如下：（过程略）1SB2

16、Bi3Bi rop i4B B 5BNOT B6AB AND7BAB8OB OR9BOBACTIONGOTOiRopNOTANDOR#BAO0S1S4S513781S2R1R1R1R12S33R2R2R2R24S1S4S511785S1S4S56786R4S9S10R47S1S4S514788S1S4S51578可编辑资料 - - - 欢迎下载精品名师归纳总结9R5R5R510R7R7R711S12S9S1012R3R3R3R313S9S10ACC14R6S9S10R615R8S9S10R8static int action21611=/*0*/1,-1,4,-1,5,-1,-1,-1,13,

17、7,8,/*1*/-1,2,-1,101,-1,101,101,101,-1,-1,-1,/*2*/3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/*3*/-1,-1,-1,102,-1,102,102,102,-1,-1,-1,/*4*/1,-1,4,-1,5,-1,-1,-1,11,7,8,/*5*/1,-1,4,-1,5,-1,-1,-1,6,7,8,/*6*/-1,-1,-1,104,-1,9,10,104,-1,-1,-1,/*7*/1,-1,4,-1,5,-1,-1,-1,14,7,8,/*8*/1,-1,4,-1,5,-1,-1,-1,15,7,8,/*9*/1

18、05,-1,105,-1,105,-1,-1,105,-1,-1,-1,/*10*/107,-1,107,-1,107,-1,-1,107,-1,-1,-1,/*11*/-1,-1,-1,12,-1,9,10,-1,-1,-1,-1,/*12*/-1,103,-1,103,-1,103,103,103,-1,-1,-1,/*13*/-1,-1,-1,-1,-1,9,10,ACC,-1,-1,-1,/*14*/-1,-1,-1,106,-1,9,10,106,-1,-1,-1,/*15*/-1,-1,-1,108,-1,9,10,108,-1,-1,-1。LR 分析表掌握语义加工的实现：当扫描

19、LR 分析表的当前状态为归约状态时，就在调用与该状态对应的产生式进行归约的同时，调用相应的语义子程序进行有关的翻译工作。现在对LR 分析器的分析栈加以扩充，使得每个文法符号之后都跟着它的语义值。为了清楚起见，我们把这个栈的每一项看成由三部分组成：状态state ，文法符号 syl 和语义值 val。编译程序实现算术表达式、布尔表达式及程序语句的语义加工时，都是按这种状态栈加工方式进行的。例如： 5 + 3 * 6的分析过程序号STATEValsylinput10-# 5 + 3 * 6 #202-#5 + 3 * 6 #3023-#5+ 3 * 6 #4026-5#E+ 3 * 6 #5026

20、4-5-#E+3 * 6 #602643-5-#E+3 * 6 #702647-5-3#E+E * 6 #8026-8#E * 6 #90269-8-#E* 6 #1001-8#E* 6 #11015-8-#E* 6 #120153-8-#E*6#130158-8-6#E*E#1401-48#E#15ACC在分析过程中，第（ 3）步操作后的状态栈为023，依据栈顶状态“3”和现行输可编辑资料 - - - 欢迎下载精品名师归纳总结入符号“+”（ input 栏字符串的第一个字符）查分析表ACTION3 ， +=R4 ，即按第（ 4）个产生式E n 来进行归约。由于产生式右部仅含一项，故去掉状态栈

21、栈顶“ 3”。此时 2 变为新的栈顶状态，再查（2 ， E）的下一状态 s： GOTO2,E=6 ，即将状态 6 和文法符号 E 压栈，最终得到第（4）步的状态。第（7）步操作后也是如此，当前状态栈为02647 ，依据栈顶状态7 和现行输入符号“）”查分析表ACTION7 ，） =R1 ，即按第（ 1）个产生式 EE1+E2 进行归约。由于产生式右部有三项，故去掉状态栈栈顶的647 三项。此时 2 变为新的栈顶状态，再查（2， E）的下一状态 s： GOTO2 ， E=6, 即将状态 6 和文法符号 E 压栈，最终得到第（ 8）步的状态。三中间代码生成器设计：布尔表达式布尔表达式在程序语言中有

22、两个基本作用：一是用作掌握语句（如 if -else 或while 语句）的条件式。二是用于规律演算，运算规律值。布尔表达式是由布尔算符（ & 、| 、！）作用于布尔变量（或常数）或关系表达式而形成的。关系表达式的形式是 E1 rop E2 ，其中 rop 是关系符（如或）， E1 和 E2 是算术式。在这里，我们只考虑前面给定文法所产生的布尔表达式：BB &B | B | B | . B | B | i rop i | i遵照我们的商定，布尔算符的优先次序（从高到低）为： .、& 、|，并假定 &和|都听从左结合规章。全部关系符的优先级都是相同的，而且高于任何布尔算符， 低于任何算术算符，关

23、系算符不得结合。表达式的真、假出口的确定：考虑表达式B1 | B2 ，如 B1 为真，就立刻知道B 也为真。因此， B1 的真出口也就是整个B 的真出口。如 B1. 为假，就 B2 必需被计值， B2 的第一个四元式就是B1 的假出口。当然，B2 的真、假出口也就是整个B 的真、假出口。类似的考虑适用于对B1 & B2的翻译，我们将 B1 | B2和 B1 & B2的翻译用下图表示，在自下而上的分析过程中，一个布尔式的真假出口往往不能在产生四元式的同时就填上。我们只好把这种未完成的四元式的的址（编号）作为B 的语义值暂存起来，待到整个表达式的四元式产生完毕之后再来回填这个未填入的转移目标。条件

24、语句对条件语句 if e S1 else S2 中的布尔表达式 e，其作用仅在于掌握对S1 和 S2 的挑选。因此，作为转移条件的布尔式e，我们可以给予它两种“出口”：一是“真”出T 口，出向 S1。一是“ 假”出口，出向 S2。于是， e的代码 F 条件语句可以翻译成如图的一般形式。非终结符e 具有两项语义值e _TC 和 e_FC，它们分别指出了尚待回填真、S2 的代码假出口的四元式串。e 的“ 真”出口只有在往回扫描到if 时才能知道，而它图3-2 条件语句的代码结构的“ 假”出口就需处处理过S1 并且到达 else 才能明确。这就是说，必需把 e_FC 的值传下去，以便到达相应的els

25、e 时才进行回填。另外，当S1 语句执行完时意味着整个if-else 语句也已执行完毕。因此，在S1 的编码之后应产生一条无条件转移指令。这条转移指令将导致程序掌握离开整个if-else 语句。但是，在完成S2 的翻译之前，这条无条件转移指令的转移目标是不知道的。甚至，在翻译完S2 之后， 这条转移指令的转移目标仍无法确定。这种情形是由于语句的嵌套性所引起的。例如可编辑资料 - - - 欢迎下载精品名师归纳总结下面的语句： if e1 if e2 S1 else S2 else S3在 S1 的代码之后的那条无条件转移指令不仅应跨过S2 而且应跨过 S3。这也就是说，转移目标的确定和语句所处的

26、环境亲密相关。条件循环语句条件循环语句 while e S 通常被翻译成图的代码结构。布尔式 e 的“ 真”出口出向 S 代码段的第一个四元式。紧接S 代码段之后应产生一条转向测试 e 的无条件转移指令。e 的“ 假”出口将导致程序掌握离开整个while语句。 e 的“ 假”出口目标即使在整个while 语句翻译完之后也未必明确。例如：ife1 while e2 S1 else S2 这种情形仍是由于语句的嵌套性引起的。所以，我们只好把它作为语句的语义值 S CHAIN 暂留下来，以便在处理外层语句时再伺机回填。语法翻译实现方法将上述语法翻译付诸实现过程中，我们仅保留了算术表达式和布尔表达式翻

27、译的文法和语义动作。面对程序语句的翻译，由于改造后含有较多的非终结符且语义动作又相对简洁，故仍复原为改造之前的程序语句文法。由于总体上构造一个SLR分析表来实现语法分析及语义加工将使得所构造的SLR分析表过大，所以将其分为下面三部分处理：(1) 对算术表达式单独处理，即为算术表达式构造一个SLR 分析表，并将赋值语句A=E 与算术表达式归为一类处理，处理之后的赋值语句仅看作为程序语句文法中的一个终结符 a。(2) 对布尔表达式也单独处理，并为其构造一个SLR 分析表，经 SLR 分析表处理后的布尔表达式看作为程序语句文法中的一个终结符e。(3) 程序语句文法此时变为：Sif e then S

28、else S | while e do S | begin L end | a 。LSL | S此时为程序语句构造相应的SLR 分析表就简洁多了。前面的程序语句文法中所添加的非终结符是为了能准时回填有关四元式转移目标而引入的，在取消了这些非终结符后又如何解决准时回填转移目标的问题了？我们实行的解决方法是增加两个数组 labelmark 和 labeltemp 来分别记录语句嵌套中每一层布尔表达式（ 假如有的话） e 的首的址以及每一层 else（ 假如有的话）之前的四元式的址（ 即无条件转出此层 if 语句的四元式）。也即，对程序语句的翻译来说： 在处理完布尔表达式 e 后，回填 if 或 w

29、hile 语句的真值链。 在归约完每一个语句 S 之后检查符号栈，看在 S 之前的文法符号是否 if 或while ，如是就回填假值链（ 假值入口为语句 S 所对应的四元式序列之后。对if 语句，此时已在该序列之后加入了一条无条件转移的四元式）。 在 if 语句中， else 前面要加入一个无条件转移的四元式转向 if 语句末尾。在while 语句尾要有一个无条件转移四元式转向 while 语句开头。四数据结构说明编译程序中涉及到的数据结构说明如下：/*/ charch=0。/* 当前字符 */ intcount=0 。staticcharspelling10=。/* 存放识别的字 */可编辑

30、资料 - - - 欢迎下载精品名师归纳总结staticcharline81=。/* 一行字符缓冲区*/ char*pline 。/* 字符缓冲区指针 */staticcharntab110010 。structntabint tc 。int fc 。ntab2200 。int label=0 。/* 存放暂时变量的表的定义*/ structrwordscharsp10 。intsy。 。/* 存放文件的结构*/struct rwords reswords10=if,sy_if,do,sy_do,else,sy_else,while,sy_while,then,sy_then,begin,sy_

31、begin,end,sy_end,and,op_and,or,op_or,not,op_not。struct aaint sy1 。int pos。buf1000,/*词法分析结果缓冲区 */ g_nCurChar,/* 当前字符 */ g_nExpCurChar,/* 当前表达式中的字符 */ E,/* 非终结符 */sstack100,/* 符号栈 */ ibuf100,stack1000 。struct aa oth。struct fourexpchar op10 。struct aa arg1。struct aa arg2。intresult。fexp200 。/* 四元式的结构 */

32、intssp=0。/* 指向 sstack100*/可编辑资料 - - - 欢迎下载精品名师归纳总结structaa*pbuf=buf 。/* 指向词法分析缓冲区*/intnlength=0 。intlnum=0 。/* 源程序长度 */ inttt1=0 。FILE*cfile 。/*/ int newt=0 。/* 暂时变量 */int nxq=100 。/*nxq 指向下一个形成的四元式的的址*/ int lr 。int lr1 。int sp=0 。/* 状态栈定义 */ int stack1100 。int sp1=0 。/* 状态栈 1 的定义 */ int num=0 。stru

33、ct llint nxq1 。int tc1 。int fc1 。labelmark10 。int labeltemp10 。int pointmark=-1,pointtemp=-1。int sign=0 。/*sign 1，表达式为赋值语句。sign 2，表达式为布尔表达式。*/五编译程序运行测试测试 PAS.dat 得源程序如下： while ab dobeginif m=n then a:=a+1 elsewhile k=h do x:=x+2 。m:=n-x/m+y 。p:=x/2-2 end#经编译程序运行后得到的输出结果如下：*词法分析结果 *30480560可编辑资料 - -

34、- 欢迎下载精品名师归纳总结423561490504000562422563105603805603405712030564Press any key to continue.425565505663805663405728056238056335056637048056234056749080568380566370可编辑资料 - - - 欢迎下载精品名师归纳总结57235057260100程序总 10 共行，产生了 51 个二元式！*变量表 *0a1b2m3n4k5h6x7y8p*状态栈变化过程及规约次序*stack0=0n=3lr=3stack1=3n=9lr=7stack2=7n=5l

35、r=11stack3=11n=4lr=4stack4=4n=0lr=2stack5=2n=9lr=6stack6=6n=1lr=10stack7=10n=7lr=5stack8=5n=2lr=104S-a 归约stack7=10n=11lr=14stack8=14n=2lr=17stack9=17n=3lr=3stack10=3n=9lr=7stack11=7n=5lr=11stack12=11n=7lr=5stack13=5n=8lr=104S-a 归约stack12=11n=11lr=15stack13=15n=8lr=102S-while e do S归约stack9=17n=11lr=18stack10=18n=8lr=101S-if e then S then S else S stack4=4n=11归约lr=9stack5=9n=8lr=13stack6=13n=7lr=5可编辑资料 - - - 欢迎下载精品名师归纳总结stack7=5n=8lr=104S-a 归