Сдвиг-уменьшение: когда прекратить сокращение?

Я пытаюсь узнать о разборе сдвига-уменьшения. Предположим, у нас есть следующая грамматика, использующая рекурсивные правила, которые обеспечивают порядок операций, основанный на грамматике ANSI C Yacc:

S: A;

P
    : NUMBER
    | '(' S ')'
    ;

M
    : P
    | M '*' P
    | M '/' P
    ;

A
    : M
    | A '+' M
    | A '-' M
    ;

И мы хотим проанализировать 1+2, используя разбор сдвига-уменьшения. Во-первых, 1 сдвигается как НОМЕР. У меня вопрос: тогда он сводится к P, затем M, затем A, и, наконец, S? Как он знает, где остановиться?

Предположим, что он сокращается до S, затем сдвигается "+". Теперь у нас есть стек, содержащий:

S '+'

Если мы сместим '2', сокращение может быть:

S '+' NUMBER
S '+' P
S '+' M
S '+' A
S '+' S

Теперь по обе стороны от последней строки S может быть P, M, A или NUMBER, и все равно будет допустимым в том смысле, что любая комбинация будет правильным представлением текста. Как парсер "знает", как сделать это

A '+' M

Так что это может уменьшить все выражение до A, тогда S? Другими словами, как он знает, что нужно прекратить сокращение, прежде чем сдвигать следующий токен? Является ли это ключевой трудностью при создании парсера LR?

Изменить: дополнение к вопросу следует.

Теперь предположим, что мы разбираем 1+2*3, Некоторые операции сдвига / уменьшения следующие:

Stack    | Input | Operation
---------+-------+----------------------------------------------
         | 1+2*3 | 
NUMBER   | +2*3  | Shift
A        | +2*3  | Reduce (looking ahead, we know to stop at A)
A+       | 2*3   | Shift
A+NUMBER | *3    | Shift (looking ahead, we know to stop at M)
A+M      | *3    | Reduce (looking ahead, we know to stop at M)

Это правильно (предоставлено, оно еще не полностью проанализировано)? Кроме того, прогнозирование на 1 символ также говорит нам не уменьшать A+M в A, так как это может привести к неизбежной синтаксической ошибке после чтения *3?

Источник

2 ответа

Решение

Проблема, которую вы описываете, это проблема с созданием LR(0) парсеры - то есть восходящие парсеры, которые не обращают внимания на символы помимо текущего, который они анализируют. Описанная вами грамматика не является LR(0) грамматика, поэтому вы сталкиваетесь с проблемами, когда пытаетесь разобрать ее без предвидения. Похоже, что это LR(1)однако, посмотрев на входе 1 символ вперед, вы можете легко определить, следует ли сдвигать или уменьшать. В этом случае LR(1) парсер будет смотреть вперед, когда у него будет 1 в стеке, увидеть, что следующий символ +и понять, что это не должно уменьшать прошлое A (поскольку это единственное, что может привести к тому, что оно все равно будет соответствовать правилу с + во второй позиции).

Интересное свойство LR грамматика для любой грамматики, которая LR(k) за k>1можно построить LR(1) грамматика, которая эквивалентна. Тем не менее, то же самое не распространяется вплоть до LR(0) - есть много грамматик, которые не могут быть преобразованы в LR(0),

Смотрите здесь для более подробной информации о LR(k)-ness:

http://en.wikipedia.org/wiki/LR_parser

Источник

Я не совсем уверен в алгоритме синтаксического анализа Yacc / Bison и в тех случаях, когда он предпочитает сдвиг по сравнению с сокращением, однако я знаю, что Bison поддерживает синтаксический анализ LR(1), что означает, что он имеет жетон предпросмотра. Это означает, что токены не передаются в стек сразу. Скорее они ждут, пока не произойдет больше никаких сокращений. Затем, если сдвиг следующего токена имеет смысл, он применяет эту операцию.

Прежде всего, в вашем случае, если вы оцениваете 1 + 2, он сместится на 1. Это уменьшит этот токен до A, потому что токен "+" указывает, что это единственный действительный курс. Поскольку сокращений больше нет, он сместит токен "+" в стек и удержит 2 в качестве заглядывания. Это сместит 2 и уменьшит до M, так как A + M производит A, и выражение завершено.

Источник
Другие вопросы по тегам