Pascal语言编译器的设计与实现

1、Pascal语言编译器的设计与实现我们设计的编译程序涉及到编译五个阶段中的三个，即词法分析器、语法分析器和中间代码生成器。编译程序的输出结果包括词法分析后的二元式序列、变量名表、状态栈分析过程显示及四元式序列程序，整个编译程序分为三部分：(1) 词法分析部分(2) 语法分析处理及四元式生成部分 (3) 输出显示部分一词法分析器设计 由于我们规定的程序语句中涉及单词较少，故在词法分析阶段忽略了单词输入错误的检查，而将编译程序的重点放在中间代码生成阶段。词法分析器的功能是输入源程序，输出单词符号。我们规定输出的单词符号格式为如下的二元式： (单词种别，单词自身的值)#defineACC-2#def

2、ine 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 tempsy 15#define EA18 /E and#define EO19 /E or#define plus34#define subtract35#define times36#define divide37#de

3、fine becomes38#define op_and39#define op_or40#define op_not41#define rop42#define lparent48#define rparent49#define ident 56#define intconst 57函数说明 1 读取函数 readline( )、readchar ( )词法分析包含从源文件读取字符的操作，但频繁的读文件操作会影响程序执行效率，故实际上是从源程序文件” PAS.dat ”中读取一行到输入缓冲区，而词法分析过程中每次读取一个字符时则是通过执行 readchar ( )从输入缓冲区获得的；若缓冲区

4、已被读空，则再执行readline( )从 PAS.dat 中读取下一行至输入缓冲区。2 扫描函数 scan( ) 扫描函数 scan( )的功能是滤除多余空格并对主要单词进行分析处理，将分析得到的二元式存入二元式结果缓冲区。3 变量处理 find（ ）变量处理中首先把以字母开头的字母数字串存到 spelling 数组中，然后进行识别。识别过程是先让它与保留关键字表中的所有关键字进行匹配，若获得成功则说明它为保留关键字，即将其内码值写入二元式结果缓冲区；否则说明其为变量，这时让它与变量名表中的变量进行匹配（ 变量匹配函数 find（ ） ），如果成功，则说明该变量已存在并在二元式结果缓冲区中标

5、记为此变量（ 值填为该变量在变量名表中的位置），否则将该变量登记到变量名表中，再将这个新变量存入二元式缓存数组中。4 数字识别 number( ) 数字识别将识别出的数字填入二元式结果缓存数组。5 显示函数 显示函数的功能在屏幕上输出词法分析的结果（ 即二元式序列程序），同时给出二元式个数及源程序行数统计。二语法分析器设计 语法分析器的核心是三张 SLR 分析表以及针对这三张 SLR 分析表进行语义加工的语义动作。编译程序中语法分析处理及四元式生成部分主要是以二元式作为输入，并通过 SLR 分析表对语法分析处理过程进行控制，使四元式翻译的工作有条不紊的进行，同时识别语法分析中的语法错误。在处理

6、 if 和 while 语句时，需要进行真值或假值的拉链和返填工作，以便转移目标的正确填入。1. 控制语句的 SLR 分析表1 设计过程如下： 将扩展文法G0） Sà S1）S à if e then S else S2）S à while e do S3）S à begin L end4）S à a5）L à S6）L à S;L用_CLOSURE方法构造LR(0)项目规范簇为：I0： Sà ·SS à ·if e then S else SS à ·while

7、e do S S à ·begin L endS à · a ;I1: Sà S·I2: S à if·e then S else SI3: S à while ·e do SI4: S à begin·L end L à ·S L à ·S;L S à ·if e then S else SS à ·while e do S S à ·begin L endS à

8、· a I5: S à a· I6: S à if e·then S else S I7: Sà while e·do S I8: S à begin L·end I9: L à S·L à S·L I10: S à if e then · S else SS à· if e then S else S S à· while e do SS à· begin L end I11: S &

