(6)对一个右线性文法G，必存在一个左线性文法G'，使得L(G)=L(G')，反之亦然。（）
答案 (1) T (2) T (3) F (4) F (5) T 3.3 描述下列各正规表达式所表示的语言。 (1) 0(0|1)*0 (2) ((ε|0)1*)* (3) (0|1)*0(0|1)(0|1) (4) 0*10*10*10*
(5) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
答案 (1) 以0开头并且以0结尾的，由0和1组成的所有符号串
(2) {α|α∈{0,1}*}即由0和1组成的所有符号串。 (3) 由0和1组成的符号串，且从右边开始数第3位为0。 (4) 含3个1的由0和1组成的所有符号串。 {α|α∈{0,1}+，且α中含有3个1 } (5) {α|α∈{0,1}*,α中含0和1的数目为偶数。} 4.10 已知文法G[S]，其产生式如下：S→(L)|a L→L,S|S 文法G[S]的算符优先关系由下表给出。建立与下表相应的算符优先函数并用算符优先分析法分析句子(a,(a,a))。 文法G[S]的算符优先关系表：
解：对每个终结符或＄建立符号f与g，把f(和g)分成一组。 根据G[S]的算符优先关系表，画出如下的有向图:
优先函数如下：
用算符优先分析法分析句子(a,(a,a))
4.19 (1) 存在有左递归规则的文法是LL(1)的。 (2) 任何算符优先文法的句型中不会有两个相邻的非终结符号。 (3) 算符优先文法中任何两个相邻的终结符号之间至少满足三种 关系(＜·，·＞，
)之一。
(4) 任何LL(1)文法都是无二义性的。 (5) 每一个SLR(1)文法也都是LR(1)文法。
(6) 存在一种算法，能判定任何上下文无关文法是否是LL(1)的。 (7) 任何一个LL(1)文法都是一个LR(1)文法，反之亦然。 (8)' LR(1)'括号中的1是指，在选用产生式A→α进行分析，看当前读入符号是否在FIRST(α)中。
答案：(1)× (2)√ (3)× (4)√ (5)√ (6)√ (7)× (8)× 4.20 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类。__A__和LL(1)分析法属于自顶向下分析；__B__和LR分析法属于自底向上分析。自顶向下分析试图为输入符号串构造一个__C__；自底向上分析试图为输入符号串构造一个__D__。采用自顶向下分析方法时，要求文法中不含有__E__。 A、B： ①深度分析法 C、D： E：
③算符优先分析法
①语法树 ③最左推导 ①右递归 ③直接右递归
②宽度优先分析法 ④预测递归分析法
②有向无环图 ④最右推导 ②左递归 ④直接左递归
A：④ B：③ C：③ D：④ E：②
4.21 自底向上语法分析采用__A__分析法，常用的是自底向上语法分析有算符优先分析法和LR分析法。LR分析是寻找右句型的 __B__；而算符优先分析是寻找右句型的__C__。LR分析法中分析能力最强的是__D__；分析能力最弱的是__E__。 A：
①递归
②回溯
③枚举
④移进－规约 ④句柄 ④LALR(1)
B、C： ①短语 ②素短语 ③最左素短语
③LR(1)
D、E： ①SLR(1) ②LR(0)
A：④ B：④ C：③ D：③ E：②
5.5 用S的综合属性val给出在下面的文法中的S产生的二进制数的值（例如，对于输入 101.101，S.val=5.625）： S→L.L|L L→LB|B B→0|1 （1）试用各有关综合属性决定S.val。
（2）试用一个语法制导定义来决定S.val,在这个定义中仅有B的综合属性，设为c，它给出由B 生成的位对于最后的数值的贡献。例如，在101.101中的第一位和最后一位对于值5.625的贡献分别为4和0.125。
解答：(1)用综合属性决定s.val的语法制导定义：
产生式 S -> L S -> L1.L2 L -> B L -> L1B B -> 0 B -> 1 S.val:=L.val; S.val:=L1.val+L2.val*L2.p; L.val:=B.val; L.p:=2-1; L.val:=L1.val*2+B.val; L.p:=L.p*2-1; B.val:=0; B.val:=1; 语义规则 注：L.p表示恢复L.val的因子。
(2)分析：设B.c是B的综合属性，是B产生的位对最终值的贡献。要求出B.c，必须求出B产生位的权，设B.i。B.i的求法请参看下面的图示：