问题标签 [recursive-descent]

我有一个非常标准的递归下降解析器。该算法很简单：每个函数从 a 中读取字符，stream然后返回FAIL或调用后续解析函数（由相应的语法规则指定）：

我想解决我stream一次没有完整的情况 - 我异步获取它的部分。因此，我需要的是“可中断性”的特性——我必须能够保存解析器的状态，然后从那时起继续。

遗憾的是，这是嵌套函数调用不可能做到的一件事，因为解析器的所有状态都“存储”在调用堆栈中（按照函数的顺序和它们的局部变量）。

所以我必须以parse*不同的方式构造函数。

我使用的语言是JavaScript。

有人可以指出我如何进行的任何想法吗？

编辑：

• 我似乎很清楚我需要某种状态机。我无法围绕生成器或延续传递风格，在我看来，在保存状态和恢复时有很多小故障。对我来说，我能想到的最清晰的途径是将嵌套调用转换为某种堆栈，将局部变量重写为存储在堆栈项中的一些哈希图，并以不同的线性方式构造解析代码，这样我就可以轻松地“转到“到某个状态。

• 我看到的子问题之一可能是：由于我没有完整的stream，我认为我必须尝试多个路径并存储所有部分解析的尝试。例如，如果语法说a = b | cthenb可能太长以至于它没有完全在stream. 所以我不能在解析中“挂起” b，我必须同时尝试并保存部分计算。我对吗？

递归下降解析器有哪些好的例子？从开源项目或特别好的示例代码中说。

我特别希望比较有和没有回溯的实现。

首选 C、C++、Java、Javascript 或 Python 中的示例。

我知道有解析器生成器可以生成各种解析器。目前，我主要有兴趣了解更多关于手写递归下降解析器的知识。

好吧，我不确定我应该如何使用递归下降解析来编写一个函数来解析如下所示的语法。实际上，我不确定我是否做得对...

BNF：

伪代码：

我正在这样做（没有检查以确定它是否是 A，但我觉得它有问题）：

我正在构建一个简单的语言解析器，并且遇到了较低优先级前缀表达式的问题。这是一个示例语法：

NOT但是，如果将其用作更高优先级中缀运算符的 RHS，则此语法不适用于 ，即：

这是由于==操作员在 RHS 上需要 E1，这不能是 NOT 操作。

我不确定表达这种语法的正确方法？是否仍然可以使用这种简单的递归下降方法，或者我需要转向更具特色的算法（调车场或优先攀登）。

注意：这是递归下降优先级解析缺少前缀表达式的更详细版本

我正在构建一个简单的语言解析器，并且遇到了较低优先级前缀表达式的问题。这是一个示例语法：

但是，如果它用作更高优先级中缀运算符的 RHS，则此语法不适用于 NOT，即：

这是由于 RHS 上需要 == 运算符E3，它不能是“NOT”操作。

我不确定表达这种语法的正确方法？是否仍然可以使用这种简单的递归下降方法，或者我需要转向更具特色的算法（调车场或优先攀登）。

以下是一些需要正确解析的示例：

• 输入true == 1 < 2,输出==(true, <(1, 2))
• 输入1 < 2 == true,输出==(<(1, 2), true)
• 输入NOT true == false,输出NOT(==(true, false))
• 输入true == NOT false，输出==(true, NOT(false))**不起作用
• 输入true < NOT false，输出<(true, NOT(false))**不起作用

我已尝试更改级别E4, E3, 并在中缀表达式的 RHS 上E2使用，如递归下降优先级解析缺少的前缀表达式（即,等）中所建议的那样。然而，这打破了这些级别之间的优先级，即错误地<(==(true, 1), 2)`。E5E3 '==' E5E3 '<' E5true == 1 < 2parsed as

我正在尝试编写一个没有回溯的递归下降解析器，用于像这样的 EBNF：

在哪里

• <a> = 非终端

• 小写字符串 = 标识符

• [term-in-brackets] = term-in-brackets 是可选的

• a|b 是 a 和 b 之间通常互斥的选择。

现在，我只关心右手边。

按照http://en.wikipedia.org/wiki/Recursive_descent_parser中的示例，我最终得到了以下过程（上述评论中的 GNU bison 语法规则）：

它似乎有效，但我的期望是每个程序都会与相应的规则密切对应。你会注意到 term() 没有。

我的问题是：在编写程序之前，语法是否需要更多的转换？

作为真实语言解析器的简化子问题，我正在尝试为虚构语言的表达式实现解析器，该语言看起来类似于标准命令式语言（如 Python、JavaScript 等）。它的语法具有以下结构：

• 整数
• 标识符 ( [a-zA-Z]+)
• +带和*和括号的算术表达式
• 结构访问.（例如foo.bar.buz）
• 元组（例如(1, foo, bar.buz)）（消除歧义，一个元组写成(x,)）
• 功能应用程序（例如foo(1, bar, buz())）
• 函数是第一类的，因此它们也可以从其他函数返回并直接应用（例如foo()()是合法的，因为foo()可能返回一个函数）

所以这种语言的一个相当复杂的程序是

关联性应该是

我目前正在使用非常好的uu-parsinglib应用解析器组合库。

第一个问题显然是直观的表达式语法 (expr -> identifier | number | expr * expr | expr + expr | (expr)是左递归的。但我可以使用pChainl组合器解决这个问题（参见parseExpr下面的示例）。

剩下的问题（因此这个问题）是函数应用与从其他函数返回的函数（f()()）。同样，语法是左递归的expr -> fun-call | ...; fun-call -> expr ( parameter-list )。有什么想法可以优雅地解决这个问题uu-parsinglib吗？（我猜这个问题应该直接适用于parsec,attoparsec和其他解析器组合器）。

请参阅下面我当前版本的程序。它运行良好，但功能应用程序仅在标识符上工作以删除左递归：

我正在学习递归体面解析，并提出了一些我认为算法不起作用的场景。其中之一是，考虑到这个简单的语法：

S→E；
E → 标识 | 身份证+身份证

那么这个字符串id + id;在这个语法的语言中是有效的。但是，如果我们执行递归下降算法，它会从S到E然后到id，这是第一个匹配的终端。现在输入在+，我们又回到了S尝试匹配;然后失败的地方；但没有其他规则可供选择S。

我认为语法没有歧义，因为语言中只有 2 个字符串id;和id + id;，每个字符串都有一个唯一的解析树。这里的一般问题是非终结符具有相同前缀的产生式，并且可能会做出在递归中更深层次匹配的选择，但会为更浅层次创建无效输入。

我已经阅读了诸如左递归之类的递归下降的典型问题，但在任何地方都没有发现上述问题。那么这真的是一个问题还是我错过了什么？

我从书中找到了一个权威的答案，Parsing Techniques: A Practical Guide p.182-188它将上述方法归类为朴素递归体面，并强调了同样的问题。有两种解决方案始终适用于没有前瞻的一般情况（因为通常所需的前瞻长度随着前缀长度的增加而增加）：需要使用延续的穷举递归下降和广度优先递归下降。

实现递归下降解析器是需要的第一个和后续集吗？如果是这样，您是否仍然可以在第一个和以下给出非唯一性的情况下构建递归下降？我很难区分递归下降和 ll(1) 解析。

谢谢。

我试图围绕如何使用递归下降解析器处理 C 风格的多行注释 (/* */)。因为这些评论可以出现在任何地方，你如何解释它们？例如，假设您正在将一个句子解析为word标记，如果一个单词中有注释，我们该怎么办？

前任。

这是一句话=word word word word

对比

这是一个 sen/*sible*/tence = ???

谢谢！