1

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

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

只有当解析器携带一个分层的、类型感知的符号表时，这个赋值才能被明确地解析，它可以用来在运行中解决歧义。

我不想这样做，因为对于上述语句，解析森林不会呈指数增长，而是线性增长，具体取决于函数调用和数组订阅的数量。

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

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

由于野牛强制用户只创建一个解析树，我使用 %merge 属性递归地收集所有子树，并将这些子树添加到单例 AST 中所谓的 AMBIG 节点下。

结果看起来像这样。

为了产生上述内容，我解析了令牌流“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>
;

整个源代码可以在这个 github 存储库中阅读。

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

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

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

你知道为什么野牛会重用上述节点吗？

我还在官方 gnu 邮件列表上为 bison 写了一个错误报告，但没有回复这一点。不幸的是，由于对新的 stackoverflow 用户的限制，我无法提供此错误报告的链接...

4

1 回答 1

0

这种行为是意料之中的。

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

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

于 2016-04-07T17:37:53.100 回答