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

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

2、，单词自身的值 )#define ACC-2#define syl_if0#define syl_else1#define syl_while2#define syl_begin3#define syl_end4#define a5#define semicolon6#define e7#define jinghao8#define s9#define L10#define tempsy11#define EA12#define EO13#define plus14#define times15#define becomes 16#define op_and17#define op_or18#

3、define op_not19#define rop20#define lparent21#define rparent22#define ident23#define intconst24函数说明1 读取函数 readline( ) 、 readch( ) 词法分析包含从源文件读取字符的操作，但频繁的读文件操作会影响程序执行效率，故实际上是从源 程序文件 ”source.dat ”中读取一行到输入缓冲区，而词法分析过程中每次读取一个字符时则是通过执 行 readch( )从输入缓冲区获得的；若缓冲区已被读空，则再执行 readline( ) 从 source.dat 中读取下一行至输入缓冲区

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

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

6、作，以便转移目标的正确填入。1. 控制语句 的 SLR 分析表 1 设计过程如下： 将扩展文法 G0) SS1)Sif e S else S2)Swhile e S3)S L 4)Sa;5)LS6) LSL用 _CLOSURE 方法构造 LR(0)项目规范簇为: lo： SSS if e S else SS while e SS L Sa ;I1:SS I2:Sif e S else SI3:Swhile e SI4:S LL SL SLS if e S else SS while e SS L S a ;I5:Sa ;I6:Sif e S else SS if e S else SS whi

7、le e SS L S a ;I7:Swhile e SS if e S else SS while e SS L S a ;I8:S L I9:LS LS LL SLLSS if e S else SS while e SS L S a ;I10:Sa ; I11:Sif e S else SI12:Swhile e S I13:S L I14:SSL I15:Sif e S else SS if e S else SS while e SS L S a ;I16:Sif e S else S 构造文法 G 中非终结符的 FOLLOW 集如下：1)FOLLOW(S )= # 2)S if e

8、 S else S 得 FOLLOW(S) = else S L 得 FOLLOW(L) = 3)SS得 FOLLOW(S) = else , #LS因为 FIRST(S) = ，所以 FOLLOW(S) = else , #, 在 LR( 0)项目规范簇中，只有 I9有“移进归约”冲突， L S L S L因为 FOLLOW(L) A FIRST(L) = /所以可以用 SLR方法解决以上冲突，最后我们得到的 SLR分析表如下：ACTIONGOTOifElsewhileae#SL0S2S3S4S511ACC2S63S74S2S3S4S5985S106S2S3S4S5117S2S3S4S512

9、8S139S2S3S4R5S591410R4R4R4111512R2R2R213R3R3R314R615S2S3S4S51616R1R1R1static int actio n2011=/* 0 */2, -1,3,4, -1,5, -1, -1, -1, 1, -1,/* 1 */ -1,-1,- 1, -1, -1,-1,- 1, -1,ACC, -1, -1,/* 2 */ -1,-1,- 1, -1, -1,-1,- 1, 6, -1, -1, -1,/* 3 */ -1,-1,- 1, -1, -1,-1,- 1,7, -1, -1, -1,/* 4 */ 2, -1,3,4, -1

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

11、,/* 11*/ -1, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1,/* 12*/ -1,102, -1, -1,102, -1, -1, -1,102, -1, -1,/* 13*/ -1,103, -1, -1,103, -1, -1, -1,103, -1, -1,/* 14*/ -1, -1, -1, -1,106, -1, -1, -1, -1, -1, -1,/* 15*/ 2,-1,3, 4, -1,5, -1, -1,-1, 16, -1,/* 16*/ -1,101, -1, -1,101, -1, -1, -1,101, -1, -1;其

12、中, 刖 9 列为 action 值，后 2 列为 goto 值；016 表示 17 个移进状态（ 即 Si）; -1 表示出错；ACC 表示分析成功；而100106对应 7 个归约产生式：100SS101Sif e S else S102Swhile e S103S L 104Sa;105LS106LSL2.算术表达式的 LR 分析表 2 设计如下0)SE1)EE+E2)EE*E3)E(E)4)Ei（过程略）ACTIONGOTOI+*()#E0S3S211S4S5ACC2S3S263R4R4R4R44S3S275S3S286S4S5S97R1R5R1R18R2R2R2R29R3R3R3R3s

