用于LL解析的语法重构

在一个简单的示例中，我很困惑如何通过删除左递归将此语法转换为LL语法。任何提示都是值得欢迎的。用于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

好吧，我只是不知道这是否是正确的......

来源

2012-10-10 vmassuchetto

首先，你的语法似乎接受了由单一b S离开a Xi的序列，因此没有2 b走到了一起。（aaa...abaaaaa...abaaa...a）这应该相当于类似于：

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

来源

2012-10-10 13:11:15 Vlad

对不起，不说了。我需要维护原文的一些结构。看看编辑。 = D – vmassuchetto

@Vinicius：好的，你提出的语法（第二个）似乎是正确的。伪代码中唯一的变化是（1）开关中的缺省情况，产生一个错误，（2）''e''应该不是一个字符，而是EOF或者任何标记输入流结束的地方。 – Vlad

用于LL解析的语法重构

回答

相关问题