語法解析樹？

Question

這個問題是在我的CS作業，我不知道該怎麼做。

考慮語法

S ← (L) 
S ← a 
L ← L , S 
L ← S 

畫一個解析樹句子(a , (a , a))

我試過結構以下，我結束了(L,(L,L))似乎並非是正確的，但。有誰能把我推向正確的方向嗎？

Answer 1

這裏是你以後的部分：

現在你做的工作:)

Answer 2

看句子(a, (a, a))。哪個右邊（RHS）可以匹配？只有第一個，S ← (L)。所以你的樹的根將是一個S - 有三個孩子的節點：一個(-node，一個L-節點和一個)-node。

現在您需要弄清楚L節點的孩子是什麼，他們必須匹配剩餘的輸入：a,(a,a)。所以看看LHS上有L的規則。那些規則中哪一個的RHS可以匹配a,(a,a)？

Answer 3

爲(a,(a,a))的解析樹是從一個最左推導得到的休息(a,(a,a))：

S => (L)  [S -> (L)] 
    => (L,S)  [L -> L,S] 
    => (S,S)  [L -> S ] 
    => (a,S)  [S -> a ] 
    => (a,(L)) [S -> (L)] 
    => (a,(L,S)) [L -> L,S] 
    => (a,(S,S)) [L -> S ] 
    => (a,(a,S)) [S -> a ] 
    => (a,(a,a)) [S -> a ] 

您解析樹的根是S。對於派生中的每個非終結符號的重寫，在分析樹中繪製適當的節點。另外，你的語法不是最優的，除此之外，還包含鏈式規則。刪除它們將防止必須從L派生S以推導出a。