По грамматическим правилам парсера рекурсивного спуска, как мы можем проверить исходную строку

Question

Если введены следующие две входные строки:

1)<id> + <id> * <id>
2) <id> * <id> <id>

E ::= T{+T}* 
T ::= V{*V}* 
V ::= <id>

Затем, применяя приведенные выше правила грамматики синтаксического анализатора рекурсивного спуска, как мы можем проверить указанную выше исходную строку. Какой тип ошибки будет указывать парсер рекурсивного спуска?

Спасибо ...

Answer 1

Ваши правила грамматики выглядят как арифметическая инфиксная запись. Pyparsing (дополнительный модуль разбора Python) имеет встроенный метод для построения выражений синтаксического анализатора для этого вида нотации, который называется operatorPrecedence. Вот как синтаксический анализатор разберет ваши два примера:

from pyparsing import operatorPrecedence, opAssoc, ParseException

expr = operatorPrecedence("<id>",
    [
    ('*', 2, opAssoc.LEFT),
    ('+', 2, opAssoc.LEFT),
    ])

tests = """\
<id> + <id> * <id> 
<id> * <id> <id>""".splitlines()

for t in tests:
    print t
    try:
        print expr.parseString(t, parseAll=True).asList()
    except ParseException,pe:
        print "parsing failed"
    print

Печать:

<id> + <id> * <id> 
[['<id>', '+', ['<id>', '*', '<id>']]]

<id> * <id> <id>
parsing failed

Надеюсь, это поможет вам в учебе.