使用 LL1 解析器解析 lambda 演算风格的函数应用

Question

我正在使用 TinyPG，这是一个 LL1 解析器生成器，用于解析 lambda 演算。我正在尝试编写一个规则来解析 (a b) 或 (a b c) 等函数应用程序。

到目前为止我有这个规则（有点简化）：

APPLICATION -> LPARENTHESES VARIABLE (SPACE+ VARIABLE)+ RPARENTHESES;

但是这将无法解析在左括号之后和右括号之前有空格的术语：( a b )。我可以像这样在左括号后留出空格：

APPLICATION -> LPARENTHESES SPACE* VARIABLE (SPACE+ VARIABLE)+ RPARENTHESES;

但我无法将其设置为在右括号前允许空格。我想到了这个，它似乎有效：

ARG_LIST        -> (RPARENTHESES | (SPACE+ (RPARENTHESES | (VARIABLE ARG_LIST))));
APPLICATION     -> LPARENTHESES SPACE* VARIABLE ARG_LIST;

但是比较杂乱和递归，这会导致难以读取和编译节点。是否有任何非递归或至少更简单的方法来解析它？

Answer 1

没有理由将解析器与白色混淆space。使用 [Skip] 属性在扫描器中忽略它就足够了，如教程中所示：

[Skip] WHITESPACE -> @"\s+";

"Skip" 并不代表 "delete"。这意味着扫描器应该识别令牌然后忽略它。如果您跳过 whitespace，whitespace 仍会很好地分隔字母数字标记。您只是不需要在语法中包含 space 标记，剩下的是：

APPLICATION -> LPARENTHESES VARIABLE VARIABLE+ RPARENTHESES;

（实际上，通常允许使用空的应用程序列表，所以我会用 * 而不是 + 来写。但这是你的语言。）

Parse lambda calculus style function applications with LL1 parser