LL(1) 解析 Table 错误

Question

我从这个语法开始

E -> E + T | T
T -> id | id[] | id[X]
X -> E, E | E

很明显第一条规则有左递归，所以去掉它得到下面的

E  -> TE'
E' -> +TE' | epsilon
T  -> id | id[] | id[X]
X  -> E, E | E

我从这里生成 FIRST 和 FOLLOW 集（id 是单个终端）。

FIRST(TE') = FIRST(E, E) = FIRST(E) = {id}
FIRST(+TE') = {+}
FIRST(epsilon = {epsilon}
FIRST(id) = FIRST(id[]) = FIRST(id[X]) = {id}

FOLLOW(E) = {$}
FOLLOW(E') = {$}
FOLLOW(T) = {$}
FOLLOW(X) = {]}

但是当我尝试构建解析 table 时，我最终得到了几个单元格的多个值。

    |  id               |  +     | [  |  ]  |  ,  |  $  |
----+-------------------+--------+----------+-----+-----+
E   |  TE'              |        |    |     |     |     |
E'  |                   |  +TE'  |    |     |     |  ε  |
T   |id or id[] or id[X]|        |    |     |     |     |
X   |E, E or E          |        |    |     |     |     |

我错过了什么吗？如何纠正此问题以便我可以使用此语法解析 id + id[id + id, id[]]？

Answer 1

即使在删除左递归之后，您的语法也不是 LL(1)。这些作品有问题：

T -> id | id[] | id[X]
X -> E , E | E

尝试应用以下转换：

A -> ab_1 | ... | ab_n  ~~~~~~> A  -> aA'
                                A' -> b_1 | ... | b_n

你的情况是：

T  -> id T'
T' -> [] | [X] | epsilon

X  -> EX'
X' -> , E | epsilon

但是T'还需要再应用一次转换：

T  -> id T'
T' -> [ T" | epsilon
T" -> ] | X ]

完整语法：

E  -> TE'
E' -> +TE' | epsilon
T  -> id T'
T' -> [ T" | epsilon
T" -> ] | X ]
X  -> EX'
X' -> , E | epsilon

此外，您应该按照以下方式进行操作：

1) 首先计算所有非终结符。

2) 计算所有非终结符的 FOLLOW。

3) 为所有产品计算 SELECT。请记住，一个非终结符的 SELECT 集应该是不相交的。

LL(1) 解析 Table 错误

LL(1) Parsing Table Error

compiler-construction

parsing

computer-science