grammar - 用于 LL 解析的语法重构

Question

在一个简单的例子中，我很困惑如何通过删除左递归将这个语法变成 LL 语法。欢迎任何提示。

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

通过应用此算法，我得到以下信息：

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

首先，您的语法似乎接受a由单个 s 分隔的s 序列b，因此没有 2b组合在一起。( aaa...abaaaaa...abaaa...a) 这应该相当于：

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