編譯原理提取左公共因子例題

⑴ 編譯原理 設文法G[S] 求答案！

1. ·消除左遞歸 S→aAS'|∧aAS'
   S'→VaAS'|ε

   對A的產生式提取左因子 A→∧aA' A'→A|ε

2. · 非終結符合 First Follow

S a∧ #

S』 V ε #

A ∧ #

A『 ∧ #

Select（S→aAS'）=a

Select(S→∧aAS')=∧

Select(S'→VaAS')=V

Select(S'→ε)=#

Select(A→∧aA')=∧

Select(A'→A)=∧

Select(A'→ε)=#

符合LL（1）文法

a ∧ V #

S S→aAS' S→∧aAS'

S' S'→VaAS' S'→ε

A A→∧aA'

A' A'→A A'→ε

⑵ 消除左遞歸及提取左公因子

如果一個文法中有一個非終禪扮結符號A使得對某個串α存在一個推導A=》Aα，那麼這個文法就是左遞歸的。遞歸分為立即左遞歸和非立即左遞歸。立即左遞歸單步即可看出來，非立即左遞歸
舉個例子：

消除立即左遞歸只需要遵循以下規律進行轉換就ok。

立即左遞歸：

非立即左遞歸：

和數學中的公因子含義相同，就是公共的因子，而左公因子就是最左邊的公因子。

例如：

可以看出前n項擁有一個共同的左公因念信子：a，所以仔襲輪可以把他提取出來。

so easy啦

S → aB1|aB2|aB3|aB4|...|aBn|y
可以看出前n項擁有一個共同的左公因子：a，所以可以把他提取出來。

提取規則
so easy啦

S → aS'|y
S'→ B1|B2|B3|...|Bn

⑶ Ab-a=76,A等於多少b等於多少

兩個未知數一個方程，有無數解，信升但正整數解是有限的。左邊提取公因數a
a(b-1)=76
76=1×76=2×38=4×19
所以有6組盯宏正整數解
a=1,2,4,19,38,76
對應的b=77,39,20,5,3,2
一般把問題化為乘法來做。也可以用一個字母表示另外一個，如a=76/(b-1),b-1是76的因數。結果一樣凱坦冊的。

⑷ AB-A=76 A= B=

一個有兩衫啟凱個未知數的方程有無數個解，但正整數或喚解是有限的。左提取公因子AA（B-1）=7676=1×76=2×38=4×因此，存在六組正整數解a=1,2,4,19,38,76，對應於B=77,39,20,5,3,2。通常，該問題通過乘法解決。旁虧一個字母也可以用來表示另一個字母，例如，a=76/（B-1），B-1是76的因子。結果是相同的。

⑸ 編譯原理，改造文法使之變為LL（1）文法，怎麼提取最左公因式 如題：

S->aAb
A->edA|ε

這樣提取，

⑹ 設文法g(s) 判斷該文法是否為ll1文法

（1）
G'(S)
S->(L)|aT
T->+S|e
L->L,S|S
提取了 公共左因子
（2）
是LL(1)文法

⑺ 對下面文法先消除左遞歸，並提取左公共因子，再判斷其是否是LL（1）文法。 S->Aa|b A->SB B->ab

消除左遞歸
S->bS'
S'->BaS'|空
B->ab
提取公共左因子笑晌
沒有可提
文法不含左遞歸
每個非終結符只有一個產生式 候選首符集唯一
FOLLOW(S')=# 與其碰轎鋒首符集帆或相交為空
是LL(1)文法

⑻ 編譯原理回溯

消除回溯：提取左公因子a,（註：用e代表一補西農符號,就是反三的那個符號,在電腦上不知道怎麼打那個符號）
S→aS'|(L)
S'→S|e
消除左遞歸：
L→SL'
L'→,SL'|e (注意S前面有一個符號「,」)