lambda演算的Python解析器

这个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>)

这里有一个替代方法,可以删除左递归。尽管访问语法树是西奥普的练习。

from parsimonious import Grammar

grammar = Grammar(r"""
    start = term

    term = ('(' _* term1 _* ')') / term1
    term1 = app / atom1

    atom = ('(' _* atom1 _* ')') / atom1
    atom1 = abs / id

    abs = 'λ' _* id _* '.' _* term

    app = atom _+ term

    id = ~"[A-Za-z]+"

    _ = ~"[^\S\n\r]"u
""")

print(grammar.parse("x y z w"))