用於LL解析的語法重構

Question

在一個簡單的示例中，我很困惑如何通過刪除左遞歸將此語法轉換爲LL語法。任何提示都是值得歡迎的。

G = { 
     A -> A a | A B | a 
     B -> b 
    } 

我通過應用this algorithm得到如下：

G = { 
     A -> a X 
     X -> e | A | B X 
     B -> b 
    } 

這似乎工作產生解析器一個C僞代碼：

void A() { 
    switch (token) { 
     case 'a' : next(); X(); break; 
    } 
} 

void X() { 
    switch (token) { 
     case 'e' : finish(); break; 
     case 'a' : A(); break; 
     case 'b' : B(); X(); break; 
    } 
} 

void B() { 
    next(); 
} 

，並生成解析樹換字：aabab：

A ---+ 
| | 
a X 
    | 
    A ---+ 
    | | 
    a X ---+ 
      | | 
      B X 
      | | 
      b A ---+ 
       | | 
       a X ---+ 
        | | 
        B X 
        | | 
        b e 

好吧，我只是不知道這是否是正確的......

Answer 1

首先，你的語法似乎接受了由單一b S離開a Xi的序列，因此沒有2 b走到了一起。 （aaa...abaaaaa...abaaa...a）這應該相當於類似於：

Q -> P | P b P 
P -> a | a P