资源描述：
《【精品】编译原理复习题集》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《编译原理》复习题集1•名词解释短语句柄文法上下文无关文法LL(1)文法LR(1)文法语法分析无环路有向图(DAG)后缀式语法制导翻译遍局部优化词法分析语法分析语义分析源语言源程序目标语言中间语言(中间表示)2.叙述下面的正规式描述的语言，并画岀接受该语言的最简DFA的状态转换图。(1
2、01)*0*3.Pascal语言无符号数的正规定义如下：num—>digit(.digit)?(E(+
3、-)?digit)?其中digit表示数字，用状态转换图表示接受无符号数的确定有限自动机。4.画出Pascal中实数(不带正负号，可带指数部分)的状态转换图
4、。5.用状态转换图表示接收(a
5、b)*aa的确定的有限自动机。6.处于/*和*/Z间的串构成注解，注解屮间没有*/。画出接受这种注解的DFA的状态转换图。7.某操作系统下合法的文件名为device:name.extension其屮第一部分(device:)和第三部分(.extension)可缺省,device,name和extension都是字母串，长度不限，但至少为1,画出识别这种文件名的确定有限自动机。2.构造一个DFA,它接受2>{0,1}上0和1的个数都是偶数的字符串。3.给出与下图的NFA等价的正规式。4.把下面的NFA确定化。11
6、.下面两个文法屮哪一个不是LR(1)文法？对非LR(1)的那个文法。给出那个有移进一归约冲突的规范的LR(1)项目集。S-aAcAtbbA
7、bS~》aAcAtbAb
8、b12.将下面的DFA化成最简形式。13.为语言L={vv
9、vvg(a
10、b)*并且在w的任何前缀中，a的个数不少于b的个数}写一个LR(1)文法，不准超过6个产生式。14.写一个文法，使其语言是奇数集，且每个奇数不以0开头。15.考查文法G(s):S-*(T)a+SaT-T,S
11、S⑴消除文法的左递归；⑵提取公共左因子；⑶对每个非终结符，写岀不带冋朔的递归子程序。13.设文法G(S
12、)：S->(L)
13、aS
14、aL->L,S
15、S(1)消除左递归和冋溯；(2)计算每个非终结符的FIRST和FOLLOW；(3)构造预测分析表。17・程序的文法如下：PtD£>T
16、id:八procid;£>;S(1)写一个语法制导定义，打印该程序一共声明了多少个id。(2)写一个翻译方案，打卬该程序每个变量id的嵌套深度。18.构造下面文法的LL(1)分析表。DtTLTtint
17、realL—idRRt,idR
18、£19.已知文法G(S)S-a
19、A
20、(T)TTS
21、S写出句子((a,a),a)的规范归约过程及每一步的句柄。20.已知文法G(E)E-T
22、E
23、+TT->F
24、T*FF->(E)
25、i(1)给岀句型(T*F+i)的最右推导及画岀语法树；(2)给出句型(T*F+i)的短语。21・在PASCAL语言中，简单类型的变量的声明例举如下：m,n:integerp,q,r:real为这样的声明写一个LR(1)文法(为简单起见，变量标识符都用id表示)，并根据你的文法写一个语法制导定义(或叫做为你的文法加上语义动作)，它将变量的类型填入符号表。22.一个非LR(1)的文法如下:LtMLb
26、aM—>E请给出所有有移进一归约冲突的LR(1)项目集，以说明该文法确实不是LR(1)的。22.现有句型ybalf
27、i和产生式ba,分别指出LL(1)方法和LR(1)方法在扫描到此句型的什么位置决定用此产生式？24・(a)为下面的算术表达式文法写一个语法制导的翻译方案，它将每个子表达式E的符号(即值大于零还是小于零)记录在属性E.sign中(属性值分别用POS或NEG表示)。你可以假定所有的整数都不为零，这样就不用担心零的符号。ETE*EI+E
28、-E
29、unsigned_integer(b)为上面的表达式产生栈机器屁码。代码执行后，表达式的值留在栈上。你自己设计所需的栈机器指令，并写清楚指令的含义。25.—个文法如下：St(S)S—»a请给出该文法中对活前缀
30、(((有效的LR(1)项目。26.为下面文法添加语义规则(或叫动作子程序)，输出S'产生的二进制数的值，如输入是101时，输出5。S'tSStSB
31、BBt0
32、127.写岀表达式(a+b*c)/(a+b)-d的逆波兰表示及三元式序列。28.何谓优化？按所涉及的程序范围可分为哪几级优化？29.目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？30・把表达式■(a+b)*(c+d)+(a+b+c)翻译成三元式。31.设布尔表达式的文法为E-*EiVE2E〜EiAE?E->i假定它们将用于条件控制语句屮，请(1)改写文法，使之适合进行语法制导
33、翻译；(2)写出改写后的每个产生式的语义动作。32.给出活动记录空间结构。并给岀各部分的存储对象。33•画出IFa>0THENx:=x+lELSEx:二4*(x-1
