《编译原理》实验说明书2012

《《编译原理》实验说明书2012》由会员分享，可在线阅读，更多相关《《编译原理》实验说明书2012（9页珍藏版）》请在金锄头文库上搜索。

1、1编译原理实验指导书执笔人：王一宾2012 年 2 月2实验一 词法分析器的设计一、实验目的和要求加深对状态转换图的实现及词法分析器的理解。熟悉词法分析器设计 的主要算法及实现过程。要求学生掌握词法分析器的设计过程，并实现词 法分析。二、实验基本内容给出一个简单语言的词法规则，画出状态转换图，并依据状态转换图 编制出词法分析程序，词法规则如下： 单词符号 种别码 内码 break 1 char 2 continue 3 do 4 double 5 else 6 extern 7 float 8 for 9 int 10 if 11 long 12 short 13 static 14 swit

2、ch 15 void 16 while 17 30 31 32 33 34 35 （ 36 ） 37 * 383* 39 := 40 41 42 ？ 43 ， 44 ； 45 标识符 70 常数 80 二进制形式三、问题描述及基本算法提示1 状态转换图的实现状态转换图的实现 让每个结点对应一小段程序。 需引进一组全局变量和过程（1）ch 字符变量，存放最新读进的源程序字符。 （2）strToken 字符数组，存放构成单词符号的字符串。 （3）GetChar 子程序过程，将下一输入字符读到 ch 中，搜索 指示器前移一字符位置。（4）GetBC 子程序过程，检查 ch 中字符是否为空白。若是，

3、则调用 GetChar 直至 ch 中进入一个非空白字符。 （5）Concat 子程序过程，将 ch 中的字符连接到 strToken 之 后。例如， 假定 strToken 原来的值为“AB”,而 ch 中存放 着C,经调用 Concat 后，strToken 的值就变为”ABC”。 （6）IsLetter 和 IsDigit 布尔函数过程，它们分别判断 ch 中的 字符是否为字母和数字。 （7）Reserve 整型函数过程，对 strToken 中的字符找保留字 表，若它是一个保留字，则返回它的编码，否则返回 0 值。 （8）Retract 子程序过程，将搜索指示器回调一个字符位置， 将

