LINUX.ORG.RU

Вопрос про Lex/Yacc

 , , ,


0

1

Вообще, я использую PLY, но поскольку синтаксис описания грамматики он использует от Yacc, то вопрос скорее по нему, а не по питоноспецифичным вещам.

На самом деле моя грамматика гораздо больше, но чтобы не загромождать сообщение написал minimal not working example:

from ply import lex, yacc

tokens = ('LT', 'LPAREN', 'RPAREN', 'NAME')

t_NAME = r'[A-Za-z_@][A-Za-z0-9_@]*'
t_LPAREN = r'\('
t_RPAREN = r'\)'
t_LT = r'<'

t_ignore = ' '

precedence = (
	('left', 'LT'),
	('left', 'CALL')
)

def p_expression_binop(p):
	'expression : expression LT expression'
	p[0] = (p[2], p[1], p[3])

def p_expression_call(p):
	'expression : expression LPAREN RPAREN %prec CALL'
	p[0] = ('Call', p[1])

def p_expression_name(p):
	'expression : NAME'
	p[0] = ('Name', p[1])

lexer = lex.lex()
parser = yacc.yacc()
print(parser.parse('a < b()'))

Если выполнить этот скрипт (PLY должен быть установлен через пакетный менеджер дистрибутива или pip), то можно получить результат (добавил отступы и переносы для читабельности):

[
    ('Call',
        ('<',
            ('Name', 'a'),
            ('Name', 'b')
        )
    )
]

Как можно заметить, операция сравнения оказалась более приоритетной (хотя в precedence она идёт раньше, что даёт меньший приоритет - проверено на другой грамматике, где есть сложение и умножение - 2 + 2 * 2 вычисляется с верными приоритетами), чем вызов функции и в результате мы получаем вызов как функции результата сравнения переменной (a) и функции (b), что, конечно же, полная чушь.

Где я допустил ошибку и как её исправить?

★★★★★

Может поднять продукцию со скобками над продукцией со сравнением? Вроде так приоритет там устанавливается, сам не пользовался.

anonymous ()
Ответ на: комментарий от anonymous

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

Для вызова функции устанавливается приоритет CALL (явно с помощью %prec), а для сравнения приоритет LT (неявно). CALL следует в списке precedence ПОСЛЕ LT, что соответствует более высокому приоритету (выражение 2 + 2 * 2 вычисляется с верными приоритетами, так что приоритеты я вроде как задаю верным способом).

KivApple ★★★★★ ()

Можешь написать грамматику в БНФ нотации? Я что-то тяжело этот код на питоне воспринимаю.

Дерево разбора ручками строил? Может у тебя где неоднозначность.

java_util_Random ★★ ()
Ответ на: комментарий от java_util_Random

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

<expression> ::= <expression> '<' <expression> | <expression> '(' ')' | NAME 

Тут есть важный момент - по идее я задаю приоритет '(' над '<' с помощью списка precedence.

Если описать грамматику вида:

<expression> ::= <expression> '+' <expression> | <expression> '*' <expression> | NAME

и точно также задать приоритет * над +, то выражение 2 + 2 * 2 парсится корректно (сначала умножение, потом сложение, а не наоборот).

Здесь NAME - последовательность из больших и малых латинских букв, цифр, знака подчёркивания и собаки. При этом начинающееся не с цифры и длинной не меньше 1 символа.

Помимо прочего PLY генерирует вот такой лог при построении дерева - http://pastebin.com/x5pzSEJh, но я недостаточно хорошо разбираюсь в вопросе, чтобы сделать по нему какие-либо выводы.

KivApple ★★★★★ ()
Последнее исправление: KivApple (всего исправлений: 2)
Ответ на: комментарий от KivApple

<expression> ::= <expression> '<' <expression> | <expression> '(' ')' | NAME

А где тут у тебя приоритет-то?

Приоритет операций как-то так задается:

<Expr> ::= <Term> {<Operation1> <Term>}
<Term> ::= <Factor> {<Operation2> <Factor>}
<Factor> ::= <Name> | '(' <Expr> ')'
<Operation1> ::= '+' | '-'
<Operation2> ::= '*' | '/'

