程式語言文法

<id> → A | B | C

<assign> → <id> = <exp>

<exp> → <id> * <exp>
| <id> + <exp>
| ( <exp> )
| <id>

**************************

<S> → <A><B><C>
<A> → a<A> | a
<B> → b<B> | b
<C> → c<C> | c

可展開得到 a^ib^jc^k , i,j,k >=1

**************************
文法：
<exp> → <exp> + <exp> | <id>
<id> → a

口訣：只要看到 <x> → <x> + <x> 這個 pattern 就是模糊文法!!

模糊文法定義：若一語言可接受的一個句子，依照語言文法產生的剖析樹
可產生兩個或以上的剖析樹，則稱此文法為模糊文法。

原因：當計算 A+A+A 時，
可以有兩種 parse tree 分別是：(A+A)+A 與 A+(A+A)
因為 <exp> → <exp> + <exp> 表示展開前面/後面 都允許

**************************


思考 <exp> → <exp> + <term> 與
<exp> → <term> + <exp> 差異點
假設 <term> → A | B | C

這兩個不同的式子，決定了左結合或右結合，
以 A+B+C 例子來看，上式呈現 (A+B)+C 而下式呈現 A+(B+C)
先被展開的，會較晚計算，位於 parse tree 上端
較晚展開的，會較先計算，位於 parse tree 底端

在 <exp> + <term> 式子中，位於右手邊的 term 表示先被展開，所以較晚計算
也就是說 A+B+C 中，右手邊的 C 會在 parse tree 上端，最晚計算。
此一結果形成「左結合」的優先權。

同理在 <term> + <exp> 中，位於左邊的 term 先被展開，右邊的 exp 較晚展開
所以在 A+B+C 例子中，會呈現 A+(B+C) 的現象，左邊的 A 先展開，較晚算。

底下這個文法，可以滿足優先權 ( 括號 > 乘法 > 加法 )

<exp> → <exp> + <term> | <term> (想一想 A+B+C 要怎麼算: (A+B)+C )
<term> → <term> * <factor> | <factor> (想一下 A*B*C 要怎麼算: (A*B)*C )
<factor> → ( <exp> ) | <id>
<id> → a | b | c


有一點要小心，如果將乘號與括號放在同個式中，
表示優先權 [括號] 等於 [乘號] 這是不對的。
像下面這個例子來說，乘號與括號的優先權會是一樣的。

<term> → <term> * <factor> | ( <factor> )

所以要分層步進，加號 → 乘號 → 括號
別忘了老原則，愈先展開者位在 parse tree 的上層，會愈晚算。

***************

下列的 E 是左遞迴，這個東西不好，因為不曉得他要展開幾次

E → E + T | T

展開的結果可以是：
(E)+T
(E+T)+T
(E+T+T)+T
(E+T+T+T)+T


實際的式子中不會有括號，這邊是為了標記出 "E" 可延伸的變化。

可以想像，光是 E 去做遞迴展開，這個式子就會很長。問題是他會有多長？

換個角度想：整個式子最後展開，得到的結果是 T+T+T+T+T (很多 T 加相加)

如果問 E 要展到何時才會停？ 答案是 " E + T " 中的 E 如果展成 T 了

那麼式子就宣告結束。所以很簡單：這個 E 最終會變成 T 的。

所以我們可以這樣看事情 E → T (+T) (+T) (+T) (+T) 括號是為了分組而寫出來的

試著用下面的邏輯表達這個結果：

E → TE' | T /* 第一個 T 打頭陣，後面 (+T) 則用 E' 帶出來 */
E' → +T /* 這邊的 E' 只能展出一個 +T */

這樣就可以創造出 "T+T" 的結果了，更重要的是排除了左因子。

現在把威力加強一點，讓這個文法可以展出 T+T+T+T 這麼長的東西

E → TE' | T
E' → +TE' /* 遞迴用 E' 去產生很多組 (+T) (+T)... 的效果 */


***************************

左因子 - 文法產生規則不可以有「左因子」 下面的例子中 α 就是左因子

A → αB | αC

因為在判斷要選用何條規則時，因為都是α開頭，會不知道該選何者。

舉個例子：

<stmt> → if <exp> then <stmt> else <stmt> |
if <exp> then <stmt>

(想法：數學提公因式，應該會吧 A= PQ + PR = P(Q+R) )

<stmt> → if <exp> then <stmt> <term>
<term> → else <stmt> | ε