13、tatic int actio n1107=/* 0 */3, -1, -1,2, -1,-1,1,/* 1 */ -1,4,5, -1, -1,ACC,-1,/* 2 */ 3, -1,-1,2, -1,-1,6,/* 3 */ -1,104,104, -1,104,104, -1,/* 4 */ 3, -1, -1,2, -1,-1,7,/* 5 */ 3, -1, -1,2, -1,-1,8,/* 6 */ -1,4,5, -1, 9,-1,-1,/* 7 */ -1,101,5, -1,101,101,-1,/* 8 */ -1,102,102, -1,102,102, -1,/* 9

14、 */ -1,103,103, -1,103,103, -1;3布尔表达式的 SLR 分析表 3 设计如下：(过程略)1)SB2)Bi3)Bi rop i4)B( B )5)B! B6)A B &7)BAB8)OB |9)BOBACTIONGOTOiRop()!&II#BAO0S1S4S513781S2R1R1R1R12S33R2R2R2R24S1S4S511785S1S4S56786R4S9S10R47S1S4S514788S1S4S515789R5R5R510R7R7R711S12S9S1012R3R3R3R313S9S10ACC14R6S9S10R615R8S9S10R8static i

15、nt actio n21611=/* 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

16、, -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 */105, -1,105, -1,105, -1, -1, -1, -1, -1, -1,/*10 */107, -1,107, -1,107, -1, -1, -1, -1, -1, -1,/*11 */ -1, -1, -1, 12, -1,9, 10, -1, -1, -1, -1,/*12 */ -1, -1, -1,103, -1,103

17、,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 分析表控制语义加工的实现：当扫描 LR 分析表的当前状态为归约状态时，则在调用与该状态对应的产生式进行归约的同时， 调用相应的语义子程序进行有关的翻译工作。现在对 LR 分析器的分析栈加以扩充，使得每个文法符号之后都跟着它的语义值。为了清晰起见，我们把这个栈的每一

18、项看成由三部分组成：状态state，文法符号 syl 和语义值 val。编译程序实现算术表达式、布尔表达式及程序语句的语义加工时，都是 按这种状态栈加工方式进行的。例如：（5 + 3 ） * 6 的分析过程序号STATEValsylin put10-#(5 + 3 ) * 6 #202-#(5 + 3 ) * 6 #3023-#(5+ 3 ) * 6 #4026-5#(E+ 3 ) * 6 #50264-5-#(E+3 ) * 6 #602643#(E+3)* 6 #702647-5-3#(E+E)* 6 #8026-8#(E)* 6 #90269一8-#(E)* 6 #1001-8#E* 6

19、 #11015-8-#E* 6 #120153-8一#E*6#130158-8-6#E*E#1401-48#E#15ACC在分析过程中，第（3）步操作后的状态栈为 023，根据栈顶状态“ 3”和现行输入符号“ + ”（ in put 栏字符串的第一个字符）查分析表ACTION3 , +=R4，即按第（4）个产生式 En 来进行归约；由于产生式右部仅含一项，故去掉状态栈栈顶“3”；此时 2 变为新的栈顶状态，再查（2, E）的下一状态 s: GOTO2,E=6，即将状态 6 和文法符号 E 压栈，最后得到第（4 ）步的状态。第（7） 步操作后也是如此，当前状态栈为02647,根据栈顶状态7 和现

20、行输入符号“）”查分析表ACTION7 ,）=R1，即按第（1）个产生式 EE1+E2 进行归约；由于产生式右部有三项，故去掉状 态栈栈顶的 647三项；此时 2 变为新的栈顶状态，再查（2, E）的下一状态 s: GOTO2 , E=6,即将状态 6 和文法符号 E 压栈，最后得到第（8）步的状态。1 .布尔表达式布尔表达式在程序语言中有两个基本作用：一是用作控制语句（如 if -else 或 while 语句）的条件式；二是用于逻辑演算，计算逻辑值。布尔表达式是由布尔算符 （&、|、！）作用于布尔变量（或 常数）或关系表达式而形成的。关系表达式的形式是E1 rop E2，其中 rop 是关

