天津理工大学编译原理期末考试试卷

编译原理期末试题（三）含答案《编译原理》期末试题（三）1、描述由正规式b*(abb*)*(a| ε)定义的语⾔，并画出接受该语⾔的最简DFA。

2、证明⽂法E → E + id | id是SLR(1)⽂法。

3、下⾯是表达式和赋值语句的⽂法，其中and的类型是bool ? bool → bool，+的类型是int ? int → int，=的类型是int ? int →bool，:= 要求id和E的类型都是int或者都是bool。

为该⽂法写⼀个语法制导定义或翻译⽅案，它完成类型检查。

S →id := EE → E and E | E + E | E = E |id4、对于下⾯C语⾔⽂件s.cf1(int x){long x;x = 1;}f2(int x){{long x;x = 1;}}某编译器编译时报错如下：s.c: In function ‘f1’:s.c:3: warning: declaration of ‘x’ shadows a parameter请回答，对函数f2为什么没有类似的警告错误。

5、下⾯C语⾔程序经⾮优化编译后，若运⾏时输⼊2，则结果是area=12.566360, addr=-1073743076经优化编译后，若运⾏时输⼊2，则结果是area=12.566360, addr=-1073743068请解释为什么输出结果有区别。

main(){float s, pi, r;pi=3.14159;scanf("%f", &r);printf("area=%f, addr=%d\n", s=pi*r*r, &r);}6、描述由正规式b*a(bb*a)*b*定义的语⾔，并画出接受该语⾔的最简DFA。

7、下⾯的⽂法产⽣代表正⼆进制数的0和1的串集：B → B 0 | B 1 | 1下⾯的翻译⽅案计算这种正⼆进制数的⼗进制值：B →B1 0 {B.va l := B1.val? 2 }| B1 1 {B.val := B1.val? 2 +1}| 1 {B.val := 1 }请消除该基础⽂法的左递归，再重写⼀个翻译⽅案，它仍然计算这种正⼆进制数的⼗进制值。

一． 填空题（每空2分，共20分）1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为（1） 和 （2） 。

2. 规范规约是最（3）规约。

3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4） 、语义分析与中间代码生成，代码优化及（5） 。

另外还有（6）和出错处理。

4．表达式x+y*z/(a+b)的后缀式为 （7） 。

5．文法符号的属性有综合属性和 （8）。

6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i ，j]的地址计算公式为（9）。

7．局部优化是局限于一个（10）范围内的一种优化。

二． 选择题（1-6为单选题，7-8为多选题，每问2分，共20分）1. 一个上下文无关文法G 包括四个组成部分：一组终结符，一组非终结符，一个（ ），以及一组（ ）。

A ． 字符串B ． 产生式C ． 开始符号D ． 文法 2.程序的基本块是指（ ）。

A ． 一个子程序B ． 一个仅有一个入口和一个出口的语句C ． 一个没有嵌套的程序段D ． 一组顺序执行的程序段，仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（ ）分析方法。

A ． 自左向右 B ． 自顶向下 C ． 自底向上 D ． 自右向左 4．在通常的语法分析方法中，（ ）特别适用于表达式的分析。

A ． 算符优先分析法 B ． LR 分析法 C ． 递归下降分析法 D ． LL （1）分析法 5．经过编译所得到的目标程序是（ ）。

A ． 四元式序列B ． 间接三元式序列C ． 二元式序列D ． 机器语言程序或汇编语言程序 6． 一个文法所描述的语言是（ ）；描述一个语言的文法是（ ）。

A ． 唯一的 B ． 不唯一的 C ． 可能唯一，也可能不唯一7．如果在文法G中存在一个句子，当其满足下列条件（）之一时，则称该文法是二义文法。

编译原理期末考试习题及答案⼀、填空题|（每题4分，共20分）1. 乔母斯基定义的3型⽂法（线性⽂法）产⽣式形式 A→Ba|a,或A→aB|a，A，B∈Vn, a,b∈Vt 。

