答：是有二义性的，因为句子abc 有两棵语法树(或称有两个最左推导或有两 个最右推导)最左推导1：S ? Ac ? abc

最左推导2：S ? aB ? abc

18、文法G=({E}, {+, *, i, (, )}, P, E)其中P为： E→i E→E+E E→E*E E→(E)

该文法是二义的吗？说明理由。

答： 是有二义性的，因为句子i*i+i 有两个最左推导 最左推导1：E?E+E ? E*E+E? i*E+E? i*i+E ? i*i+i 最左推导2：E?E*E ? i*E ? i*E+E? i*i+E ?i*i+i

19、自顶向下分析思想是什么？

答：从开始符出发导出句型并一个符号一个符号地与给定终结符串进行匹配。 如果全部匹配成功，则表示开始符号可推导出给定的终结符串。因此判定 给定终结符号串是正确句子。

25、简单优先方法基本思想是什么？ 答：简单优先方法基本思想是首先规定文法符号之间的优先关系和结合性质，然后再利用这种关系，通过比较两个相邻的符号之间的优先顺序来确定句型的“句柄”并进行归约。 28、语法制导翻译方法的基本思想是什么?

答：在语法分析过程中，每当使用一条产生式进行推导或归约时，就执行该产生式所对应的语义动作进行属性计算，完成对输入符号串的翻译。

33、给定下列中缀式，分别写出等价的后缀式和四元式(运算符优先级按常规理解)。

(1)(a＋b*c)/(a＋b)－d 答：后缀式：abc*+ab+/d- 四元式：?（*，b，c，t1）

?（+，a，t1，t2） ?（+，a，b，t3） ④（/，t2,t3,t4） ⑤ (-,t4,d,t5)

一、最左、最右推导及语法树

1、令文法为 E?T|E+T|E-T

T?F|T*F|T/F

F?（E）|i

1） 2）

给出i+i*i的最左推导和最右推导； 给出i+i*i的最左推导语法树。

3、下面的文法生成的是以x和y为操作数、二元运算符+、*和-为运算符的前缀表达式：

E?+EE|*EE|-EE|x|y

1）给出串+*-xyxy的最左推导和最右推导； 2）给出+*-xyxy的语法树。

4、一个上下文无关文法生成句子abbaa的推导树如下：

SAaBSSεBbBbAaa 1） 给出该句子相应的最左推导，最右推导。 2） 该文法的产生式集合P可能有哪些元素？

二、自动机的确定化和最小化

1、将下图中的自动机确定化并最小化。

aXε5b

εa1b3b4aa2ε6bεY

3、试构造正规式(0|1)*1(0|1)相应的自动机，并将其确定化

4、试构造正规式(a|b)*ab(a|b)*相应的自动机，并将其确定化和最小化。

三、FIRST和FOLLOW集合

1、考虑下面文法G1：

S?a|?|(T) T?T，S|S

1） 消去G1的左递归；

2） 经改写后的文法是否是LL(1)的？给出它的预测分析表(要求写出详细过程，应先

求出每个非终结符的FIRST和FOLLOW集合)。

2、判断下面文法是否为LL(1)文法，若是，请构造相应的预测分析表。 S→aD

D→STe|ε T→bH|H H→d|ε

3、对文法G(S)：

S ? S ?a T | a T | ?a T T ??a T | ?a

1）消除该文法的左递归和提取左公因子； 2）构造各非终结符的FIRST和FOLLOW集合；

3）构造该文法的LL(1)分析表，并判断该文法是否是LL(1)的。

四、短语、直接短语、句柄和素短语

1、对于文法G（S）：

S?(L)|aS|a L?L,S|S

1）画出句型(S,(a))的语法树。

2）写出上述句型的所有短语、直接短语、句柄和素短语。

2、文法G[S]为：

S→V V→T | ViT T→F| T+F F→)V* |(

1）画出句型ViFi(的语法树。

2）写出上述句型的所有短语、直接短语、句柄和素短语。

3、对于文法G(E):

E?T|E+T

T?F|T*F F?(E)|i

1）画出句型T*F+i1*i2的语法树。

2）写出上述句型的短语，直接短语、句柄、素短语和最左素短语。 答：短语：T*F +i1*i2, T*F, i1*i2 , i1, i2