使用 %glr-parser 和 %merge 规则减少错误的野牛

Question

目前我正在尝试为 VHDL 构建一个解析器，它有一些 C++-Parsers 必须面对的问题。 VHDL 的上下文无关文法产生一个解析森林而不是单个解析树，因为它是关于函数调用和数组订阅的歧义

foo := fun(3) + arr(5);

只有当解析器会携带一个分层的、类型感知的符号 table 它会用来即时解决歧义。

我不想这样做，因为对于像前面提到过，解析森林不会呈指数增长，但是相当线性取决于函数调用的数量和数组订阅。

（除了，当然，有人会用这样的语句来折磨解析器）

foo := fun(fun(fun(fun(fun(4)))));

由于 bison 强制用户只创建一个分析树，我使用 %merge 属性递归地收集所有子树并且在单例中的所谓 AMBIG 节点下添加了那些子树 AST.

结果看起来像 this。

为了生成以上内容，我解析了令牌流 "I=I(N);"。我在 parse.y 文件中使用的语法的实质是收集如下。它试图模仿 VHDL 的模棱两可的部分：

start: prog
;

/* I cut out every semantic action to make this
   text more readable */
prog: assignment ';'
| prog assignment ';'
;

assignment: 'I' '=' expression
;

expression: function_call   %merge <stmtmerge2>
| array_indexing            %merge <stmtmerge2>
| 'N'
;

function_call: 'I' '(' expression ')'
| 'I'
;

array_indexing: function_call '(' expression ')'   %merge <stmtmerge>
| 'I' '(' expression ')'                           %merge <stmtmerge>
;

The whole sourcecode can be read at this github repository.

现在，让我们开始讨论实际问题。正如您在上面生成的解析树中看到的那样，节点 FCALL1 和 ARRIDX1 指的是同一个单个节点 EXPR1 又引用 N1 两次。

无论如何，这不应该发生，我也没有知道为什么。相反应该有路径

FCALL1 -> EXPR2 -> N2
ARRIDX1 -> EXPR1 -> N1

你知道为什么 bison 重复使用前面提到的节点？

我还在官方 gnu 邮件上写了错误报告野牛名单，虽然没有回复这一点。不幸的是，由于新计算器的限制用户，我不能向这个错误报告提供 no link...

Answer 1

该行为是预期的。

expression 可以明确地减少，并且包括该值的两个可能的模糊减少都使用减少的值。请记住，与 LR 一样，GLR 是一个从左到右的解析器。执行缩减操作时，所有子缩减都已经发生。效果与在右侧使用终端没有区别；终端不会被人为复制以在使用它的模糊产品中产生不同的实例。

对于大多数人来说，这将是一个功能而不是一个错误，我的意思不是开玩笑。没有图结构堆栈，GLR 具有指数运行时间。如果你真的想在合并解析树时对共享 AST 节点进行深拷贝，你将不得不自己做，但我建议你找到一种方法来利用解析森林实际上是一个有向无环的事实图而不是树；您可能可以利用缺少重复的优势。

使用 %glr-parser 和 %merge 规则减少错误的野牛

Faulty bison reduction using %glr-parser and %merge rules

parsing

bison

text-parsing

glr