Анализатор Python для лямбда-исчисления - PullRequest
Новая
       31

Анализатор Python для лямбда-исчисления

1 голос
/ 10 апреля 2019

Ради интереса я хочу написать парсер для нетипизированного лямбда-исчисления.Самый простой подход - написать рукописный парсер, но мне интересно, есть ли более питонский способ?В частности, я хочу использовать библиотеку 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'))))

В последней строке указано, каким может быть созданное абстрактное синтаксическое дерево.Абс обозначает абстракцию (лямбда), приложение для приложения и идентификатор для идентификатора.Я думаю, что генератор синтаксического анализатора PEG Packrat будет хорошо работать здесь.

Ответы [ 2 ]

1 голос
/ 10 апреля 2019

Эта грамматика 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>)
0 голосов
/ 18 апреля 2019

Вот альтернатива, которая удаляет левую рекурсию.Хотя посещение синтаксического дерева - это упражнение для ОП. 

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"))
...