21、系符（如、w、=、工、或）,E1 和 E2 是算术式。在这里，我们只考虑前面给定文法所产生的布尔表达式：BTB &B | B | B | ! B | （B） | i rop i | i.中间代码生成器设计:遵照我们的约定，布尔算符的优先顺序（从高到低）为：！、&、|,并假定&和嘟服从左结合规则。所有关系符的优先级都是相同的，而且高于任何布尔算符，低于任何算术算符，关系算符不 得结合。表达式的真、假出口的确定：考虑表达式B1 | B2，若 B1 为真，则立即知道 B 也为真；因此，B1的真出口也就是整个 B 的真出口。若 B1?为假，则 B2 必须被计值，B2 的第一个四元式就是 B1 的 假出

22、口。当然，B2 的真、假出口也就是整个 B 的真、假出口。类似的考虑适用于对 B1 & B2 的翻 译，我们将 B1 | B2 和B1 & B2 的翻译用下图表示，在自下而上的分析过程中，一个布尔式的真假出口往往不能在产生四元式的同时就填上。我们只 好把这种未完成的四元式的地址（编号）作为 B 的语义值暂存起来，待到整个表达式的四元式产生完毕之后再来回填这个未填入的转移目标。2 .条件语句对条件语句if e S1 else S2中的布尔表达式转移条件的布尔式 e,我们可以赋予它两种“口，出向 S2。于是，e 的代码 F 条件语句可以翻译成如图的一般形式。非终结符 e 具有两项语义值 e _TC

23、 和 e_FC,它们分别指出了尚待回填真、S2 的代码假出口的四元式串。e 的“真”出口只有在往回扫描到 if 时才能知道，而它图 3-2条件语句的代码结构的“假”出口则需到处理过 S1 并且到达 else 才能明确。这就是说，必须把 e_FC 的值传下去，以便到达相 应的 else 时才进行回填。另外，当S1 语句执行完时意味着整个if-else 语句也已执行完毕；因此，在 S1 的编码之后应产生一条无条件转移指令。这条转移指令将导致程序控制离开整个if-else 语句。但是，在完成 S2 的翻译之前，这条无条件转移指令的转移目标是不知道的。甚至，在翻译完S2 之后，这条转移指令的转移目标仍

24、无法确定。这种情形是由于语句的嵌套性所引起的。例如下面的语句：if el if e2 S1 else S2 else S3 在 S1 的代码之后的那条无条件转移指令不仅应跨越S2 而且应跨越S3。这也就是说，转移目标的确定和语句所处的环境密切相关。3 .条件循环语句条件循环语句 while e S 通常被翻译成图的代码结构。e,其作用仅在于控制对 S1 和 S2 的选择。 因此， 作为 出口” ：一是“真”出 T 口，出向 S1; 是“假”出布尔式 e 的“ 真”出口出向 S 代码段的第一个四元式。紧接 S 代码段之后应产生一条转向测试e的无条件转移指令。e 的“ 假”出口将导致程序控制离开整

25、个 while 语句。e 的“ 假”出口目标即 使在整个 while语句翻译完之后也未必明确。例如： if e1 while e2 S1 else S2 这种情况仍是由于语句 的嵌套性引起的。所以，我们只好把它作为语句的语义值s CHAIN 暂留下来，以便在处理外层语句时再伺机回填。语法翻译实现方法 将上述语法翻译付诸实现过程中，我们仅保留了算术表达式和布尔表达式翻译的文法和语义动作；面对程序语句的翻译，由于改造后含有较多的非终结符且语义动作又相对简单，故仍恢复为改造 之前的程序语句文法。由于总体上构造一个 sLR 分析表来实现语法分析及语义加工将使得所构造的 sLR 分析表过大，所以将其分为

26、下面三部分处理：（1）对算术表达式单独处理， 即为算术表达式构造一个 sLR 分析表， 并将赋值语句 A=E 与算术表达式归为一类处理，处理之后的赋值语句仅看作为程序语句文法中的一个终结符a。（2）对布尔表达式也单独处理， 并为其构造一个 sLR 分析表， 经 sLR 分析表处理后的布尔表达式看作为程序语句文法中的一个终结符e。（3）程序语句文法此时变为：s if e s else s | while e s | L | a;L sL | s此时为程序语句构造相应的 sLR 分析表就简单多了。前面的程序语句文法中所添加的非终结符 是为了能及时回填有关四元式转移目标而引入的，在取消了这些非终结符

