parsing - 解析表大小（自下而上）

Question

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

我想问你，代表歧义语法的解析表（自底向上解析器）的大小总是小于对应的明确语法的解析表的大小是否总是正确的？显然假设冲突得到了正确解决。

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

Answer 1

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

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

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

同时，歧义文法在 SLR(1) 自动机中有 6 个状态。

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

因此，歧义语法的表大小大于明确语法的表大小。

对于该a+语言的两种语法也是如此：S -> a S | a和S -> S S | S S S | a。