-2

我正在用 Bison 为一种具有以下结构的语言编写解析器，其中包括：

  • 自发货：[ identifier arguments]
  • 调度：[ expression。identifier arguments]
  • 字符串切片：expression[ expression, expression] - 类似于 Python。

arguments是一个以逗号分隔的表达式列表，也可以为空。以上所有内容本身也是表达方式。我的问题是我不确定如何解析两者[method [other_method]]，[someString[idx1, idx2].toInt]或者是否可以使用 LALR(1) 解析器来完成。

更准确地说，让我们看下面的例子：（用方法的结果[a[b]]调用方法）。当它达到状态时。（前瞻是第二个），它不知道是减少（已经减少到），因为可能会出现类似的东西（它本身可以减少到并继续上面的第二个构造）还是保留它（并转移它），因为后面会出现一个列表（例如在这种情况下）。ab[a[b]][aidentifierexpressiona[b,c]expressionidentifierarguments[b]

这种移位/减少冲突是由于我表达这种语法的方式造成的，还是不可能用 LALR(1) 解析器解析所有这些结构？

而且，一个更普遍的问题是，如何证明一种语言可以/不能被特定类型的解析器解析？

4

1 回答 1

2

假设您的语法是明确的（您描述的部分似乎是），那么您最好的选择是指定一个%glr-parser. 由于在大多数情况下，仅在几个标记之后就会强制执行正确的解析，因此开销不应该是明显的，而且优点是您不需要使语法或 AST 的构造复杂化。

一个缺点是，bison 无法验证语法是否明确——一般来说，这是不可能的——而且不容易证明。如果事实证明某些输入不明确，GLR 解析器将产生错误，因此良好的测试套件很重要。

证明该语言不是 LR(1) 会很棘手，我怀疑这是不可能的，因为该语言可能可以被LALR(1) 解析器识别。（不过，如果不看整个语法就不可能说出来。）但是解析（在 CS 理论之外）需要创建一个正确的解析树才能有用，并且生成 LR 语法所需的那种修改也会修改 AST ，需要解析后修复。创建正确 AST 的困难源于两者之间的优先级差异

a[b[c],d]

和

[a[b[c],d]]

在第一种（子集）情况下，b绑定到它的参数列表[c]并且逗号具有较低的优先级；最后，b[c]并且d是切片的兄弟姐妹。在第二种情况下（方法调用），逗号是参数列表的一部分，并且比方法应用程序绑定得更紧密；b， [c]并且d是方法应用程序中的兄弟姐妹。d但是在任意长的输入（因为可以是任何表达式）之前，您无法确定解析树的形状。

由于“优先级”没有正式定义，因此这一切都有些手忙脚乱，并且有一些技巧可以使调整树成为可能。由于 LR 属性并不是真正可组合的，因此确实可以提供更严格的分析。但无论如何，GLR 解析器可能是最简单、最健壮的解决方案。

供将来参考的一点：CFG 不仅仅是一种编程工具；它们还有助于清楚地传达所讨论的语法。一般来说，如果你想描述你的语言，你最好使用清晰的 CFG，而不是试图非正式地描述。当然，有意义的非终结符名称会有所帮助，并且一些示例永远不会受到伤害，但是语法的本质在于正式的描述和省略，这使得其他人更难“提供帮助”。

于 2016-11-07T18:11:22.813 回答