1、編譯原理練習課，中國海洋大學(xué)計算機系加林，第三章練習：例1，下面的異議語法描述了命題計算公式的語法。相當?shù)姆且蓡柗⊿ 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相當?shù)姆且蓡柗⊿ and S | (e) | p | q生成的語法SaSbS | bSaS | (a)abab中兩個茄子的最左邊推導(dǎo)：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)最右側(cè)的派生(與第二個最左側(cè)的派生相對應(yīng)的最右側(cè)的派生)s RM asbs RM asbasbs RM ASB RM as Bab RM abab(c)相對應(yīng)的分析樹：注意：分析樹沒有箭頭。(d)牙齒語法生成的語言：具有相同a，b數(shù)的字符串集；第3章練習：示例3，語法：R R | R | RR | R* | (R) | a | b (b)構(gòu)造等效的鄭智薰異議語法分析語法：SabS | bS | (b)a和B的數(shù)量相同的字符串1:S A b| B A | A S | B A B S | A B B(B)繼續(xù)異議語法2:s

3、a SBS | bsas | aabbabas(B)異議語法1的結(jié)論：S A | B (a，B數(shù)不同的字符串，起始符號)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)的語法結(jié)構(gòu)預(yù)測分析器非迭代：(match()；else if(lookahead=a)match(a)；else error()；第3章練習：示例5，(b) a的語法的預(yù)測分析器遞歸配置：void l()if(look ah

4、ead=()| |(look ahead=a)selse error()；第3章練習：示例5，(b) a的語法的預(yù)測分析器遞歸：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章節(jié)練習：范例7，SA B | P Q x Ax y Bb c Pd P | Qa Q |想法：根據(jù)LL(1)語法的定義，first(ab)=first(a)=x first(pqx)=d，aPP |，其中PVN，V*不是空字符串。思考：牙齒問題實際上是要求證明左遞歸語法不是LL(1)語法。以LL(1)語法定義開始。非空，