2.语法分析程序的输⼊是单词符号，其输出是语法单位。

3 型为 B → .aB 的LR（0）项⽬被称为移进项⽬，型为 B → a.B 的LR（0）项⽬被称为待约项⽬，4.在属性⽂法中⽂法符号的两种属性分别为继承属性和综合属性。

5、运⾏时存贮管理⽅案有静态存储分配、动态存储分配和堆式存储分配和⽅案。

⼆.已知⽂法 G(S)(1) E → T | E+T(2) T → F | F*F(3) F →（E）| i（1）写出句型（T*F+i）的最右推到并画出语法树。

（4分）（2）写出上述句型的短语，直接短语和句柄。

（4分）答：（1）最右推到（2分）E ==> T ==>F ==> (E) ==> (E+T) ==> (E+F) ==> (E+i) ==> (T+i) ==> (T*F+i)(2) 语法树（2分）（3）（4分）短语：（T*F+i），T*F+i ，T*F ， i直接短语：T*F ， i句柄：T*F三. 证明⽂法G(S) ：S → SaS |ε是⼆义的。

（6分）答：句⼦aaa对应的两颗语法树为：因此，⽂法是⼆义⽂法四.给定正规⽂法G（S）：(1) S → Sa | Ab |b(2) A → Sa请构造与之等价的DFA。

（6分）答：对应的NFA为：（6分）五. 构造识别正规语⾔b*a(bb*a)*b* 最⼩的DFA（要求写出求解过程）。

（15分）答：（1）对应的NFA（5分）（5分）六. 已知⽂法G(S) :(1) S → ^ | a | (T)(2) T → T,S | S试：（1）消除⽂法的左递归；（4分）（2）构造相应的first 和 follow 集合。

（6分）答：（1）消除⽂法的左递归后⽂法 G’（S）为：(1) S → ^ | a | (T)(2) T → ST’ | S(3) T ’ → ,ST ’ |ε（4分）七. 已知⽂法 G(S) :(1) S → SiA | A(2) A → A+B | B(3) B → A* | （试构造⾮终⽌符的firstVT 和lastVT 集合。

期末考试试卷（A）卷一、填空题（每小题2分，共20分）1、字母表∑，用∑*表示∑上所有有穷长的串集合，∑*称为∑的①。

2、设z=abc，则z的固有头是①。

3、如何由语言基本符号组成程序中各个语法成分（包括程序）的一组规则叫①。

4、设∑＝{a,b}，∑上的正规式(a|b)(a|b) 相应的正规集为①5、NFA的映象f是从"状态×字"映射到"状态子集"，f为①值函数。

6、LR分析是按规范句型的①为可归约串。

7、结点的①属性值由该结点的兄弟结点和父结点的属性值计算。

8、如果分析树中一结点的属性b依赖于属性c，那么这个结点的属性b的语义规则的计算必须在定义属性c的语义规则的计算①。

9、对于栈式符号表，引入一个显示嵌套层次关系表- ①表，该表总是指向当前正在处理的最内层的过程的子符号表在栈符号表中的起始位置。

10、任一有向边序列n1 → n2,n2 → n3,…,nk-1 → nk为从结点n1到结点nk的一条通路。

如果n1=nk，则称该通路为①。

二、单项选择（每小题2分，共14分）1、乔姆斯基把文法分成4种类型，即0型、1型、2型和3型。

其中3型文法也称为（）。

A．上下无关文法 B.正规文法C．上下文有关文法 D.无限制文法2、生成非0开头的正偶数集的文法是（）。

A． Z::=ABC B. Z::=ABCC::=0|2|4|6|8 C::=0|2|4|6|8B::=BA|B0|ε B::=BA|B0|0A::=1|2|3|…|9 A::=1|2|3|…|9C. Z::=ABC|2|4|6|8D. Z::=ABC|2|4|6|8C::=0|2|4|6|8 C::=0|2|4|6|8B::=BA|B0|0 B::=BA|B0|εA::=1|2|3|…|9 A::=1|2|3|…|93、简单优先分析法从左到右扫描输入串,当栈顶出现（）时进归约。

