Построение грамматики в слое - рекурсия разрешена? - PullRequest
Новая
       47

Построение грамматики в слое - рекурсия разрешена?

0 голосов
/ 19 января 2019

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

У меня есть строки типа a OR b, b OR C, но также a OR (b AND c). Теперь вложенные скобки доставляют мне неприятности, и я не знаю, как создать соответствующие функции p_*. Допускается ли рекурсия? Если да, то как?

Это то, что я имею до сих пор: 
import ply.lex as lex
import ply.yacc as yacc

# List of token names.   This is always required
tokens = (
    'VARIABLE',
    'OR',
    'AND',
    'PAR_OPEN',
    'PAR_CLOSE',
)

# Regular expression rules for simple tokens
t_ignore        = ' \t'
t_VARIABLE      = r'\b[a-z]+\b'
t_OR            = r'\bOR\b'
t_AND           = r'\bAND\b'
t_PAR_OPEN      = r'\('
t_PAR_CLOSE     = r'\)'

def t_error(t):
    print("Illegal character '%s'" % t.value[0])
    t.lexer.skip(1)

# Build the lexer
lexer = lex.lex()

def p_term(p):
    '''term : VARIABLE OR VARIABLE
            | VARIABLE AND VARIABLE
            | PAR_OPEN VARIABLE AND VARIABLE PAR_CLOSE'''

    if p[2] == 'AND':
        p[0] = "".join([p[1], p[3]])

    for idx, val in enumerate(p):
        print(idx, val)

def p_error(p):
    print("Syntax error in input!")
    print(p)


parser = yacc.yacc()
res = parser.parse("(a AND b)")
print(res)

Я также хотел бы назвать это, например, res = parser.parse("a OR (b AND c)") но безрезультатно.

П.С .: Это основано на вопрос другого человека , действительно.

1 Ответ

0 голосов
/ 19 января 2019

Скобки в выражении довольно распространены.Сначала я отошлю вас к части 5 документации PLY , в которой приведен пример разбора вложенных выражений.Да, рекурсия - это ответ.

Есть несколько фраз, которые означают «наименьший элемент выражения».Вы можете увидеть «atom» или «term» (сокращение от «Terminal») или «primary-expression».

При работе с подвыражениями в скобках обычно используется именно такой подход.Напишите правило грамматики, которое объединяет различные низкоуровневые вещи (например, литеральные числа и имена переменных) и добавьте подвыражение в этой точке.

В этом примере из документов PLY expressionэто вещь самого высокого уровня, и поддерживает сложение и вычитание.Следующий уровень вниз - term, который поддерживает умножение и деление.Самым нижним уровнем является factor, который не поддерживает никаких операций, но объединяет NUMBER и вложенные выражения в скобках.Фактор может быть 7, но также может быть (7 + 2 * 3). 

 expression : expression + term
            | expression - term
            | term

 term       : term * factor
            | term / factor
            | factor

 factor     : NUMBER
            | ( expression )
...