Почему в некоторых случаях я не могу использовать токен в качестве маркера приоритета

Question

Предположим, этот код работает:

left '*'
left '+'

expr: expr '+' expr
    | expr '*' expr
    ;

Я хочу определить другой маркер приоритета, например:

left MULTIPLY
left PLUS

expr: expr '+' expr %prec PLUS
    | expr '*' expr %prec MULTIPLY
    ;

Тем не менее, это на самом деле не эффективно.

Я полагаю, что эти две формы должны быть эквивалентны, однако это не так.

Это не практическая проблема. Я просто хочу знать причину и принцип этого явления.

Благодарю.

Answer 1

Вы говорите, что не пытаетесь решить конкретную, практическую проблему. И из вашего вопроса, я немного запутался в том, как вы пытаетесь использовать маркер приоритета.

Я думаю, вы обнаружите, что вам не нужно часто использовать маркер приоритета. Как правило, читателю проще и понятнее переписать грамматику так, чтобы приоритет был явно учтен. Чтобы дать умножение и деление более высокого приоритета, чем сложение и вычитание, вы можете сделать что-то вроде этого (пример, адаптированный из John Levine, lex & yacc 2 / e, 1992):

%token NAME NUMBER

%%

stmt : NAME '=' expr
     | expr
     ;

expr : expr '+' term
     | expr '-' term
     | term
     ;

term : term '*' factor
     | term '/' factor
     | factor
     ;

factor : '(' expr ')'
       | '-' factor
       | NUMBER
       ;

В вашем примере PLUS а также MULTIPLY не настоящие токены; Вы не можете использовать их взаимозаменяемо с '+' а также '*', Левин называет их псевдо-токенами. Они там, чтобы связать ваши произведения обратно с вашим списком приоритетов, которые вы определили с %left а также %nonassoc деклараций. Он приводит этот пример того, как вы могли бы использовать %prec дать одинарный минус высокий приоритет, даже если токен '-' имеет низкий приоритет:

%token NAME NUMBER
%left '-' '+'
%left '*' '/'
%nonassoc UMINUS

%%

stmt : NAME '=' expr
     | expr
     ;

expr : expr '+' expr
     | expr '-' expr
     | expr '*' expr
     | expr '/' expr
     | '-' expr %prec UMINUS
     | '(' expr ')'
     | NUMBER
     ;

Подводя итог, я бы рекомендовал следовать шаблону моего первого примера кода, а не второго; сделать грамматику явной

Answer 2

Правила приоритета Yacc на самом деле не относятся к приоритету выражений, хотя они могут использоваться для этого. Вместо этого они являются способом разрешения конфликтов смещения / уменьшения (и ТОЛЬКО смещения / уменьшения конфликтов) явно.

Чтобы понять, как это работает, нужно понять, как работает синтаксический анализ сдвиг / уменьшение (снизу вверх). Основная идея заключается в том, что вы читаете символы токенов из входных данных и помещаете ("смещаете") эти токены в стек. Когда символы в верхней части стека соответствуют правой части некоторого правила в грамматике, вы можете "уменьшить" правило, вытолкнув символы из стека и заменив их одним символом с левой стороны правила. Вы повторяете этот процесс, меняя токены и сокращая правила до тех пор, пока не прочитаете весь ввод и не уменьшите его до одного экземпляра начального символа, после чего вы успешно проанализировали весь ввод.

Основная проблема с вышеизложенным (и тем, что решает весь механизм генератора синтаксического анализатора) состоит в том, чтобы знать, когда сокращать правило по сравнению с тем, когда сдвигать токен, если оба возможны. Генератор синтаксического анализатора (yacc или bison) создает конечный автомат, который отслеживает, какие символы были сдвинуты, и поэтому знает, какие "частично совпадающие" правила в настоящее время возможны, и ограничивает сдвиги только теми токенами, которые могут соответствовать большему количеству такого правила. Это не работает, если рассматриваемая грамматика не является LALR(1), и поэтому в таких случаях отчеты yacc/bsion сдвигают / уменьшают или уменьшают / уменьшают конфликты.

Правила приоритета работают для разрешения конфликтов уменьшения сдвига, назначая приоритет определенным токенам и правилам в грамматике. Всякий раз, когда возникает конфликт сдвига / уменьшения между токеном, подлежащим сдвигу, и правилом, подлежащим сокращению, и ОБА имеют приоритет, он будет делать то, что имеет более высокий приоритет. Если они имеют тот же приоритет, то он смотрит на %left/%right/%nonassoc флаг, связанный с уровнем приоритета - %left значит уменьшить, %right означает сдвиг, и %nonassoc означает, что не делайте ни одного, и рассматривайте это как синтаксическую ошибку.

Единственный хитрый оставшийся бит - как токены и правила получают свой приоритет. Токены получают их от %left/%right/%nonassoc директива, в которой они находятся, которая также устанавливает порядок. Правила получают приоритет от %prec директива ИЛИ от самого правого терминала на их правой стороне. Итак, когда у вас есть:

%left '*'
%left '+'

expr: expr '+' expr
    | expr '*' expr
    ;

Вы устанавливаете приоритет '*' а также '+' с %left директивы, и эти два правила получают их приоритет от этих токенов.

Когда у тебя есть:

%left MULTIPLY
%left PLUS

expr: expr '+' expr %prec PLUS
    | expr '*' expr %prec MULTIPLY
    ;

Вы устанавливаете приоритет токенов MULTIPLY а также PLUS а затем явно установить правила, чтобы иметь эти приоритеты. Однако вы НЕ УСТАНАВЛИВАЕТЕ ЛЮБОЙ ПРЕЦЕДЕНТНОСТИ для токенов '*' а также '+', Таким образом, когда есть сдвиг / уменьшение конфликта между одним из двух правил и либо '*' или же '+', приоритет не разрешает это, потому что токен не имеет приоритета.

Answer 3

Конфликты Shift-Reduce - это конфликт между попыткой сократить производство по сравнению со смещением токена и переходом в состояние гнезда. Когда Bison разрешает конфликт, он не сравнивает два правила и выбирает одно из них - сравнивает одно правило, которое он хочет уменьшить, и маркер, который вы хотите изменить в других правилах. Это может быть понятнее, если вам нужно изменить два правила:

expr: expr '+' expr
    | expr '*' expr
    | expr '*' '*' expr

Причина, по которой все это сбивает с толку, заключается в том, что способ, которым Bison отдает приоритет правилу "уменьшить", заключается в том, чтобы связать его с токеном (последний терминал в правиле по умолчанию или токен из предварительного объявления), а затем он использует приоритет таблица для сравнения этого токена с токеном, который вы пытаетесь сдвинуть. По сути, предварительные декларации имеют смысл только для "уменьшенной" части конфликта, и они не учитываются для сменной части.

Один из способов увидеть это с помощью следующей грамматики

command: IF '(' expr ')' command               %prec NOELSE
       : IF '(' expr ')' command ELSE command

В этой грамматике вам нужно выбрать между уменьшением первого правила или смещением токена ELSE. Вы делаете это либо путем предоставления приоритетов токену ')' и токену ELSE, либо используя предварительное объявление и давая приоритет для NOELSE вместо ')'. Если вы попытаетесь дать предварительное объявление второму, оно будет проигнорировано, и Бизон продолжит поиск приоритета токена ELSE в таблице приоритетов.