如何使用PEG.js为左关联运算符构建 AST（抽象语法树）？

我试图根据我在互联网上找到的信息编写一些代码，但我似乎犯了一个错误。

我编写的代码为大多数表达式生成了不正确的 AST。

表达

预期 AST

生成的 AST

代码

我非常感谢任何有关如何为左关联和右关联运算符构建 AST 的帮助或示例代码。

编辑：正如@Bergi 指出的那样，问题在于E2用作E1运算符列表其余部分的表达式而不是Value. 但是，Bergi 写的代码比我的要简单得多。

我通过编写解析 vCard 格式的解析器来学习 Parsley。我的问题是 vCard 格式的某些行可能会分成几行。使用 RFC 822 “折叠”技术的多行表示。也就是说，只要可能存在线性空白，CRLF 就会紧跟至少一个 LWSP 字符。我的解决方案是首先解析原始文本，在那里我可以找到换行符后跟空格并加入这些行。但是我无法让它工作：这是我最近的尝试：代码返回错误最后是：TypeError：不支持的操作数类型为+：'bool'和'str

我的同事 PaulS 问了我以下问题：

我正在为现有语言（SystemVerilog - IEEE 标准）编写解析器，并且规范中有一个规则，其结构与此类似：

问题是在解析以下合法字符串时：

anIdentifier成功匹配data_type（通过其标识符选项），这意味着 Grako 正在寻找另一个标识符，然后失败。然后它不会尝试在没有 data_type 部分的情况下进行解析。

我可以重写规则如下，

但我想知道是否：

1. 这是故意的
2. 如果有更好的语法？

这是一个 PEG-in-general 问题，还是一个工具（Grako）？

我想解析一个包含以下内容的文件：

所以现在解释这些部分（由于此处的标记，并未描述所有空格）：

• simple word是由空格分隔的一个或多个单词（短语）
• abbr -是字符串的固定部分（从不改变）
• 8- 可选号码
• .- 始终包括在内
• word, simple phrase, one another phrase- 一个或多个以逗号分隔的单词或短语
• - (- 固定部分，始终包括在内
• simply dummy text of the printing; Lorem Ipsum : "Lorem" - has been the industry's standard dummy text, ever since the 1500s!;- （可选）一个或多个短语;
• "It is a long established!"; "Sometimes by accident, sometimes on purpose (injected humour and the like)"; "sometimes on purpose"- （可选）一个或多个用引号"分隔的短语;
• ) This is the end of the line- 始终包括在内

在最坏的情况下，从句中没有短语，但这并不常见：应该有一个短语不加引号（phrase1type）或不加引号（phrase2type）。

所以这些短语是自然语言句子（所有可能的标点符号）......

但：

• 内部内容无关（即我不需要解析NLP含义中的Natural Language本身）
• 只需将其标记为 aphrase1或phrase2类型：
  • 那些没有和带引号的，即如果短语，它放在(and;或;and ;or ;and )or even between (and之间)加上引号，那么它是phrase2类型
  • 否则，如果短语开头或结尾没有引号，尽管它可能包含短语中的所有标记，但它是phrase1类型

由于为这样的输入编写正则表达式（PCRE）是一种矫枉过正的做法，所以我研究了解析方法（EBNF 或类似方法）。我最终得到了一个 PEG.js 解析器生成器。我创建了一个基本的语法变体（甚至不处理子句中具有不同短语的部分）：

或（区别仅在于" abbr -"和"_ "abbr" _ "-""）：

但即使是这种简单的语法也无法解析字符串的开头。错误是：

• Parse Error Expected [A-Za-z] but " " found.
• Parse Error Expected "abbr" but "-" found.
• 等等

所以看起来问题在于模棱两可："abbr"被term用作word令牌。尽管我定义了!(" abbr -")我认为有意义的规则，但word如果下一个子字符串不是那种类型，则只会消耗下一个令牌" abbr -"。