9、#224; while e do ·SS à· if e then S else SS à ·while e do SS à· begin L endS à· aI12: S à begin L end · I13: L à S; ·L L à·SL à·S;LS à·if e then S else SS à·while e do SS à·begin L endS

10、 à·a I14: S à if e then S·else S I15: S à while e do S· I16: L àS;L·I17: S àif e then S·else SS à·if e then S else SS à·while e do SS à·begin L endS à·aI18: S àif e then S else S·构造文法G中非终结符的FOLLOW集如下：

11、FOLLOW(L) = end FOLLOW(S) = else , ; ,end,# 在（）项目规范簇中，只有9有“移进归约”冲突，L à S·L à S·L因为FOLLOW(L) FIRST(L) = 所以可以用方法解决以上冲突，最后我们得到的分析表如下：ACTIONGOTO Ifthenelsewhilebegindoenda;e#SL0S2S3S4S511ACC2S63S74S2S3S4S5985R4R3R4R46S107S118S129R5S1310S2S3S4S51411S2S3S4S51512R3R3R3R313S2S3S4S591614S

12、1715R2R2R2R216R617S2S3S4S51818R1R1R1R1static intaction1913=/*0*/2,-1,-1,3,4,-1,-1,5,-1,-1,10,1,-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,5,-1,-1,-1,9,8,/*5*/-1,-1,104,-1,-1,-1,104,-1,10

13、4,-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,-1,-1,5,-1,-1,-1,15,-1,/*12*/-1,-1,103,-1,-1,-1,1

14、03,-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*/-1,-1,101,-1,-1,-1,101,-1,101,-1,101,-1,-1;其中，前 9

15、列为 action 值，后 2 列为 goto 值；016 表示 17 个移进状态（ 即 Si）；-1表示出错；ACC 表示分析成功；而 100106 对应归约产生式：2. 算术表达式的 LR 分析表 2 设计如下：0) S à E1) E à E+E2) E à E*E3) E à (E)4) E à i （过程略）ACTIONGOTOI+-*/()#E0S3S211S4S11S5S10ACC2S3S263R4R4R4R4R4R44S3S275S3S286S4S11S5S10S97R1R1S5S10R1R18R2R2R2R2R2R29R3R3

16、R3R3R3R310S3S21211S3S21312R6R6R6R6R6R613R5R5S5S10R5R5static 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*/3,-1,-1,-1,-1,2,-1,-1,8,/*6*/-1,4,11,5,10,-1,9,-1,-1,/*7*/101,

17、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*/105,105,105,5,10,105,105,105,-1;3.布尔表达式的 SLR 分析表3 设计如下：（过程略）1) Sà B2) B à

18、 i3) B à i rop i4) B à ( B )5) B à NOT B6) A à B AND7) B à AB8) O à B OR9) B à OBACTIONGOTOiRop()NOTANDOR#BAO0S1S4S513781S2R1R1R1R12S33R2R2R2R24S1S4S511785S1S4S56786R4S9S10R47S1S4S514788S1S4S515789R5R5R510R7R7R711S12S9S1012R3R3R3R313S9S10ACC14R6S9S10R615R8S9S10R8st

19、atic int action21611=/*0*/1,-1,4,-1,5,-1,-1,-1,13,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

20、,-1,14,7,8,/*8*/1,-1,4,-1,5,-1,-1,-1,15,7,8,/*9*/105,-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,-

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

22、* 6 #202-#(5 + 3 ) * 6 #3023-#(5+ 3 ) * 6 #4026-5#(E+ 3 ) * 6 #50264-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 栏字符串的第一个字符）查分

23、析表 ACTION3，+=R4，即按第（4）个产生式 En 来进行归约；由于产生式右部仅含一项，故去掉状态栈栈顶“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 和文法符号

