Python PLY парсер

Question

Я пытался найти ответ на этот вопрос, но, похоже, не смог его найти.Я пытаюсь написать парсер на Python, используя PLY для выдуманного языка.Упрощенная версия моего BNF выглядит следующим образом:

statement-list -> statement ',' statement-list |
                 'print' expr

statement -> ident 'was' 'a' type |
             ident 'became' expr

type -> 'number' | 'letter'

expr -> factor |
       expr '+' factor |
       expr '-' factor

factor -> number | letter | ident

, где числа и буквы похожи на int и char.

Документация Yacc (http://www.dabeaz.com/ply/ply.html#ply_nn23) показывает только синтаксис дляпростые арифметические выражения, где ясно, каким должно быть p [0].

def p_expression_plus(p):
   'expression : expression PLUS term'
    p[0] = p[1] + p[3]

Мой вопрос: что мне делать для списка операторов в моей БНФ? У меня есть:

def p_statement_list_comma(p):
    'statement-list : statement COMMA statement-list'

но я действительно не уверен, что делать дальше. Любая помощь будет очень признательна!

Answer 1

Я не могу говорить о PLY-решении, но вот тот, который использует pyparsing. Иногда пример pyparsing может быть полезен, даже если вы в конечном итоге захотите реализовать свой парсер, используя какую-то другую библиотеку, в качестве быстрого и грязного прототипа / упражнения. К сожалению, в этом примере интенсивно используется метод operatorPrecedence, который скрывает большую часть магии разбора инфикса, поэтому я не знаю, насколько легко вы сможете его перевести. Более традиционный пример синтаксического анализатора expr / term / factor можно найти на вики-странице pyparsing на странице примеров (http://pyparsing.wikispaces.com/Examples), под названием fourFn.py .

bnf = """
statement-list -> statement ',' statement-list

statement -> ident 'was' 'a' type | 
             ident 'became' expr |
             'print' expr |
             'if' conditional-expr statement

type -> 'number' | 'letter' 

expr -> factor | 
       expr '+' factor | 
       expr '-' factor 

factor -> number | letter | ident 
"""

from pyparsing import (CaselessKeyword, Word, nums, alphas, alphanums, operatorPrecedence, 
    Forward, MatchFirst, opAssoc, oneOf, Group, delimitedList)

PRINT, WAS, A, BECAME, NUMBER, LETTER, IF, ELSE, TRUE, FALSE, AND, OR, NOT = map(
    CaselessKeyword,
    "print was a became number letter if else true false and or not".upper().split())
keyword = MatchFirst([PRINT, WAS, A, BECAME, NUMBER, LETTER, IF, ELSE, TRUE, FALSE, AND, OR, NOT])

typeSpecifier = NUMBER | LETTER

number = Word(nums)
ident = ~keyword + Word(alphas, alphanums+'_')
operand = number | ident

expr = operatorPrecedence(operand,
    [
    ('-', 1, opAssoc.RIGHT),
    (oneOf('* /'), 2, opAssoc.LEFT),
    (oneOf('+ -'), 2, opAssoc.LEFT),
    ])

comparisonExpr = operatorPrecedence(expr,
    [
    ("!", 1, opAssoc.RIGHT),
    (oneOf("< > = <= >= !="), 2, opAssoc.LEFT),
    ])

booleanExpr = operatorPrecedence(TRUE | FALSE | comparisonExpr,
    [
    (NOT, 1, opAssoc.RIGHT),
    (AND, 2, opAssoc.LEFT),
    (OR, 2, opAssoc.LEFT),
    ])

statement = Forward()
printStmt  = PRINT + expr
wasaStmt   = ident + WAS + A + typeSpecifier
becameStmt = ident + BECAME + expr
ifStmt = IF + booleanExpr + statement
statement << Group(printStmt | wasaStmt | becameStmt | ifStmt)

statementList = delimitedList(statement)

tests = """\
    x was a number
    y became 2+5
    print y
    print 100*(5+2)
    print 100*5+2
    if 5 > y print 1000
    if y < 10 y became y+1, print y
    """.splitlines()[:-1]

for t in tests:
    print t.strip()
    for s in statementList.parseString(t).asList():
        print(s)
    print

Печать:

x was a number
['x', 'WAS', 'A', 'NUMBER']

y became 2+5
['y', 'BECAME', ['2', '+', '5']]

print y
['PRINT', 'y']

print 100*(5+2)
['PRINT', ['100', '*', ['5', '+', '2']]]

print 100*5+2
['PRINT', [['100', '*', '5'], '+', '2']]

if 5 > y print 1000
['IF', ['5', '>', 'y'], ['PRINT', '1000']]

if y < 10 y became y+1, print y
['IF', ['y', '<', '10'], ['y', 'BECAME', ['y', '+', '1']]
['PRINT', 'y']

Я позволил себе добавить print в качестве типа оператора, чтобы он мог появляться в любом месте тела вашей программы. Кроме того, я попытался добавить оператор IF-THEN, и этот действительно показывает, как добавление такого оператора control-flow начинает вас по пути написания рекурсивной грамматики (рекурсия не нужна только для ' был ',' стал ', и' печать ').

Answer 2

Это действительно зависит от того, как вы структурируете свой код и как вы хотите его оценить.Если вы оцениваете по ходу дела, при условии, что оно оценивается в правильном порядке, вы не хотите, чтобы вы, вероятно, ничего не хотели после строки документа p_statement_list_comma, то есть точно так же, как у вас - операторы все равно будут оцениватьсяи, если необходимо, вы можете хранить глобальный словарь переменных или что-то подобное для отслеживания некоторого состояния, такого как значения идентификаторов.

Если вы хотите создать дерево разбора, например, для оценки отдельно, если вы этого не сделаетекак и порядок оценки ply, вы можете сделать что-то вроде этого:

def p_statement_list_comma(p):
    'statement-list : statement COMMA statement-list'
    p[0] = [p[1]] + p[3]

def p_statement_print_expr(p):
    'statement-list : PRINT expr'
    p[0] = [p[2]]

Это даст вам список утверждений, а последний элемент в списке будет выражением.Это использует списки для простоты;Вы также можете использовать свои собственные классы, если хотите - просто назначьте любой объект python, который вы хотите, p [0], и он будет доступен для уровня выше.

Если вы хотите, чтобы результат выражения print был возвращениз yacc.parse (значение из верхнего уровня дерева разбора будет возвращено из yacc.parse), вы можете сделать это так:

def p_statement_list_comma(p):
    'statement-list : statement COMMA statement-list'
    p[0] = p[3]

def p_statement_print_expr(p):
    'statement-list : PRINT expr'
    p[0] = p[2]