1

所以我正在做一个解析器，我更喜欢灵活性而不是速度，我希望它易于编写语法，例如没有棘手的变通规则（解决冲突的假规则等，就像你在 yacc/bison 等中必须做的那样.)

有一个手动编码的 Lexer，带有一组固定的标记（例如 PLUS、DECIMAL、STRING_LIT、NAME 等），现在有三种类型的规则：

  • TokenRule：匹配特定的令牌
  • SequenceRule：匹配一个有序的规则列表
  • GroupRule：匹配列表中的任何规则

例如，假设我们有 TokenRule 'varAccess'，它匹配令牌 NAME（大致 /[A-Za-z][A-Za-z0-9_]*/）和 SequenceRule 'assignment'，它匹配 [表达式，TokenRule(PLUS)，表达式]。

表达式是与“assignment”或“varAccess”匹配的 GroupRule（我正在测试的实际规则集更完整，但对于示例来说就是这样）

但现在假设我要解析

var1 = var2

假设解析器以规则表达式开头（定义它们的顺序无关紧要 - 稍后将解决优先级）。假设 GroupRule 表达式将首先尝试“赋值”。然后由于“表达式”是“赋值”中要匹配的第一个规则，它会尝试再次解析表达式，依此类推，直到堆栈被填满并且计算机 - 正如预期的那样 - 只是在一个闪亮的段错误中放弃。

所以我所做的是 - SequenceRules 将自己作为“叶子”添加到他们的第一条规则中，并成为非根规则。根规则是解析器首先尝试的规则。当其中一个被应用并匹配时，它会尝试一个接一个地子应用它的每个叶子，直到一个匹配。然后它尝试匹配叶子的叶子，依此类推，直到不再匹配。

这样它就可以解析表达式

var1 = var2 = var3 = var4

恰到好处 =) 现在有趣的东西。这段代码：

var1 = (var2 + var3)

不会解析。发生的情况是，var1 被解析（varAccess），assign 被子应用，它寻找一个表达式，尝试'括号'，开始，在'（'之后寻找一个表达式，找到 var2，然后在'+ ' 因为它期待一个 ')'。

为什么它不匹配 'var2 + var3' ？（是的，在你问之前有一个“添加”SequenceRule）。因为“添加”不是根规则（以避免使用 parse-expression-beginning-with-expression-etc. 进行无限递归），并且叶子没有在 SequenceRules 中测试，否则它会解析类似

reader readLine() println()

作为

reader (readLine() println())

（例如，'1 = 3' 是 add 期望的表达式，varAccess a 的叶子）

而我们希望它是左关联的，例如解析为

(reader readLine()) println()

所以无论如何，现在我们遇到了这个问题，我们应该能够在 SequenceRules 中解析诸如“1 + 2”之类的表达式。该怎么办？添加一个特殊情况，即当 SequenceRules 以 TokenRule 开头时，它包含的 GroupRules 会被测试是否为叶子？在那个特定的例子之外，这甚至有意义吗？或者是否应该能够在 SequenceRule 的每个元素中指定是否应该对其进行叶子测试？告诉我你的想法（除了扔掉整个系统 - 无论如何这可能会在几个月内发生）

PS：拜托，拜托，请不要回答诸如“去阅读这本 400 页的书，否则您甚至不值得我们花时间”之类的问题，如果您觉得有必要 - 请克制自己并在 reddit 上大肆抨击。好的？提前致谢。

4

2 回答 2

2

LL(k) 解析器（自上而下的递归，无论是自动的还是手工编写的）需要重构您的语法以避免左递归，并且通常需要特殊的前瞻规范（例如 ANTLR）才能处理 k-token 前瞻。由于语法很复杂，您可以通过实验来发现 k，这正是您希望避免的事情。

YACC/LALR(1) 语法避免了左递归问题，这是向前迈出的一大步。坏消息是没有真正的编程语言（除了 Wirth 的原始 PASCAL）是 LALR(1)。因此，您可以破解您的语法以将其从 LR(k) 更改为 LALR(1)，再次迫使您遭受暴露奇怪案例的实验，并破解语法简化逻辑以尝试在解析器处理 K-lookaheads生成器（YACC，BISON，......你的名字）产生 1-lookahead 解析器。

GLR 解析器 ( http://en.wikipedia.org/wiki/GLR_parser ) 可以让您避免几乎所有这些废话。如果您可以编写上下文无关解析器，那么在大多数实际情况下，GLR 解析器将无需进一步努力即可对其进行解析。当您尝试编写任意语法时，这是一个巨大的解脱。一个非常好的 GLR 解析器会直接生成一棵树。

BISON 已经得到了增强，可以进行 GLR 解析。您仍然需要编写复杂的逻辑来生成所需的 AST，并且您必须担心如何处理失败的解析器以及清理/删除它们对应的（失败的）树。DMS Software Reengineering Tookit为任何上下文无关语法提供标准 GLR 解析器，并自动构建 AST，无需您付出任何额外的努力；歧义树是自动构建的，可以通过后解析语义分析来清理。我们已经使用它来定义 30 多种语言语法，包括 C，包括 C++（被广泛认为难以解析 [并且几乎不可能用 YACC 解析]，但对于真正的 GLR 来说很简单）；请参阅基于 DMS 的C++ 前端解析器和 AST 构建器。

底线：如果您想以直接的方式编写语法规则，并让解析器处理它们，请使用 GLR 解析技术。野牛几乎可以工作。DM确实有效。

于 2009-10-03T04:26:24.620 回答
0

我最喜欢的解析技术是从 PEG 语法规范创建递归下降 (RD) 解析器。它们通常非常快速、简单且灵活。一个很好的优势是您不必担心单独的标记化通道，并且不存在将语法压缩成某种 LALR 形式的问题。[此处][1] 列出了一些 PEG 库。

抱歉，我知道这属于丢弃系统，但是您的问题几乎没有解决问题并切换到 PEG RD 解析器，现在只会消除您的头痛。

于 2009-10-15T03:06:56.297 回答