时间戳

首页 > 解决方案 > 用于 lambda 演算的 Python 解析器

python - 用于 lambda 演算的 Python 解析器

问题描述

为了好玩，我想为无类型的 Lambda 演算编写一个解析器。最简单的方法可能是写一个手写解析器，但我想知道是否有更 Pythonic 的方式？具体来说，我想使用一个 Python 库，将语言的语法描述翻译成解析器。这是该语言的 BNF 定义：

<term> ::= <var>
        |  <term> <term>
        |  λ <var> <term>

为简单起见，我省略了括号规则。应用程序关联到左侧，x y z即(x y) z。

什么 Python 库可以采用上述语法描述，或从它派生的一些语法（如所写，我相信语法是模棱两可的和左递归的，因此实现起来并不简单），并产生一个解析器？我想看看它是如何使用代码完成的，所以请不要只回答“pyparsing 可以做到”。请按照以下几行编写代码：

>>> G = """syntax description here..."""
>>> parser = build.the_parser(G)
>>> parser.parse("λ x. (y z)")
Abs('x', App(Id('x', Id('y'))))

最后一行是生成的抽象语法树可能是什么。Abs 代表抽象 (lambda)，App 代表应用程序，Id 代表标识符。我认为 PEG packrat 解析器生成器在这里可以很好地工作。

标签： pythonparsinglambda-calculuspeg

解决方案

这个 ANTLR4 语法可以解决问题：

grammar T;

program
 : term EOF
 ;

term
 : Lambda Id '.' term
 | '(' term ')'
 | term term
 | Id
 ;

Lambda
 : '\u03BB'
 ;

Id
 : [a-z] [a-zA-Z0-9]*
 ;

Spaces
 : [ \t\r\n] -> skip
 ;

将上述内容放在一个名为T.g4. 将ANTLR4 jar下载到同一文件夹中并执行以下操作：

java -cp antlr-4.7.2-complete.jar org.antlr.v4.Tool -Dlanguage=Python3 T.g4

这将创建词法分析器和解析器文件。

现在运行：

from antlr4 import *
from playground.TLexer import TLexer
from playground.TParser import TParser


tests = [
  'λ x. (y z)', 
  'x y z w'
]

for test in tests:
    lexer = TLexer(InputStream(test))
    parser = TParser(CommonTokenStream(lexer))
    tree = parser.program()
    print("{}".format(tree.toStringTree(recog=parser)))

这将打印：

(program (term λ x . (term ( (term (term y) (term z)) ))) <EOF>)
(program (term (term (term (term x) (term y)) (term z)) (term w)) <EOF>)

推荐阅读