A.素短语B.直接短语C.句柄D.最左素短语4、同心集合并有可能产生新的（）冲突。

编译原理期末试题及答案2、写出表达式a＋b*(c-d)/e的逆波兰式和三元序列。

3、写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。

4、已知⽂法G(S)及相应翻译⽅案S→aAb {print “1”}S→a {print “2”}A→AS {print “3”}A→c {print “4”}输⼊acab, 输出是什么5、已知⽂法G(S)S→bAaA→(B | aB→Aa)写出句⼦b(aa)b的规范归约过程。

6、已知⽂法G[S]S→S*aF | aF | *aFF→+aF | +a消除⽂法左递归。

1、设⽂法G(S):S→^ | a | (T)T→T,S | S⑴消除左递归；⑵构造相应的FIRST和FOLLOW集合；⑶构造预测分析表2.语句if E then S(1) 改写⽂法，使之适合语法制导翻译；(2) 写出改写后产⽣式的语义动作。

4.设某语⾔的for语句的形式为for i:＝E(1) to E(2) do S其语义解释为i:＝E(1)LIMIT:＝E(2)again: if i＜＝LIMIT thengoto againEnd;（1）写出适合语法制导翻译的产⽣式；（2）写出每个产⽣式对应的语义动作。

7.已知⽂法G(S)S→a | ^ | (T)T→T,S | S(1) 给出句⼦(a,(a,a))的最左推导；(2) 给出句型((T,S),a)的短语, 直接短语，句柄。

8.对于C 语⾔do S while E语句(1)改写⽂法，使之适合语法制导翻译；(2)写出改写后产⽣式的语义动作。

9.已知⽂法G(S)S→aAcBeA→Ab| bB→d(1)给出句⼦abbcde的最左推导及画出语法树；(2)给出句型aAbcde的短语、素短语。

10.设⽂法G(S):S→(T) | aS | aT→T,S | S⑴消除左递归和提公共左因⼦；⑵构造相应的FIRST和FOLLOW集合；⑶构造预测分析表。

北方工业大学《编译原理》课程期末复习题（答案）A 卷开课学院考试方式：闭卷考试时间：120 分钟班级 姓名 学号 一判断题（每个小题1分，共10分）1. 程序语言主要由语法和语义两方面定义。

（ ）2. 自上而下分析方法会遇到的主要问题有左递归和回溯。

（ ）3. 已知文法G ：E →i | EAE ，A →+|* ，其中的终结符号集包括{i ，+}。

（ ）4. 编译程序是将高级语言程序翻译成机器语言程序。

（ ）5. 只含有综合属性的属性文法称为S-属性文法。

（ ）6. LL(1)文法中第一个L 的含义是从左到右扫描输入串。

（ ）7. 在编译中进行语法检查的目的是为了发现程序中所有错误。

（ ）8. 一个语义子程序描述了一个文法所对应的翻译工作。

（ ）9. 一个句型的直接短语是唯一的。

（ ） 10. 确定的自动机以及不确定的自动机都能正确地识别正规集。

（ ） 解：1.√ 2.√ 3.× 4.× 5.√ 6.√ 7.× 8.× 9.× 10.√二、选择题（每个小题1分，共20分）1. 文法分为四种类型，即0型、1型、2型、3型。

其中3型文法是____。

A. 短语文法 B. 正规文法 C. 上下文有关文法 D. 上下文无关文法2. 不可能是目标代码。

A. 汇编指令代码B. 可重定位指令代码C. 绝对指令代码D. 中间代码 3. 将编译程序分成若干个“遍”是为了 。

