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

编译原理实验指导书执笔人：王一宾2012年2月 实验一 词法分析器的设计一、实验目的和要求加深对状态转换图的实现及词法分析器的理解。熟悉词法分析器设计的主要算法及实现过程。要求学生掌握词法分析器的设计过程，并实现词法分析。二、实验基本内容给出一个简单语言的词法规则，画出状态转换图，并依据状态转换图编制出词法分析程序，词法规则如下：单词符号 种别码 内码break 1char 2continue 3do 4double 5else 6extern 7float 8for 9int 10if 11long 12 short 13static 14switch 15void 16while 17 30 31 32 33 34 35（ 36） 37* 38* 39:= 40 41 42？ 43， 44； 45标识符 70常数 80 二进制形式三、问题描述及基本算法提示1 状态转换图的实现让每个结点对应一小段程序。 需引进一组全局变量和过程 （1）ch 字符变量，存放最新读进的源程序字符。（2）strToken 字符数组，存放构成单词符号的字符串。 （3）GetChar 子程序过程，将下一输入字符读到ch中，搜索指示器前移一字符位置。 （4）GetBC 子程序过程，检查ch中字符是否为空白。若是，则调用GetChar直至ch中进入一个非空白字符。（5）Concat 子程序过程，将ch中的字符连接到strToken之后。例如， 假定strToken 原来的值为“AB”,而ch中存放着C,经调用Concat后，strToken的值就变为”ABC”。（6）IsLetter和IsDigit 布尔函数过程，它们分别判断ch中的字符是否为字母和数字。（7）Reserve 整型函数过程，对strToken中的字符找保留字表，若它是一个保留字，则返回它的编码，否则返回0值。（8）Retract 子程序过程，将搜索指示器回调一个字符位置，将ch置为空白字符。（9）DTB 把strToken中数字串译成标准二进制码，并作为函数值返回（十进制转换为二进制）（10）Ainput 输入源程序（键盘直接输入或以文件形式输入）2词法分析器构造基本算法int code,value;strToken:=“”; 置strToken为空串GetChar();GetBC();if (IsLetter()begin while (IsLetter() or IsDigit() begin Concat();GetChar(); end Retract(); code : = Reserve(); if(code = 0) begin value : = InsertId(strToken); return($ID,value); end else return(code,-);endelse if (IsDigit()begin while(IsDigit() begin Concat();GetChar(); end Retract(); value : = InsertConst(strToken); returnr($INT,value);endelse if (ch = = ) retutn($ASSIGN,-);else if (ch = +) return ($PLUS,-);else if (ch =*)begin GetChar(); If (ch = *) return ($POWER,-); Retract() ; return ($STAR,-);endelse 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(); /错误处理/实验二 语法分析器设计之一 -预测分析器设计一实验目的和要求 理解预测分析器程序的构造过程,掌握预测分析程序的设计。二实验基本内容编写预测分析程序，能实现1. 给定文法，求出FIRST（）和FOLLOW（A）2. 构造分析表,判断是否为LL(1)文法3. 任意输入一个输入串,可得到成功的分析或错误的提示三问题描述及算法提示 略实验三 语法分析器设计之二LR分析器设计一 实验目的和要求使学生理解LR分析器的构造过程及产生分析表的具体算法二 实验基本内容选择一种LR文法（LR（0）、SLR（1）、LALR（1）、LR（1），设计出一个LR分析器。1 对输入的文法进行判断，是否为相应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属于I4求出项目集规范族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,则置ACTIONk,a为”把(j,a)移进栈”,简记为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.写出总控程序进行分析输入：一个输入串和一张LR分析表输出：若L（G），对于的一个自下而上的分析，否则出错。开始时，（S0，）在分析栈顶，在输入缓冲区ip指向输入串的第一个输入符号 while (t=True) DO BEGIN使S是栈顶状态，a是ip指向的符号； if actions,a=sj then Begin将a和j压入分析栈，修改ip，使其指向下一个输入符号； end； else if actions,a=rj (A) Begin从分析栈顶弹出2|个符号，令S是当前栈顶状态;将A和gotos,A压入分析栈;输出产生式Aendelse if actions,a=acc return else error();endif; endif;endif;end of while; end;实验四 语法分析器设计之三 算符优先分析器设计一实验目的和要求熟悉FIRSTVT、LASTVT、优先关系表构造算法的实现，掌握算符优先分析器的构造过程。二实验基本内容编写一个自下而上的语法分析程序，能够实现1 输入文法，判断是否为算符文法2 构造分析表，判断是否为算符优先文法，若不是提示无法进行分析3 生成算符优先文法语法分析程序4 用户输入句子若合法,输出归约的过程或语法树三问题描述及算法提示1 理解算符文法，算符优先文法的概念2 求出FIRSTVT和LASTVT3 依据FIRSTVT，LASTVT 构造优先表FOR每条产生式PX1X2XnFOR I : =1 TO n-1 DO BEGIN IF Xi 和Xi+1均为终结符THEN置Xi Xi+1 IF in2且Xi 和Xi+2都为终结符但Xi+1为非终结符THEN置Xi Xi+2 IF Xi 为终结符而且Xi+1为非终结符THEN FOR FIRSTVT（Xi+1）中的每个a DO 置 Xia IF Xi 为非终结符而且Xi+1为终结符THENFOR LASTVT（Xi）中的每个a DO 置 aXi+1 END4. 依据分析表进行算符优先分析 k : = 1; Sk : = #;REPEAT 把下一个输入符号读进a 中； IFSk VT THEN j : = k ELSE j : = k-1; WHILE Sja DO BEGIN REPEA