24、E 压栈，最后得到第（8）步的状态。三中间代码生成器设计：布尔表达式 布尔表达式在程序语言中有两个基本作用：一是用作控制语句（ 如 if -else 或 while语句）的条件式；二是用于逻辑演算，计算逻辑值。布尔表达式是由布尔算符（ &&、| 、！）作用于布尔变量（ 或常数）或关系表达式而形成的。关系表达式的形式是 E1 rop E2，其中 rop 是关系符（ 如<、=、>或），E1和 E2是算术式。在这里，我们只考虑前面给定文法所产生的布尔表达式：BB &&B | B | B | ! B | (B) | i rop i | i遵照我们的约定，布尔

25、算符的优先顺序（ 从高到低）为：!、&&、|，并假定&&和|都服从左结合规则。所有关系符的优先级都是相同的，而且高于任何布尔算符，低于任何算术算符，关系算符不得结合。表达式的真、假出口的确定：考虑表达式 B1 | B2 ，若 B1为真，则立即知道 B 也为真；因此，B1的真出口也就是整个 B 的真出口。若 B1?为假，则 B2必须被计值，B2的第一个四元式就是 B1的假出口。当然，B2的真、假出口也就是整个 B的真、假出口。类似的考虑适用于对 B1 && B2的翻译，我们将 B1 | B2和 B1 && B2 的翻译用下图表示，在

26、自下而上的分析过程中，一个布尔式的真假出口往往不能在产生四元式的同时就填上。我们只好把这种未完成的四元式的地址（ 编号）作为 B 的语义值暂存起来，待到整个表达式的四元式产生完毕之后再来回填这个未填入的转移目标。条件语句对条件语句 if e S1 else S2 中的布尔表达式 e，其作用仅在于控制对 S1和 S2的选择。因此，作为转移条件的布尔式e，我们可以赋予它两种“ 出口”：一是“ 真”出T口，出向 S1；一是“ 假”出口，出向 S2。于是，e的代码F条件语句可以翻译成如图的一般形式。非终结符 e 具有两项语义值 e _TC 和e_FC，它们分别指出了尚待回填真、S2的代码假出口的四元式

27、串。e 的“ 真”出口只有在往回扫描到if时才能知道，而它图 3-2 条件语句的代码结构 的“ 假”出口则需到处理过 S1并且到达 else 才能明确。这就是说，必须把 e_FC 的值传下去，以便到达相应的 else时才进行回填。另外，当 S1语句执行完时意味着整个 if-else 语句也已执行完毕；因此，在 S1的编码之后应产生一条无条件转移指令。这条转移指令将导致程序控制离开整个 if-else 语句。但是，在完成 S2的翻译之前，这条无条件转移指令的转移目标是不知道的。甚至，在翻译完 S2之后，这条转移指令的转移目标仍无法确定。这种情形是由于语句的嵌套性所引起的。例如下面的语句：if e

28、1 if e2 S1 else S2 else S3 在 S1的代码之后的那条无条件转移指令不仅应跨越 S2而且应跨越 S3。这也就是说，转移目标的确定和语句所处的环境密切相关。条件循环语句条件循环语句 while e S 通常被翻译成图的代码结构。布尔式 e 的“ 真”出口出向 S 代码段的第一个四元式。紧接 S 代码段之后应产生一条转向测试 e 的无条件转移指令。e 的“ 假”出口将导致程序控制离开整个 while 语句。e 的“ 假”出口目标即使在整个 while 语句翻译完之后也未必明确。例如： if e1 while e2 S1 else S2这种情况仍是由于语句的嵌套性引起的。所以

29、，我们只好把它作为语句的语义值 S·CHAIN 暂留下来，以便在处理外层语句时再伺机回填。语法翻译实现方法 将上述语法翻译付诸实现过程中，我们仅保留了算术表达式和布尔表达式翻译的文法和语义动作；面对程序语句的翻译，由于改造后含有较多的非终结符且语义动作又相对简单，故仍恢复为改造之前的程序语句文法。由于总体上构造一个 SLR 分析表来实现语法分析及语义加工将使得所构造的 SLR 分析表过大，所以将其分为下面三部分处理：(1) 对算术表达式单独处理，即为算术表达式构造一个 SLR 分析表，并将赋值语句A=E 与算术表达式归为一类处理，处理之后的赋值语句仅看作为程序语句文法中的一个终结符