A. 提高程序的执行效率B. 利用有限的机器内存并提高机器的执行效率C. 使程序的结构更加清晰D. 利用有限机器内存但降低了机器的执行效率 4. 后缀式ab+cd+/可用表达式 来表示。

订线装A. a+b/c+dB. (a+b)/(c+d)C. a+b/(c+d)D. a+b+c/d5. 文法G：S→xSx|y所识别的语言是。

A. xyxB. (xyx)*C. x n yx n(n≥0)D. x*yx*6. 文法G[E]：E→E+T|TT→T*P|PP→(E)|i则句型P+T+i的句柄和最左素短语为。

编译原理复习题一、填空题：1、编译方式与解释方式的根本区别在于（是否生成目标代码）。

2、对编译程序而言，输入数据是（源程序），输出结果是（目标程序）。

3、如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段：（编译阶段）和（运行阶段）。

4、如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分成三个阶段：（编译阶段）、（汇编阶段）和（运行阶段）。

5、自顶向下语法分析方法会遇到的主要问题有（回溯）和（（左递归带来的）无限循环）。

6、LL(k)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“k”的含义是（向输入串中查看K个输入符号）。

7、LL(1)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“1”的含义是（向输入串中查看1个输入符号）。

8、自顶向下语法分析方法的基本思想是：从（识别符号）出发，不断建立（直接推导），试图构造一个推导序列，最终由它推导出与输入符号相同的（符号串）。

9、自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行（直接归约），试图（归约）到文法的（识别符号|开始符号）。

10、LR(0)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“0”的含义是（向貌似句柄的符号串后查看0个输入符号）。

11、LR(1)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。

12、SLR(1)分析法的名字中，“S”的含义是（简单的），“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。

13、在编译过程中，常见的中间语言形式有（逆波兰表示）、（三元式）、（四元式）和（树形表示）。

编译原理期末考试试卷（D卷）编译原理期末考试试卷（D 卷）⼀、单项选择题（每⼩题2分，共30分）1、编译程序是对_ _____程序进⾏翻译。