我没有找到任何很好的例子来解释 PEG.js 的以下表达式，在我看来，这似乎是上述问题的可能解决方案 [来自： http://pegjs.majda.cz/documentation ]：

• & expression
• ! expression
• $ expression
• & { predicate }
• ! { predicate }

TL;博士：

与 PEG.js 相关：

• 有没有应用规则的例子：

  • & expression
  • ! expression
  • $ expression
  • & { predicate }
  • ! { predicate }

一般问题：

• 用直观的模​​棱两可的语法处理如此复杂的字符串的可能方法是什么？这仍然不是自然语言，看起来它有一些正式的结构，只是有几个可选部分。其中一个想法是通过预处理来拆分字符串（借助正则表达式，在固定元素的位置，即“abbr -”“这是行尾”），然后为每个拆分部分创建一个单独的语法。但它似乎存在性能问题和可伸缩性问题（即 - 如果固定元素会发生一些变化 - 例如不再有-char 了。）

更新1：

我找到了解决匹配"abbr -"歧义问题的规则：

但结果看起来很奇怪：

如果删除谓词term = term:(word (!" abbr -" _? word))+：：

我期待的是：

或者至少：

表达式是分组的，那么为什么它被分成这么多嵌套级别，甚至undefined包含在输出中呢？是否有任何通用规则可以根据规则中的表达式折叠结果？

更新2：

我创建了语法，以便它可以根据需要进行解析，尽管我还没有确定这种语法创建的清晰过程：

它可以在 PEG.js 作者的网站上进行测试：[ http://pegjs.majda.cz/online]或在 PEG.js Web-IDE：[ http://peg.arcanis.fr/]

如果有人对前面的问题有答案（即消除语法歧义的一般方法，PEG.js 中可用表达式的示例）以及对语法本身的改进建议（我认为这与现在的理想语法相去甚远） ，我将不胜感激！

使用https://github.com/JetBrains/Grammar-Kit如何在没有左递归的情况下重写语法？

样本输入：

答案应维护节点包含 2/3 个子节点的解析树属性：

如果这已经被问到，我提前道歉。我有一种由语法定义的语言，我想知道人们如何为他们的自定义语法实施 Intellisense。这对我来说似乎是机械的；用户输入一些内容，然后输入到生成的解析器中，并提供关键字建议。我想解析将需要修改，以便它是增量的而不是一次性的，即生成的解析器。

我是这个领域的新手，所以欢迎任何提示。

我打算使用http://pegjs.majda.cz/但任何事情都可以。

我正在设计一种音乐编程语言并将其语法实现为 PEG 语法。解析过程最终变得相当复杂，所以看起来最简单的方法是定义几个单独的语法，并按顺序应用它们。到目前为止，我有三个语法：

1. 获取源文件的全部内容并去掉注释。
2. 获取源文件（已删除注释）并按仪器分隔。这导致成对的乐器名称/定义和由所述乐器“播放”的“音乐代码”。
3. 实际解析音乐代码并返回音乐“事件”的解析树。

在三个解析器中，#3 是迄今为止最复杂的。#1 和 #2 比较简单，每个只占用大约 10 行。另一方面，#3 变得越来越复杂，我实现的语法越多，目前是 33 行并且还在增加。

我突然想到，也许我可以将 3 个语法浓缩为一个？这可能会消除语法中的一点重复，甚至可能减少程序本身的代码行数，但我不确定它是否会使事情过于复杂。我粗略地尝试将它们组合起来，但很快发现它很困难，因为我似乎必须解决在每条规则中出现评论的可能性（如果我错了，请纠正我！）。事实上，我已经有一个可选空格的规则，我已将其包含在大多数音乐“事件”的定义中，以便在语法中允许空格的一些灵活性。我无法决定坚持多次解析并拥有多个单独的解析器是否更有意义，每个任务一个，

我的问题是：对于那些有构建 PEG 语法经验的人，您是否经常发现自己将大型语法分解为较小的子语法并多次传递您的输入？将所有内容都保存在一个语法中是否有任何优势（性能或其他方面）？

我定义了以下最小的 Peg.js 语法：

您可以在沙盒中尝试。

我本来希望匹配“A1”和“A123”（根据我对回溯如何工作的概念）。但事实并非如此：语法识别“A1”但不识别“A123”。

注意：我不是在寻找相关问题“如何将简单的语法转换为适用于 PEG.js 的东西”中的“颠倒你的术语的顺序”的建议（预期为“a”，但找到了“a”）。相反，我希望了解我所看到的行为，以及为什么 Peg.js 的回溯不适用于这种情况。有关为什么颠倒我的术语顺序没有帮助的解释，请参阅下面更现实的示例。

举一个更现实的例子，考虑单位解析。语法应该识别带有可选前缀的公制单位（如“m”、“mol”），如“mm”、“mmol”，以及非公制单位，如“yr”、“week”或“mo”。

以下 Peg.js 语法无法识别“mol”，因为它在使用“mo”时会出错，并且不会回溯。（更改术语的顺序无济于事；或者更确切地说，会导致“mo”以牺牲“mol”或“mmol”为代价而被识别。）

我可以在 Antlr 中成功地做类似的事情：

故事如下。我正在使用peg/leg 解析器生成器，它具有用于定义 PEG 语法的出色语法，并且非常易于使用。我对此非常满意，直到生成的解析器出现神秘的段错误。一些研究揭示了生成的辅助函数之一中的问题：

此函数始终在 count<0 时调用。在 C 数组上使用负索引是未定义的行为。据我了解，内存是由 peg/leg 以这样一种方式分配的，即从数组开头向后指向会在其他数组中给出正确的指针。这实际上是非常糟糕的代码，但它在大多数情况下都能正常工作。但是，我的程序其他部分的某些分配会强制将内存块和所有段错误放在不同的位置。

我怀疑问题是由于 peg/leg 使用 malloc 而我的程序使用 new 的事实引起的，但是我无法将代码更改为使用 malloc 并且无法修复 peg/leg（它复杂且晦涩）。

因此，我需要将解析器使用的内存与我的程序的其余部分隔离，以避免任何干扰。

有没有办法在 C++ 中做到这一点？是否有可能将解析器代码放入“沙箱”？

我有这个 pegjs 语法。如何删除左递归？