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

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

5 голосов
/ 13 апреля 2010

Я пытаюсь узнать о разборе сдвига-уменьшения. Предположим, у нас есть следующая грамматика, использующая рекурсивные правила, обеспечивающие порядок операций, основанный на грамматике 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 ]

5 голосов
/ 13 апреля 2010

Проблема, которую вы описываете, связана с созданием парсеров 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

1 голос
/ 13 апреля 2010

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

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

...