Shift-reduce: когда прекратить уменьшать?
Я пытаюсь узнать о восходящем синтаксическом анализе. Предположим, что у нас есть следующая грамматика, с помощью рекурсивных правил, которые осуществляют порядок операций, вдохновленных 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, или ЧИСЛО, и это все еще будет допустимо в том смысле, что любая комбинация была бы корректным представлением текста. Как синтаксический анализатор "знает" для создания его
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 см. Здесь:
Я не совсем уверен в алгоритме синтаксического анализа Yacc / Bison и о том, когда он предпочитает сдвиг сокращению, однако я знаю, что Bison поддерживает синтаксический анализ LR (1) что означает, что у него есть предварительный токен. Это означает, что токены не сразу попадают в стек. Скорее они ждут, пока сокращение больше не произойдет. Затем, если сдвиг следующего токена имеет смысл, он применяет эту операцию.
Прежде всего, в вашем случае, если вы оцениваете 1 + 2, он сдвинется на 1. Это уменьшит этот токен до A, потому что прогнозируемый токен «+» указывает, что это единственный допустимый курс. Поскольку сокращений больше нет, он сдвинет токен «+» в стек и удержит 2 в качестве опережающего просмотра. Он сдвинет 2 и уменьшится до M, поскольку A + M производит A и выражение завершено.