4、ch 置为空白字符。 （9）DTB 把 strToken 中数字串译成标准二进制码，并作为函 数值返回（十进制转换为二进制） （10）Ainput 输入源程序（键盘直接输入或以文件形式输入） 2词法分析器构造基本算法词法分析器构造基本算法 int code,value;strToken:=“”; 置 strToken 为空串 GetChar();GetBC(); if (IsLetter() beginwhile (IsLetter() or IsDigit()4beginConcat();GetChar();endRetract();code : = Reserve();if(code =

5、0)begin value : = InsertId(strToken);return($ID,value);endelsereturn(code,-); end else if (IsDigit() begin while(IsDigit()beginConcat();GetChar();endRetract();value : = InsertConst(strToken);returnr($INT,value); end else if (ch = = ) retutn($ASSIGN,-); else if (ch = +) return ($PLUS,-); else if (ch

6、=*) beginGetChar();If (ch = *) return ($POWER,-);Retract() ; return ($STAR,-); end else if (ch = ;) return ($SEMICOLON,-); else if (ch = () return ($LPAR,-); else if (ch = ) return ($RPAR,-); else if (ch = ) return ($LBRACE,-); else if (ch = ) rerurn ($RBRACE,); else ProcError(); /错误处理错误处理/5实验二 语法分析

7、器设计之一-预测分析器设计一实验目的和要求理解预测分析器程序的构造过程,掌握预测分析程序的设计。二实验基本内容编写预测分析程序，能实现 1. 给定文法，求出 FIRST（）和 FOLLOW（A） 2. 构造分析表,判断是否为 LL(1)文法 3. 任意输入一个输入串,可得到成功的分析或错误的提示三问题描述及算法提示略6实验三 语法分析器设计之二LR 分析器设计一实验目的和要求使学生理解 LR 分析器的构造过程及产生分析表的具体算法二实验基本内容选择一种 LR 文法（LR（0） 、SLR（1） 、LALR（1） 、LR（1） ） ， 设计出一个 LR 分析器。 1 对输入的文法进行判断，是否为相

8、应 LR 文法，若不是提示重新输 入文法。 2 若是构造相应的 LR 分析表。 3 输入一个句子，输出其分析过程（移进，归约，接受）三问题描述及算法提示1 文法进行拓广文法进行拓广 2 构造构造 I 的闭包的闭包 CLOSURE（I） I 是文法 G 的任一项目集。 （1）I 的任何项目都属于 CLOSURE（I） （2）若 AB 属于 CLOSURE（I） 。则关于 BVN的产生 式B 项目 BCLOSURE（I）（3）重复执行上述步骤直至 CLOSURE（I）不再增大。 3 求出状态转换函数求出状态转换函数 GO（I，X） GO（I，X）CLOSURE（J） J形如 AX 的项目|AX 属

9、于 I 4求出项目集规范族求出项目集规范族 C 的算法的算法 （1）CLOSURE（S S）C （2）对 C 中每一项目集 I 和文法 G的每个符号 X 做 若 GO(I,X)非空且不属于 C,则把 GO(I,X)加入 C （3）重复 1,2 直至 C 不再增大为止. 5. 分析表构造分析表构造 假定 C=I0,I1In,每个项目 Ik的下标 K 作为分析器状态,令包含项 目 S S 的集合 Ik的下标 K 为初态. 分析表的 ACTION 子表和 GOTO 子表的构造 (1)若项目 Aa 属于 Ik且 GO(Ik，a)Ij. aVT,则置7ACTIONk,a为”把(j,a)移进栈”,简记为

10、S j (2)若项目 AIk,那么对于任意 aVT(或#)置 ACTIONk,a为 “用产生式 A 进行归约”简记为 rj (A 是文法 G的第 j 个产生式) (3)若项目 S SIk,则置 ACTIONk,#为“接受“，记为“acc” (4)若 GO(Ik,A)= Ij,A 为非终结符,置 GOk,a= j (5)分析表中凡不能用规则 14 填入信息的空白格置上“报错标志” 6.6.写出总控程序进行分析写出总控程序进行分析 输入：一个输入串 和一张 LR 分析表 输出：若 L（G） ，对于 的一个自下而上的分析，否则出错。开始时， （S0，）在分析栈顶，在输入缓冲区 ip 指向输入串 的第

11、一个输入符号while (t=True) DOBEGIN 使 S 是栈顶状态，a 是 ip 指向的符号；if actions,a=sj thenBegin 将 a 和 j 压入分析栈， 修改 ip，使其指向下一个输入符号；end；else if actions,a=rj (A)Begin 从分析栈顶弹出 2|个符号， 令 S是当前栈顶状态; 将 A 和 gotos,A压入分析栈; 输出产生式 Aend else if actions,a=accreturnelseerror(); endif;endif; endif; end of while;end;8实验四 语法分析器设计之三算符优先分析

12、器设计一实验目的和要求熟悉 FIRSTVT、LASTVT、优先关系表构造算法的实现，掌握算 符优先分析器的构造过程。二实验基本内容编写一个自下而上的语法分析程序，能够实现 1 输入文法，判断是否为算符文法 2 构造分析表，判断是否为算符优先文法，若不是提示无法进行分 析 3 生成算符优先文法语法分析程序 4 用户输入句子若合法,输出归约的过程或语法树三问题描述及算法提示1 理解算符文法，算符优先文法的概念理解算符文法，算符优先文法的概念 2 求出求出 FIRSTVT 和和 LASTVT 3 依据依据 FIRSTVT，LASTVT 构造优先表构造优先表 FOR 每条产生式 PX1X2Xn FOR

13、 I : =1 TO n-1 DOBEGINIF Xi 和 Xi+1均为终结符 THEN 置 Xi Xi+1IF in2 且 Xi 和 Xi+2都为终结符 但 Xi+1为非终结符 THEN 置 Xi Xi+2IF Xi 为终结符而且 Xi+1为非终结符 THENFOR FIRSTVT（Xi+1）中的每个 a DO置 XiaIF Xi 为非终结符而且 Xi+1为终结符 THEN FOR LASTVT（Xi）中的每个 a DO置 aXi+1END94. 依据分析表进行算符优先分析依据分析表进行算符优先分析k : = 1; Sk : = #; REPEAT把下一个输入符号读进 a 中； IFSk VT THEN j : = k ELSE j : = k-1;WHILE Sja DOBEGIN REPEATQ : = Sj;IF Sj-1 VT THEN j : = j-1 ELSE j: =j-2 UNTIL Sj Q; 把 Sj+1 Sk归约为某个 N； k : = j=1;