解析 table 大小(自下而上)

Parsing table size (bottom-up)

我看到了为歧义语法和明确语法(相同语言)构造的解析表大小之间的比较。为模棱两可而创建的那个要小得多。使用的解析器是 SLR(1)。

请问,代表歧义语法的解析表(自底向上解析器)的大小是否总是小于对应的无歧义语法的解析表?显然假设冲突得到正确解决。

我做了一些研究,但我找不到任何证据或这个问题的答案。

情况并非总是如此。考虑平衡括号语言的经典语法

明确的在SLR(1)自动机中有5个状态。

S -> '(' S ')' S | \epsilon

同时,二义文法在SLR(1)自动机中有6种状态。

S -> S S | '(' S ')' | \epsilon 

因此,歧义语法的 table 大小大于无歧义语法的 table 大小。

a+ 语言的两个语法也是如此:S -> a S | aS -> S S | S S S | a