parsing - 为什么这不是语法 LL(1)

Question

我的任务是将此语法转换为 LL(1)

E → E+E | E-E | E*E | E/E | E^E | -E | (E)| id | num

所以对于第一步，我消除了歧义并得到了这个:

E → E+T | E-T | T 
T → T*P | T/P | P
P → P ^ F | F
F → id | num | -E | (E)

然后我消除了左递归并得到了这个:

E  → TE'
E' → +TE' | -TE' | ɛ
T  → PT'
T' → *PT' | /PT' | ɛ
P  → FP'
P' → ^FP' | ɛ
F  → id | num | -E | (E)

当我将其放入 JFLAP 并单击“构建 LL(1) 解析表”时，我收到警告，上面的语法不是 LL(1)。

为什么这个文法不是LL(1)，我需要改成LL(1)。

Answer 1

你的语法仍然有歧义，所以它不可能是 LL(1)。

此产生式 F → -E 可以在不应出现的级别(一元运算符)中混合具有较低优先级运算符的表达式。

注意 id + - id + id 有两个派生树。

你不应该在那里使用E，而是一个代表原子值的符号。你可以替换

F → id | num | -E | (E)

与

F → -A | A
A → id | num | (E)

或 F → -F | A 如果你想允许多个一元负号。