编译原理 复习资料

2.LEX是用于词法分析的工具，YACC是用于语法分析的工具。

3.解释程序和编译程序的区别在于是否生成目标代码。

4.任一文法终结符集合和非终结符集合的交集是空集。

5.描述程序设计语言语法的BNF方法中，“：：=”表示定义为，“|”表示或，[W]表示W可出现0或1次，｛W｝表示W可出现n（n≥0）次。

6.已知文法G[G]: S→aSb|ab|ε，该文法描述的语言L(G)=｛anbn|n≥0｝。

7.单词的描述工具有正规文法、正规式和有穷自动机，他们之间存在等价性。

8.高级程序设计语言的单词通常分为五类，它们是关键字、标识符、常数、运算符和界符。

9.正则式中的“|“表示或，“*”表示闭包。

10.自顶向下语法分析方法会遇到的主要问题有回溯，以及左递归带来的无限循环。

11.算符优先分析法每次归约当前句型的最左素短语，规范归约中每次归约的是当前句型的句柄。

12.对文法G[G]: S→a|b|cTc，T→S|TdS而言，FIRSTVT(T)=｛a,b,c,d｝。

13.活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。

14.对文法G[G]: E→E*T|T, T→T+i|i的句子1+2*8+6进行归约后的结果为42（23，42）。

15.在LR(0),SLR(1),LR(1),LALR(1),四种文法中，描述能力最强的是LR(1)。

1.0型文法中每条规则左部至少包含一非终结符（√）。

2.3型文法一定是2型、1型、0型文法（√）。

3.对无二义性文法而言，无论最左推导还是最右推导，同一个句子的语法树是一样的。

4.若一个文法是递归的，则其语言中句子的个数必定是无穷个。（√）

5.文法规则右部的符号一定是终结符。（×）

6.语法树描述的是一个文法。（×）

7.若G是正则文法，则G一定是上下文无关文法。（√）

8.正则文法、正则式和有限自动机三者都是描述正则集的有力工具，它们的描述能力是等价的。（√）

9.LL（1）分析法必须要求原文法不含左公因子和左递归。（√）

10.对于LR(0)文法，我们可直接从它的项目集规范族和活前缀识别自动机的状态转换函数GO构造了LR分析表。（√）

1.BNF是一种广泛采用的描述（文法）的工具。

2.无符号常数的识别和拼数工作通常在（词法分析）阶段完成。

3.“运算符与运算对象类型不匹配”属于（语义错误）

4.将汇编语言程序翻译成机器可以执行的目标程序的工作由（汇编程序）完成。

5.在汇编过程中，汇编程序能够找到的错误包括（全部语法错误和部分语义错位）

6.由“非终结符→符号串”形式的规则构成的文法是（2型文法）

7.关于短语和句柄，正确的叙述为（直接短评才可能是句柄）

8.同正则式a*b*等价的文法是（G3:S→aS|Sb|ε）

9.文法G[S]:S→xSy|y所描述的语言是（x^nyx^n(n>=0)）

10.若G为一文法，Vt是该文法的终结符号集合，L(G)和Vt^*之间的关系是（L(G)是Vt^*的子集）

11.有限自动机能够识别（正则文法）

12.同正则式（a|b）+等价的正则式是（（a|b）(a|b)*）

13.递归子程序法属于（自顶向下）语法分析法

14.Chmosky的3型语言是这样的一种语言，其产生式为（A::=a   A::=aB）

15.若a为终结符，则A→α●aβ为（移进）项目

16.设a,b,c是文法的终结符，且满足优先关系a=.b和b=.c，则（以上都不一定成立）

17.在yacc程序中main必须调用（yyparse）函数来进行语法分析

18.赋值语句-(a+b)/(c-d)-(a+b*c)的逆波兰表示是（xab+-cd-/abc*+-）

1.例7.6，while(a      翻译成一串四元式：

 100（j<，a，b，102）

 101（j，-，-，107）

 102（j<，c，d，104）

 103（j，-，-，100）

 104（+，y，z，T）

 105（：=，T，-，x）

 106（j，-，-，100）

 107

2.LR分析器：一个LR分析器的工作过程可看成是栈里的状态序列、已归约串和输入串所构成的三元式的变化过程。分析开始时的初始三元式为（s0,  #,  a1a2···an #）

 其中，s0为分析器的初态；#为句子的左括号；a1 a2···an为输入串；其后的#为结束符（句子右括号）。分析过程每步的结果可表示为（s0s1···sm ，#X1 X2 ···Xm，ai ai+1···an#）

分析器的下一步动作是由栈顶状态sm和现行输入符号ai所唯一决定的。即执行AC-TION[sm，ai]所规定的动作。经执行每种可能的动作之后，三元式的变化情形是：

（1）若ACTION[sm，ai]为移进，且s=GOTO[sm，ai]，则三元式变成：

 （s0s1···sm s，#X1 X2 ···Xm ai， ai+1···an #）

（2）若ACTION[smai]=[A→β],则按产生式A→β进行归约。此时三元式变为

  （s0s1···sm-r s，#X1 X2 ···Xm-r A，ai ai+1···an#）此处s= GOTO[sm-r，A]，r为β的长度，β= Xm-r+1 ···Xm。

（3）若ACTION[sm，ai]为“接受”，则三元式不再变化，变化过程终止，宣布分析成功。

（4）若ACTION[sm，ai]为“报销”，则三元式的变化过程终止，报告错误。

 一个LR分析器的工作过程就是一步一步的变换三元式，直至执行“接受”或“报销”为止。