编译原理实验题目

编译原理课程设计指导书题目一基于语法制导翻译的表达式转换编译器一、设计目的通过本课程设计获得对实际编译器的构造原理、过程和方法的感性认识，全面掌握语法制导翻译技术。二、设计内容采用语法制导翻译模式设计一个包含词法分析、语法分析、符号表管理、错误处理及输出等功能模块的、由中缀表达式到后缀表达式的完整编译器。该翻译器的规格说明如下：startlisteoflistexpr|exprexpr+term{print(‘+’)}|expr–term{print(‘-’)}|term|εtermterm*factor{print(‘*’)}|term/factor{print(‘/’)}|termdivfactor{print(‘DIV’)}|termmodfactor{print(‘MOD’)}factor(expr)|id{print(id.name)}|num{print(num.value)}三、设计要求1、使用模块化设计思想来设计该编译器；2、词法分析模块用于读入输入串，并将其转换成供语法分析模块使用的记号流。其中包括滤掉空格和注释、识别常数、识别标识符和关键字等功能；3、要求在语法分析模块中利用语法制导翻译技术完成具体的中缀表达式到后缀表达式的翻译，其中包括按前述翻译器的规格说明构建对应表达式、项、因子的非终结符expr、term和factor的函数以及检查记号是否匹配的函数；并在不匹配时调用错误处理模块；4、要求符号表管理模块主要完成符号表对应数据结构的具体实现功能；5、错误处理模块负责报告错误信息及位置，并终止分析过程；6、输出模块完成翻译后所得到的后缀表达式的输出。四、运行结果1、从键盘输入任意中缀表达式，如：4-5*6DIV4+8MOD2输出相应的后缀表达式：456*4DIV-82MOD+1、若键盘输入串为非中缀表达式时，如：4!+*5-6DIV4+8MOD2输出相应语法错误报告信息，并停止语法分析，如：line1:compilererror!五、提示1、将各功能模块设计为独立的源程序文件；2、建立一个全局头文件，将本设计所需要用到的系统头文件的打开、一些必要的宏定义和全局变量的声明信息放在该全局头文件中；3、将本设计所有文件加入一个工程文件。六、分析与讨论1、如何修改错误处理模块，使得编译器在发现错误后能跳过出错语句，继续进行语法分析；2、试使用手工构造和自动生成相结合的方法来完成本课程设计；3、仔细研读附录C有关“PL/0语言词法分析器的手工构造和自动生成”的设计内容，并通过借鉴PL/0语言词法分析器的设计方法和具体实现技术，对本课程设计的综合设计进行优化。题目二说明语句的词法分析器一、设计目的了解的基本构造原理，掌握词法分析程序的手工构造及自动构造方法。二、设计内容根据PASCAL语言的说明语句形式，用手工及自动方法构造一个对说明语句进行词法分析的程序。该程序能对从键盘输入或从文件读入的形如：“constcount=10,sum=81.5,char1=’f’,string1=”hj”,max=169；”的常量说明串进行处理，分析常量说明串中各常量名、常量类型及常量值，并统计各种类型常量个数。三、设计要求1、输入的常量说明串，要求最后以分号作结束标志；2、根据输入串或读入的文本文件中第一个单词是否为“const”判断输入串或文本文件是否为常量说明内容；3、识别输入串或打开的文本文件中的常量名。常量名必须是标识符，定义为字母开头，后跟若干个字母，数字或下划线；4、根据各常量名紧跟等号“=”后面的内容判断常量的类型。其中：字符型常量定义为放在单引号内的一个字符；字符串常量定义为放在双引号内所有内容；整型常量定义为带或不带+、-号，不以0开头的若干数字的组合；实型常量定义为带或不带+、-号，不以0开头的若干数字加上小数点再后跟若干数字的组合；5、统计并输出串或文件中包含的各种类型的常量个数；6、以二元组(类型,值)的形式输出各常量的类型和值；7、根据常量说明串置于高级语言源程序中时可能出现的错误情况，模仿高级语言编译器对不同错误情况做出相应处理。四、运行结果1、输入如下正确的常量说明串：constcount=10,sum=81.5,char1=‘f’,max=169,str1=“h*542..4S!AAsj”,char2=‘@’,str2=“aa!+h”；输出：count(integer,10)sum(float,81.5)char1(char,‘f’)max(integer,169)str1(string,“h*542..4S!AAsj”)char2(char,‘@’)str2(string,“aa!+h”)int_num=2;char_num=2;string_num=2;float_num=1.2、输入类似如下的保留字const错误的常量说明串：Aconsttcount=10,sum=81.5,char1=‘f’;输出类似下面的错误提示信息：Itisnotaconstantdeclarationstatement!Pleaseinputastringagain!3、输入类似如下含常量名或常量值错误的常量说明串：constcount=10,12sum=81.5,char1=‘ff’,max=0016；输出类似下面的错误提示信息：count(integer,10)12sum(Wrong!Itisnotaidentifier!)char1(Wrong!Therearemorethanonecharin‘’.)max(Wrong!Theintegercan’tbestartedwith‘0’.)int_num=1;char_num=0;string_num=0;float_num=0.4、其他类型的错误处理情况（略）。五、提示本课程设计重点有三个：一是作为常量名的标识符的识别；二是如何根据“=”后出现的内容来判断常量类型；三是对各种错误的处理。难点是对整型和实型常量的判断必须综合考虑多种可能情况。提示：1、用指针或数组与指针相结合来处理输入的常量说明串；2、对整型和实型常量处理时，重点考虑常数中‘0’的位置。六、分析与讨论1、若考虑用E或e的科学计数法来表示整数和实数，应该如何实现？2、若考虑布尔型常量，且规定其值只能为true或false，应该如何实现？3、如何对手工构造的词法分析程序做进一步的优化，以提高代码质量和运行效率？题目三基于预测分析方法的表达式语法分析器一、设计目的了解预测分析器的基本构成及用自顶向下的预测法对表达式进行语法分析的方法，掌握预测语法分析程序的手工构造方法。二、设计内容已知文法G[S]：S-ATA-BUT-+AT|$U-*BU|$B-(S)|m其中，$表示空串。对该文法构造预测分析表，并手工构造预测分析程序，对输入串m+m*m#进行语法分析，并根据栈的变化状态输出分析过程。三、设计要求：1、判断上述文法G[S]是否LL(1)文法，若不是，将其转变为LL(1)文法；2、对转变后的LL(1)文法建立预测分析表；3、根据清华大学出版、吕映之等编著的编译原理教材教材第五章Page88的图5.11手工构造预测分析程序；4、用预测分析程序对键盘输入串m+m*m#进行语法分析，并根据栈的变化状态输出给定串的具体分析过程。四、运行结果从键盘输入串：m+m*m#；输出：用预测分析法分析符号串m+m*m#的过程StepStackStringRuleStepStackStringRule1#Sm+m*m#S-AT10#TUmm*m#M匹配2#TAm+m*m#A-BU11#TU*m#U-*BU3#TUBm+m*m#B-m12#TUB**m#*匹配4#TUmm+m*m#M匹配13#TUBm#B-m5#TU+m*m#U-$14#TUmm#M匹配6#T+m*m#T-+AT15#TU#U-$7#TA++m*m#+匹配16#T#T-$8#TAm*m#A-BU17##接受9#TUBm*m#B-m五、提示本课程设计重点有两个：一是如何用适当的数据结构实现预测分析表存储和使用；二是如何实现各规则右部串的逆序入栈处理。建议：使用结构体数组。六、分析与讨论1、若输入串不是指定文法的句子，会出现什么情况？2、总结预测语法分析程序的设计和实现的一般方法。题目四基于算符优先分析方法的表达式语法分析器一、设计目的了解用算符优先法对表达进行语法分析的方法，编程实现算符优先表达式语法分析器。二、设计内容对简单表达式文法构造算符优先分析器。三、设计要求1、对下列简单表达式文法G[E’]构造算符优先关系表。E’→#E#E→E+T|TT→T*F|FF→P/F｜PP→(E)｜i2、根据算符优先关系表，使用栈结构来实现算符优先分析：设置两个栈：存放运算符的OPTR栈和存放操作数或运算结果的OPND栈。具体算法描述如下：（1）首先置操作数OPND栈为空栈，将#入运算符OPTR栈。（2）依次读入表达式中每个单词，若是操作数则进OPND栈，若是运算符则转（3）。（3）当前设读入的运算符为θ2，查找算符优先关系表，比较θ2与OPTR栈顶元素θ1：若θ1θ2,则θ2进OPTR栈，转（2）；若θ1＝θ2,如θ2为#，则分析成功，否则OPTR栈顶元素θ1出栈，并转（2）；若θ1＞θ2，则出栈OPND栈顶元素存放到b，又出栈其新栈顶元素存放到a，再出栈OPTR栈顶元素至t，进行运算r=atb(t为运算符)，并将结果r存入栈OPND后转（2）；（4）若θ1和θ2之间无优先关系，则报错。1、从键盘输入表达式，利用算符优先法求出其值，如输入表达式有错，则给出报错提示。表达式以“#”结尾。四、运行结果1、从键盘输入表达式串：10+15*4#输出：702、从键盘输入表达式串：10+*15+输出：Theexpressioniserror!五、提示1、构造算符优先关系表如下：+-*/()i#+-*/(=)i#=2、参考严蔚敏等编著、清华大学出版社出版的C语言版《数据结构》P52-P54的表达式求值算法。题目五递归下降分析法一、设计目的掌握递归下降分析法的基本原理，掌握预测符集的求法，掌握递归下降分析程序的构造方法。二、设计内容假设文法中有如下的产生式A1|2|…|n，则应按如下方法编写语法分析子程序procedureA()beginiftokenPredict(A1)thenθ(1)elseiftokenPredict(A2)thenθ(2)else……iftokenPredict(An)thenθ(n)elseerror()end其中对i=X1X2…Xn，θ(i)=θ’(X1);θ’(X2);…;θ’(Xn);如果XiVN，θ’(Xi)=Xi如果XiVT，θ’(Xi)=Match(Xi)如果Xi=,θ’(λ)=skip(空语句)三、设计要求：理解递归下降语法分析方法的主要原理，理解递归下降分析法对文法的要求，熟练掌握Predict集合的求法，熟练掌握文法变换算法（消除左递归和消除公共前缀）。四、提示：1.基本原理递归下降法是语法分析中最易懂的一种方法。它的主要原理是，对每个非终极符按其产生式结构构造相应语法分析子程序，其中终极符产生匹配命令，而非终极符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。2.文法要求递归下降法要满足的条件：假设A的全部产生式为Aα1|α2|……|αn，则必须满足如下条件才能保证可以唯一的选择合适的产生式predict(Aαi)∩predict(Aαj)=Φ,当i≠j.五、实验步骤1．求SNL文法中每个产生式Predict集合Predict(Aβ)=First(β)，当First(β)=(First(β)-{})∪Follow(A)，当F