包含遞迴的生成規則

寫遞迴的文法在生成文法中也是稀鬆平常的事。底下是在四則運算加上代表優先順序的括號的文法生成規則：

expr = mul ("+" mul | "-"
 mul)*
mul  = term ("*" term | "/" term)*
term = num | "(" expr ")"

上述的文法和之前的文法的差異，在於以前我們放num的位置被term，也就是num或是 "(" expr ")"取代了。也就是說，在新的文法中，被包含在小括號中的式子和至今為止的單一數值是同等的「結合方式」。我們用一個範例來看。

底下是1*2的語法樹：

1*2的語法樹

接下來的樹是1*(2+3)的語法樹：

1*(2+3)的語法樹

比較兩個樹，會發現只有mul的右子樹的term展開是不一樣的。樹裡充份表現了在樹展開的最尾端出現的term，可以展開為一個數值，也可以展開成被括號包住的任意式子的這條規則。像這樣，把括號的優先順序用很簡單的生成規則來表示，是不是覺得有點感動呢？