编译原理ch3-8e.ppt

1、编译原理练习课，中国海洋大学计算机系加林，第三章练习：例1，下面的异议语法描述了命题计算公式的语法。相当的非疑问法S S and S | S or S | not S | p | q | (S)非疑问法生成为E or T | T T T and F | F F F not F |(E)| p | q相当的非疑问法S and S | (e) | p | q生成的语法SaSbS | bSaS | (a)abab中两个茄子的最左边推导：SLM asbs lm absa SBS lm abas bs lm abas lm ababs lm asbs lm ABS lm ABS lm ABS lm AB

2、S lm ABS lm ABS lm abas ，第3章练习：示例2，(b)最右侧的派生(与第二个最左侧的派生相对应的最右侧的派生)s RM asbs RM asbasbs RM ASB RM as Bab RM abab(c)相对应的分析树：注意：分析树没有箭头。(d)牙齿语法生成的语言：具有相同a，b数的字符串集；第3章练习：示例3，语法：R R | R | RR | R* | (R) | a | b (b)构造等效的郑智薰异议语法分析语法：SabS | bS | (b)a和B的数量相同的字符串1:S A b| B A | A S | B A B S | A B B(B)继续异议语法2:s

3、a SBS | bsas | aabbabas(B)异议语法1的结论：S A | B (a，B数不同的字符串，起始符号)A A | A A (a (a大于B的字符串)b b | b b b (b大于A的字符串)A a C | b As是直接(间接)左递归吗？l呢？A | (a，a，(a，)，a) S (L) | a L S L，S L |，第3章练习：示例5，(b)为(a)的语法结构预测分析器非迭代：(match()；else if(lookahead=a)match(a)；else error()；第3章练习：示例5，(b) a的语法的预测分析器递归配置：void l()if(look ah

4、ead=()| |(look ahead=a)selse error()；第3章练习：示例5，(b) a的语法的预测分析器递归：void l prime () if (look ahead=，)match(，)；s()；LP rime()；else if(lookahead=)return；else error()；第3章练习：示例6，已知语法生成如下：xy1 y2 y3 y4 y5y1a | y2b | y3c | y4d | y5e | FIRST(X)基于一种求FIRST(X)的算法。因为x Y1，Y2 b，所以X *bY3Y4Y5 Y1，Y2，Y3 c，所以X *cY4Y5 Y1，Y2，Y3，Y4 d，所以X *dY5 Y1，Y2，Y3，Y3章节练习：范例7，SA B | P Q x Ax y Bb c Pd P | Qa Q |想法：根据LL(1)语法的定义，first(ab)=first(a)=x first(pqx)=d，aPP |，其中PVN，V*不是空字符串。思考：牙齿问题实际上是要求证明左递归语法不是LL(1)语法。以LL(1)语法定义开始。非空，