编译原理习题1

《编译原理习题1》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、※<习题一>填空题：1、编译阶段按前后端组合，可分为编译前端和编译后端，其中与目标机有关的阶段一般属于分析阶段，而与源语言相关的阶段一般属于综合阶段。*2、设文法G=（VN，VT，P，S），若P中的每一个规则A→β满足：A∈VN，β∈(VN∪VT),则称此文法为0型文法。3、已知M为一个确定的有穷自动机，M=（Q，∑，q0，F，δ），则Q表示一个有穷的状态集合;∑表示字母表，δ表示状态转换函数，q0是唯一的初始状态。4、规范推导是指最右推导，每步推导只变换符号串中最右边的非终结符，其逆过程即最左规约，称为规范归约。5、LR(0)项目集规范族中的项目可分为四类，即移进

2、项目、待约项目、归约项目和接受项目，其中归约项目和归约项目或移进项目共存于一个项目集中会引起冲突。6、表达式s:=a+b*c/d+(b-d)的逆波兰式表示为sabc*d/bd-++:=。判断题：1、从功能上看，一个编译程序就是一个语言翻译程序。T2、ＬＥＸ是一个语法分析程序的生成系统。F3、一个句型的最左（直接）简单短语称为句柄。T4、已证明文法的二义性是可判定的。F5、一个ＮＦＡ一定能转换为ＤＦＡ。T6、递归下降分析法是一种不确定的自顶向下分析法。F简答：1、文法Ｇ是LL(1)文法的充要条件是什么？答：（1）.不能有左递归；（2）.LL(1)文法的分析表不出现多重

3、定义即：对于文法G的每个非终结符A的任何两条不同规则A→α

4、β，下面条件成立：•FIRST(α)∩FIRST(β)=φ即头符号集不相交。•假若β==*>ε，那么，FIRST(α)∩FOLLOW(A)=φ，即α所能推出的符号串的头符号集中的元素不能出现在FOLLOW(A)中。2、将表达式A:=B*（C-D）/D：翻译成波兰后缀表达式。答：ABCD-D/*:=※<习题二>填空题：1、对给定文法G[E]，由推导序列E=>E+T=>T+T=>i+T=>i+i可知：该推导为（最左）推导，从该推导序列可得到（5）个句型，其中的（i+i）同时也是句子。2、用四元组G=（VN，VT

5、，P，S）表示文法，则其元素VN表示（非终结符）集；元素VT表示（终结符）集；元素P表示规则集；元素S表示开始符号，它必须是一个（至少在某个产生式的左部出现一次的非终结符）符号。3、YACC是一种（语法）分析程序的自动构造工具；而LEX是一种（词法）分析程序的自动构造工具。4、对一个文法G，在其LR(0)项目集规范族DFA中，当有归约项目和（规约）项目或（移进）项目共存于同一个状态中时，该文法就不是LR(0)文法。5、编译程序是一种语言翻译程序，它将源语言程序翻译成功能等价的（目标语言程序）。6、所谓规则或产生式是指形如α→β或α::=β的(α,β)有序对，其中α是

6、字母表V的（正闭包元素）,而β是字母表V的（闭包元素）。7、设文法G=（VN，VT，P，S），若P中的每一个规则都是A→aB或A→a，其中A和B是非终结符，而a是终结符，则称此文法G为正规文法或（3）型文法。8、实用文法中不得含有形如U→U的（有害规则），也不得含有由不可达或不可终止的非终结符所构成的（多余规则）。9、对任意给定的一个正则表达式R，都可以将它转换为与之功能等价的（正则）文法，或与之功能等价的（有穷自动机）。判断题：1、在语法分析过程中，随着分析的步步进展，根据每个规则所对应的语义子程序或语义动作进行翻译的办法，称为语法制导翻译，它被现代很多编译程序所

7、采用。T2、可归前缀本身就是活前缀，它是包含句柄在内的活前缀。T简答：一、现有文法G[E]：E→EE+E→EE*E→FF→i1、证明ii*i+是文法的一个句子。2、构造句型ii*i+的语法推导树。3、指出该句型所有短语、简单短语和句柄。答：1、因为存在一个最左推导过程：E→EE+→FE+→FE+→iE+→iE*E+→iF*E+→ii*E+→ii*F+→ii*i+并且，ii*i+只含有终结符。2、EEE+EE*FFFiii3、短语：ii*i+ii*i+简单短语：i*＋句柄：i二、现有文法G[E]：E→E+T

8、E-T

9、TT→T*F

10、T/F

11、FF→i

12、(E)1、证明：F+

13、T*(E)是文法的一个句型。2、构造句型F+T*(E)的语法推导树。3、指出该句型所有短语、直接短语和句柄。答：1、因为存在这样的一个推导过程：E→E+T→T+T→F+T→F+T*F→F+T*(E)2、EE+TTT*FF（E）T3、短语：F+T*(E)T*(E)(E)简单短语：(E)句柄：(E)※<习题三>填空题：1、在语法分析过程中，随着分析的步步进展，根据每个规则所对应的语义子程序或语义动作进行翻译的办法，称为（语法制导）翻译方法，它被现代很多编译程序所采用。2、（YACC）是一种语法分析程序的自动构造工具，用它可以直接构造各种语言的语法分析器；而（LEX）