27、后又如何解决及时回填 转移目标的问题呢？我们采取的解决方法是增加两个数组labelmark 和 labeltemp 来分别记录语句嵌套中每一层布尔表达式（ 如果有的话） e 的首地址以及每一层else（ 如果有的话）之前的四元式地址（ 即无条件转出此层 if 语句的四元式） 。也即，对程序语句的翻译来说：1在处理完布尔表达式 e 后，回填 if 或 while 语句的真值链；2在归约完每一个语句 s 之后检查符号栈，看在 s 之前的文法符号是否 if 或 while ，若是则 回填假值链（ 假值入口为语句 s 所对应的四元式序列之后；对 if 语句，此时已在该序列之 后加入了一条无条件转移的四

28、元式） ；3在 if 语句中， else 前面要加入一个无条件转移的四元式转向 if 语句末尾；在 while 语句尾 要有一个无条件转移四元式转向 while 语句开头。四数据结构说明编译程序中涉及到的数据结构说明如下：charch=0; /* 从字符缓冲区中读取当前字符 */intcount=0; /* 词法分析结果缓冲区计数器*/static char spelling10= ;/* 存放识别的字 */static char line81= ; /* 一行字符缓冲区（ 最多 80 个字符） */ char *pline; /* 字符缓冲区指针 */static char ntab1100

29、10;/*变量名表：共 100 项，每项长度为 10*/struct ntabint tc;/* 真值 */int fc; /*假值 */ntab2200; /* 在布尔表达式 ) 中保存有关布尔变量的真、 假值 */ int label=0; /* 指向 ntab2 的指针 */ structrewordschar sp10;int sy; /* 匹配表的结构，用来与输入缓冲区中的单词进行匹配 */struct rewords rewords8=if,syl_if,else,syl_else,while,syl_while,syl_begin,syl_end,&,op_and,|,op_or

30、,!,op_not; /* 匹配表初始化，大小为 8*/ struct aaint syl; /* 存放名字 */int pos; /* 存放名字所对应的值 */buf100, /* 词法分析结果缓冲区 */n, /* 读取二元式的当前字符 */n1, /* 当前表达式中的字符 */E, /* 非终结符 */sstack100, /* 算术或布尔表达式加工处理使用的符号栈 */ibuf100, /* 算术或布尔表达式使用的缓冲区 */ stack1000; /* 语法分析加工处理使用的符号栈 */ structaa oth; /* 四元式中空白位置 */ struct fourexpchar

31、op10;struct aa arg1;struct aa arg2;int result;fexp200; /* 四元式的结构定义 */ int ssp=0; /*指向 sstack 栈指针 */ struct aa *pbuf=buf; /* 指向词法分析缓冲区的指针 */ int nlength=0; /* 词法分析中记录单词的长度 */ int tt1=0; /* 变量名表指针 */ FILE*cfile;/* 源程序文件， 为结束符 */intlnum=0; /* 源程序行数记数 */intsign=0;/*sign=0 为赋值语句；sign=1 为 while 语句； sign=3

32、 为 if 语句 */intnewt=0; /* 临时变量计数器 */intnxq=100;/* nxq 总是指向下一个将要形成的四元式地址，每次执行gen()时，地址自动增 1*/int lr; /*扫描 LR 分析表 1 过程中保存的当前状态值 */int lr1; /*扫描 LR 分析表 2 或表 3 所保存的当前状态值 */int sp=0;/*查找 LR 分析表时状态栈的栈顶指针 */intstack1100;/*状态栈 1 定义*/int sp1=0;/*状态栈 1 的栈顶指针 */intnum=0; /* 算术或布尔表达式缓冲区指针*/struct ll int nxq1; /*记录下一条四元式的地址 */int tc1;/* 真值链 */int fc1;/*假值链 */labelmark10;/*记录语句嵌套层次的数组，即记录嵌套中每层的布尔表达式e 的首地址*/intlabeltemp10;/*记录语句嵌套层次的数组，即