A.⾃然语⾔B.⾼级语⾔C.汇编语⾔D.机器语⾔2、描述语⾔L={ a n b n | n ≥。

3、设有⽂法G=({b},{S,B}, S, { S →bB , B →bS |ε} )，该⽂法描述的语⾔是。

A. L(G)={b n | n ≥1 } B. L(G)={ b 2n | n ≥1} C. L(G)={ b 2n+1 | n ≥0} D. L(G)={ b 2n | n ≥0} 4、下图DFA 所识别的语⾔为_______ 。

A. a 3n+1(n ≥0)B. a 2n+1(n ≥0)C. a 2n+1(n ≥1)D. a 3n+1(n ≥1) 5、下述正规式等价的是。

A.(a|b)*与a *|b *B.(ab)*与a *b *C.(a|b)*与(ab)*D.(a|b)*与(a *b *)*6、如果⽂法G 中没有形如 A →…BC …的产⽣式，其中A ，B ，C 表⽰⾮终结符，则称⽂法G 为 __________。

A.算符⽂法B.算符优先⽂法C.LR(0)⽂法D. LL(1)⽂法 7、算符优先分析法从左到右扫描输⼊串，采⽤移进-归约的⽅式，当栈顶出现___________时进⾏归约。

A. 素短语B.最左素短语C. 句柄D. 直接短语 8、LR 语法分析栈中存放的状态是识别⽂法规范句型__________的DFA 状态。

A. 句柄B.前缀C. 活前缀D. 项⽬A. S →AB A →Aa | a B →Bb | b C. S →aSb | ab D. S →aSb | ε9、中缀表达式a↑(b / d-c)的后缀式是_________。

A.abdc-/↑B. abd/c-↑C. ab/dc-↑D. abdc/-↑10、以下说法正确的是_________。

2020-2021《编译原理》期末课程考试试卷B适用专业：考试日期：闭卷所需时间：120分钟总分：100分一、填空题：（每空1分，共10分）1.解释系统与编译系统的区别在于和。

2.在编译过程中始终伴随着管理和出错处理过程。

3.语法分析的方法为和两大类。

4.LL(1)文法中不能有和。

5.词法分析器中单词的描述工具是 ,单词的识别工具。

6.算符优先语法分析，在符号栈栈顶出现时，进行规约处理。

二、单选题（每小题2分，共10分）1.词法分析器的加工对象是（）A.中间代码B.单词C.源程序D.元程序2.同正则表达式a*b*等价的文法是（）A. G1:S→aS|bS|εB. G2: S→aSb|εC. G3:S→aS|Sb|εD. G4: S→abS|ε3.文法G[A]:A→bH H→BA B→Ab H→a 不是（）A. 2型文法B. 3型文法C. 0型文法D.1型文法4.算符优先分析每次都是对（）进行规约。

A.短语B.最左素短语C.素短语D.句柄5.( )不是DFA的成分。

A.有穷字母表B. 初始状态集合C.终止状态集合D.有限状态集合三、问答题（第1,5小题每题15分，其余每小题10分，共80分）1. （15分）解释下列术语：（1）编译程序（2）句柄（3）上下文无关文法2.编译程序主要有哪些构成成分？（10分）3.给出描述语言L={a n b2n c m|n,m≥0}的cfg。

（10分）4.（10分）将下图中的DFA M最小化。

5. （15分）判断文法G[S]:S→aHH→aMd|dM→Ab|εA→aM|e是否为LL(1)文法？给出判断过程。

6. （10分）改写文法G[E]：E → E+T|TT →T*F|FF →(E)| a为无左递归文法。

7. （10分）已知文法G[S]为：S→VV→T|ViTT→F|T+FF→)V*|(请指出句型(+(i( 规范推到，并指出句型F+Fi( 中的短语、句柄和素短语。

2020-2021《编译原理》期末课程考试试卷B答案适用专业：考试日期：闭卷所需时间：120分钟总分：100分一、填空题：（每空1分，共10分）1. 边翻译边执行和不生成目标代码。

编译原理期末考试试题（卷）（C卷）编译原理期末考试试卷（ C 卷）⼀、单项选择题（每⼩题2分，共30分）1、编译程序是对_ _____程序进⾏翻译。

A. ⾃然语⾔B. 汇编语⾔C. ⾼级语⾔D. 机器语⾔2、描述语⾔L={ a m b n | m ≥1。

3、设有⽂法G=({b},{S,B}, S, { S →bB , B →bS |ε} )，下列哪个符号串不是该⽂法的句⼦。

A. bB. bbC. bbbD. bbbbb 4、下图DFA 所识别的语⾔为_______ 。

A. 含有偶数个0偶数个1的⼆进制串 B. 含有偶数个0奇数个1的⼆进制串 C. 含有奇数个0偶数个1的⼆进制串 D. 含有奇数个0奇数个1的⼆进制串 5、下述正规式等价的是。

A.(a|b)*与(a *b *)*B.(ab)*与a *b *C.(a|b)*与(ab)*D. (a|b)*与a *|b *6、设有⼀个LR(1)项⽬集I ={ X →α.bB,a B →α.,a }则该项⽬集 __________。

A.不含冲突项⽬B. 含有移进-归约冲突C.含有归约-归约冲突D. 含有移进-待约冲突 7、LR 语法分析栈中存放的状态是识别⽂法规范句型__________的DFA 状态。

A. 句柄B.前缀C. 活前缀D. 项⽬A. S →ABA →Aa | aB →Bb | b C. S →aSb | ab D. S →aSb | ε8、有⽂法如S → r DD → D,i | i则FIRSTVT(D)=_________。

A.{ i }B. {i ,}C. { i r }D. { i r ,}9、有⽂法如 S → r DD → D,i | i则 i 和，的优先关系是_________。

A.没有优先关系B. 等于C. 低于D. ⾼于10、算符优先分析法从左到右扫描输⼊串，采⽤移进-归约的⽅式，当栈顶出现___________时进⾏归约。

A. 素短语B.C.D. 直接短语11、局部优化是局限于⼀个_________范围内的⼀种优化。

.得分 20分）填空题（每空2分，共一．但大部分编译中采用的方案有两1. 不同的编译程序关于数据空间的存储分配策略可能不同，。

（2）种：静态存储分配方案和动态存储分配方案，而后者又分为（1）和 3）规约。

2. 规范规约是最（、语义分析与中间代码生成，代码优化及）个阶段：词法分析、（453. 编译程序的工作过程一般划分为 6）和出错处理。

）。

另外还有（（5。

（7）4．表达式x+y*z/(a+b)的后缀式为。

（8） 5．文法符号的属性有综合属性和j]，a[1..15,1..20]某个元素a[i6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组。

的地址计算公式为（9））范围内的一种优化。

7．局部优化是局限于一个（10得分分）分，共201-6为单选题，7-8为多选题，每问2（二．选择题，以）包括四个组成部分：一组终结符，一组非终结符，一个（ 1. 一个上下文无关文法G 。

）及一组（文法．开始符号 D．A．字符串 B．产生式 C ）。

2.程序的基本块是指（一个仅有一个入口和一个出口的语句一个子程序 B．A．一组顺序执行的程序段，仅有一个入口和一个出口一个没有嵌套的程序段 D．C．）分析方法。

高级语言编译程序常用的语法分析方法中，递归下降分析法属于（3.自右向左． D自顶向下 C．自底向上 BA．自左向右．）特别适用于表达式的分析。

（ 4．在通常的语法分析方法中， LR分析法．．算符优先分析法 BA 1）分析法． LL（ DC．递归下降分析法。

．经过编译所得到的目标程序是（5 ）间接三元式序列．四元式序列A． B 机器语言程序或汇编语言程序．二元式序列 D．C 。

））．6 一个文法所描述的语言是（；描述一个语言的文法是（ C B A．唯一的．不唯一的．可能唯一，也可能不唯一..7．如果在文法G中存在一个句子，当其满足下列条件（）之一时，则称该文法是二义文法。

A．其最左推导和最右推导相同 B．该句子有两个不同的最左推导C．该句子有两个不同的最右推导 D．该句子有两棵不同的语法树E．该句子对应的语法树唯一8．下面（）语法制导翻译中，采用拉链—回填技术。

1、试为表达式 w+（a+b)＊（c+d/(e-10）+8) 写出相应的逆波兰表示。

2、写出表达式a＋b＊(c-d)/e的逆波兰式和三元序列。

3、写出表达式a:=（b+c)＊e+(b+c)/f的逆波兰式和三元序列。

4、已知文法G(S)及相应翻译方案S→aAb ｛print “1”}S→a {print “2”｝A→AS {print “3”｝A→c ｛print “4"｝输入acab, 输出是什么？5、已知文法G（S)S→bAaA→(B | aB→A a)写出句子b（aa）b的规范归约过程.6、已知文法G［S］S→S*aF | aF ｜＊aFF→+aF | +a消除文法左递归。

1、设文法G（S）：S→^ ｜ a | （T）T→T,S ｜ S⑴ 消除左递归;⑵ 构造相应的FIRST和FOLLOW集合;⑶ 构造预测分析表2.语句 if E then S(1）改写文法，使之适合语法制导翻译；（2）写出改写后产生式的语义动作。

4。

设某语言的for语句的形式为for i：＝E（1) to E（2) do S其语义解释为i：＝E(1）LIMIT:＝E（2）again: if i＜＝LIMIT thenBeginS；i：＝i＋1goto againEnd；（1）写出适合语法制导翻译的产生式;（2)写出每个产生式对应的语义动作。

7。

已知文法G(S)S→a ｜ ^ | （T）T→T，S ｜ S（1) 给出句子(a，（a,a))的最左推导;（2) 给出句型（(T,S），a）的短语, 直接短语，句柄。

8。

对于 C 语言do S while E语句(1）改写文法，使之适合语法制导翻译;(2）写出改写后产生式的语义动作.9。

已知文法G(S）S→aAcBeA→Ab｜ bB→d（1)给出句子abbcde的最左推导及画出语法树；（2）给出句型aAbcde的短语、素短语。

10。

设文法G（S）:S→（T) | aS | aT→T,S ｜ S⑴消除左递归和提公共左因子；⑵构造相应的FIRST和FOLLOW集合；⑶构造预测分析表。

1、试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。

2、写出表达式a＋b*(c-d)/e的逆波兰式和三元序列。

3、写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。

4、已知文法G(S)及相应翻译方案S→aAb {print “1”}S→a {print “2”}A→AS {print “3”}A→c {print “4”}输入acab, 输出是什么？5、已知文法G(S)S→bAaA→(B | aB→A a)写出句子b(aa)b的规范归约过程。

6、已知文法G[S]S→S*aF | aF | *aFF→+aF | +a消除文法左递归。

1、设文法G(S):S→^ | a | (T)T→T,S | S⑴ 消除左递归；⑵ 构造相应的FIRST和FOLLOW集合；⑶ 构造预测分析表2.语句 if E then S(1) 改写文法，使之适合语法制导翻译；(2) 写出改写后产生式的语义动作。

4.设某语言的for语句的形式为for i:＝E(1) to E(2) do S其语义解释为i:＝E(1)LIMIT:＝E(2)again: if i＜＝LIMIT thenBeginS;i:＝i＋1goto againEnd;（1）写出适合语法制导翻译的产生式；（2）写出每个产生式对应的语义动作。

7.已知文法G(S)S→a | ^ | (T)T→T,S | S(1) 给出句子(a,(a,a))的最左推导；(2) 给出句型((T,S),a)的短语, 直接短语，句柄。

8.对于 C 语言do S while E语句(1)改写文法，使之适合语法制导翻译；(2)写出改写后产生式的语义动作。

9.已知文法G(S)S→aAcBeA→Ab| bB→d(1)给出句子abbcde的最左推导及画出语法树；(2)给出句型aAbcde的短语、素短语。

10.设文法G(S):S→(T) | aS | aT→T,S | S⑴消除左递归和提公共左因子；⑵构造相应的FIRST和FOLLOW集合；⑶构造预测分析表。

《编译原理》期末考试复习题一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）×1．计算机高级语言翻译成低级语言只有解释一种方式。

()×2．在编译中进行语法检查的目的是为了发现程序中所有错误。

()√3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。

()×4．正则文法其产生式为 A->a ， A->Bb, A,B∈VN ， a 、b∈VT 。

()√5．每个文法都能改写为 LL(1) 文法。

()√6．递归下降法允许任一非终极符是直接左递归的。

()×7．算符优先关系表不一定存在对应的优先函数。

()×8．自底而上语法分析方法的主要问题是候选式的选择。

()×9．LR 法是自顶向下语法分析方法。

()×10．简单优先文法允许任意两个产生式具有相同右部。

()三、填空题(每空1分，共10分)1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有__ ___和 ___ _。

表格管理出错处理_2．若源程序是用高级语言编写的,__ __是机器语言程序或汇编程序,则其翻译程序称为 __ __ 。

_目标程序_编译程序3．编译方式与解释方式的根本区别在于__ __。

是否生成目标代码_4．对编译程序而言,输入数据是__ __, 输出结果是__ ___。

_源程序目标程序5．产生式是用于定义__ __的一种书写规则。

_语法成分6．语法分析最常用的两类方法是___ __和__ __分析法。

自上而下_自下而上四、简答题（20分）1. 什么是句子？什么是语言 ?答：(1)设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈VT*),则称x是文法的一个句子。

(2)设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│S x,x∈VT*} 。