java_util_Random ★★ ()
Ответ на: комментарий от KivApple

Я вроде понял, тебе надо упростить грамматику с

<expression> ::= <expression> '<' <expression> | <expression> '(' ')' | NAME 
<expression> ::= <expression> '<' <expression> | <call> | NAME
<call>       ::= NAME '(' ')'
т.е. идентификатор функции не должен быть произвольным выражением

anonymous ()
Ответ на: комментарий от anonymous

А если мне как раз таки нужно, чтобы идентификатор функции мог быть произвольным выражением, как это сделано в Си?

KivApple ★★★★★ ()
Ответ на: комментарий от KivApple

Не думаю что там произвольное выражение может вызываться, a < b же не должно вызываться. Мне кажется тебе все равно надо как-то ограничить язык вызова, разделить всю эту длинную портянку expression'а на какие-нибудь binary, unary prefix, unary postfix и т.п. На конкретно этом, упрощенном примере, это будет так как я написал, на реальном конечно сложнее. Мне так кажется.

anonymous ()
Ответ на: комментарий от anonymous

Пока решил проблему таким образом:

expression : NAME LPAREN expression_list RPAREN %prec CALL
           | LPAREN expression RPAREN LPAREN expression_list RPAREN %prec CALL		
KivApple ★★★★★ ()
Ответ на: комментарий от java_util_Random

речь идет о LALR
подсовывает пердолькостыль для LL

Deleted ()

Директива %prec не работает потому, что она задаёт приоритет второго правила: expression: expression '(' ')', а конфликт вида перенос/свёртка (shift/reduce) происходит между первым правилом (expression: expression '<' expression) и символом предпросмотра '('.

С виду кажется, что раз конфликт вызван столкновением двух правил, то и разрешать его надо на уровне «правило против правила». Но в данном случае это «правило против символа».

В случае с арифметическими выражениями %prec срабатывает потому, что там конфликт вида свёртка/свёртка (reduce/reduce), а это другое дело: конфликт между двумя правилами, и приоритет обоих участвует в разрешении.

Всё это довольно легко понять из лога гну-бизона. Пример:

%%
e : e '<' e
  | e '(' ')'
  | 'a'
  ;
Обдаём бизоном с ключом -r all чтобы он сдампил лог:
State 6 conflicts: 2 shift/reduce
...
State 6

    1 e: e . '<' e
    1  | e '<' e .  [$end, '<', '(']
    2  | e . '(' ')'

    '<'  shift, and go to state 4
    '('  shift, and go to state 5

    '<'       [reduce using rule 1 (e)]
    '('       [reduce using rule 1 (e)]
    $default  reduce using rule 1 (e)

Бизон говорит про два конфликта, оба shift/reduce.

Первый легко разрешается добавлением директивы %left '<':, как было предложено в оригинальном посте (решается в пользу reduce из-за левоассоциативности '<').

Второй конфликт между сдвигом символа '(' и свёрткой по правилу e: e '<' e, у которого среди допустимых символов предпросмотра тоже есть '(' (как раз этим и вызван конфликт). Разрешить его можно, задав символу '(' больший приоритет, чем правилу e: e '<' e (у которого по умолчанию приоритет символа '<'):

%left '<'
%left '('

%%
e : e '<' e
  | e '(' ')'
  | 'a'
  ;
И отследить в логе, что всё разрешилось именно так, как мы думаем:
State 6

    1 e: e . '<' e
    1  | e '<' e .  [$end, '<']
    2  | e . '(' ')'

    '('  shift, and go to state 5

    $default  reduce using rule 1 (e)

    Conflict between rule 1 and token '<' resolved as reduce (%left '<').
    Conflict between rule 1 and token '(' resolved as shift ('<' < '(').
То есть ошибка в том, что вместо пары (свёртка e: e '<' e, сдвиг '(') автор пытался разрешить несуществующий конфликт пары (свёртка e: e '(' ')', сдвиг '<'). А ведь в логе всё написано!

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.