Анализ подразумеваемого и явного оператора времени

Я писал синтаксический анализатор LALR с использованием ply и столкнулся с несоответствием при попытке проанализировать умножение.

Поскольку полный анализатор link состоит из нескольких тысяч строк, я не буду включать его сюда, но я создал простую демонстрацию:

import ply.lex as lex
import ply.yacc as yacc

tokens = (
    'int',
    'times',
    'plus',
)

precedence = (
    ('left', 'plus'),
    ('left', 'times'),
)

t_ignore = ' \t\n '
t_int = r' \d+ '
t_plus = r' \+ '
t_times = ' \* '

def p_int(args):
    'expr : int'
    args[0] = int(args[1])

def p_times(args):
    '''expr : expr times expr
            | expr expr %prec times'''
    if len(args) == 3:
        args[0] = args[1] * args[2]
    elif len(args) == 4:
        args[0] = args[1] * args[3]

def p_plus(args):
    'expr : expr plus expr'
    args[0] = args[1] + args[3]

lex.lex()
parser = yacc.yacc()

while True:
    s = raw_input('>> ')
    print " = ", parser.parse(s)

PLY не сообщает о конфликтах сдвига/уменьшения или конфликтах уменьшения/уменьшения, но я получаю следующее несоответствие:

    >>  1 + 2 3
     =  9
    >>  1 + 2 * 3
     =  7

Это кажется мне странным, поскольку явные и неявные правила времени имеют одинаковый приоритет. Но я думаю, что это может быть связано с тем, что PLY присваивает приоритет токену «times» и, таким образом, сдвигает его в стек в пользу сокращения выражения с помощью правила p_plus. Как я могу это исправить?

Изменить: более простая демонстрация.


person sn6uv    schedule 10.04.2013    source источник
comment
Вы можете просто добавить open к своей приоритетной ассоциации? Я давно не занимался грамматикой   -  person Joran Beasley    schedule 10.04.2013
comment
Это может сработать в данном случае, но есть и другие случаи, которые следует учитывать. Например, «1 + 2 3» => 9 против «1 + 2 * 3» => 7.   -  person sn6uv    schedule 10.04.2013
comment
@JoranBeasley Я отредактировал вопрос, чтобы упростить пример.   -  person sn6uv    schedule 10.04.2013
comment
Вы можете добавить expr к своим приоритетам? ... не уверен, что это может сломать другие вещи   -  person Joran Beasley    schedule 10.04.2013
comment
Да, это тоже не работает. Я думаю, потому что expr не является терминалом, а PLY позволяет вам назначать приоритет только терминалам. Редактировать: что-то подобное работает - добавление int к приоритету, поскольку это токен, который смещается.   -  person sn6uv    schedule 10.04.2013
comment
хорошо :) грубо, это может быть больно, если вы планируете добавить больше типов ...   -  person Joran Beasley    schedule 10.04.2013
comment
Истинный. Интересно, есть ли другой способ сделать это, так как у меня есть несколько типов, и я беспокоюсь, что это может сломать другие вещи.   -  person sn6uv    schedule 10.04.2013
comment
давайте продолжим это обсуждение в чате   -  person Joran Beasley    schedule 10.04.2013


Ответы (2)


Быстрый хак: добавьте токен int в спецификацию приоритета (с приоритетом времени). Затем токен int будет соответствующим образом перемещен в стек символов. То есть (согласно исходному вопросу),

precedence = (
    ('left', 'plus'),
    ('left', 'times', 'int'),
)

Это работает, но запутанно при работе с потенциально большим количеством токенов (открытые скобки, символы, числа с плавающей запятой и т. д.).

>>  1 + 2 3
 =  7

Я все еще хотел бы знать, есть ли более элегантное решение для этого.

person sn6uv    schedule 22.04.2013

Есть более подходящее решение: отказаться от приоритета операторов и определить нетерминальные символы expr, term и factor обычным способом. Причина? Подразумеваемое умножение не имеет маркера характеристики, на котором можно основывать решения о приоритете, и вы не хотите вручную восстанавливать ПЕРВЫЙ набор нетерминала. Кроме того, по мере роста вашей грамматики будет расти и набор FIRST.

В BNF рассмотрите что-то вроде:

expr -> term | expr + term | expr - term
term -> factor | term * factor | term factor | term / factor
factor -> number | variable | ( expr )

И, кстати, вы, вероятно, захотите создать дополнительный нетерминальный слой, чтобы представить тот факт, что неявное умножение на смежность обычно считается более приоритетным, чем деление, в то время как явное умножение обычно интерпретируется как имеющее такой же приоритет .

Это не относится к какой-либо конкретной структуре генератора синтаксических анализаторов.

person Ian    schedule 13.07.2019