30、a。(2) 对布尔表达式也单独处理，并为其构造一个 SLR 分析表，经 SLR 分析表处理后的布尔表达式看作为程序语句文法中的一个终结符 e。(3) 程序语句文法此时变为：S à if e then S else S | while e do S | begin L end | a;L à SL | S此时为程序语句构造相应的 SLR 分析表就简单多了。前面的程序语句文法中所添加的非终结符是为了能及时回填有关四元式转移目标而引入的，在取消了这些非终结符后又如何解决及时回填转移目标的问题呢？我们采取的解决方法是增加两个数组 labelmark 和 labeltemp 来分别记

31、录语句嵌套中每一层布尔表达式（ 如果有的话）e 的首地址以及每一层else（ 如果有的话）之前的四元式地址（ 即无条件转出此层 if 语句的四元式）。也即，对程序语句的翻译来说： 在处理完布尔表达式 e 后，回填 if 或 while 语句的真值链； 在归约完每一个语句 S 之后检查符号栈，看在 S 之前的文法符号是否 if 或 while，若是则回填假值链（ 假值入口为语句 S 所对应的四元式序列之后；对 if 语句，此时已在该序列之后加入了一条无条件转移的四元式）； 在 if 语句中，else 前面要加入一个无条件转移的四元式转向 if 语句末尾；在 while语句尾要有一个无条件转移四元

32、式转向 while 语句开头。四数据结构说明 编译程序中涉及到的数据结构说明如下：/*/charch='0'/*当前字符*/int count=0;staticcharspelling10=""/*存放识别的字*/staticcharline81=""/*一行字符缓冲区*/char*pline;/*字符缓冲区指针*/staticcharntab110010;structntabint tc;int fc;ntab2200;int label=0;/*存放临时变量的表的定义 */structrwordscharsp10;intsy;/*存放

33、文件的结构*/struct rwords reswords10="if",sy_if,"do",sy_do,"else",sy_else,"while",sy_while,"then",sy_then,"begin",sy_begin,"end",sy_end,"and",op_and,"or",op_or,"not",op_not;struct aaint sy1;int pos;buf1000

34、,/*词法分析结果缓冲区*/g_nCurChar,/*当前字符*/g_nExpCurChar,/*当前表达式中的字符*/E,/*非终结符*/sstack100,/*符号栈*/ibuf100,stack1000;struct aa oth;struct fourexpchar op10;struct aa arg1;struct aa arg2;intresult;fexp200;/*四元式的结构*/intssp=0;/*指向sstack100*/structaa*pbuf=buf;/*指向词法分析缓冲区*/int nlength=0;int lnum=0;/*源程序长度*/int tt1=0;

35、FILE *cfile;/*/int newt=0;/*临时变量*/int nxq=100;/*nxq指向下一个形成的四元式的地址*/intlr;int lr1;int sp=0;/* 状态栈定义*/int stack1100;int sp1=0;/*状态栈1的定义*/int num=0;struct llint nxq1;int tc1;int fc1;labelmark10;int labeltemp10;int pointmark=-1,pointtemp=-1;int sign=0;/*sign1，表达式为赋值语句；sign2，表达式为布尔表达式。*/五编译程序运行测试测试PAS.da

36、t得源程序如下： while (a>b) do begin if m>=n then a:=a+1else while k=h do x:=x+2; m:=n-x/(m+y); p:=x/2-2 end# 经编译程序运行后得到的输出结果如下：*词法分析结果*30480560423561490504000562422563105603805603405712030564Press any key to continue.42556550566380566340572805623805633505663704805623405674908056838056637057235057260100程序总 10 共行