Парсеры
SLR, LALR и LR могут быть реализованы с использованием одного и того же механизма, управляемого таблицами.
По сути, алгоритм синтаксического анализа собирает следующий входной токен T и обращается к текущему состоянию S (и соответствующим таблицам предпросмотра, GOTO и сокращения), чтобы решить, что делать:
- SHIFT: если текущая таблица говорит SHIFT на токене T, пара (S, T) помещается в стек разбора, состояние изменяется в соответствии с тем, что таблица GOTO говорит для текущего токена (например, GOTO (T)), другой входной токен T 'выбирается, и процесс повторяется
- УМЕНЬШЕНИЕ: В каждом штате есть 0, 1 или много возможных сокращений, которые могут произойти в этом состоянии. Если синтаксическим анализатором является LR или LALR, токен проверяется на основе наборов предварительного просмотра для всех допустимых сокращений для состояния. Если токен совпадает с набором преднамеренного сокращения для правила грамматики G = R1 R2 .. Rn, происходит уменьшение стека и сдвиг: вызывается семантическое действие для G, стек выталкивается n (из Rn) раз, пара ( S, G) помещается в стек, новое состояние S 'устанавливается в GOTO (G), и цикл повторяется с тем же маркером T. Если синтаксический анализатор является синтаксическим анализатором SLR, существует не более одного правила сокращения для состояние и поэтому действие сокращения может быть выполнено вслепую без поиска, чтобы увидеть, какое сокращение применяется. Для парсера SLR полезно знать, есть ли сокращение или нет; легко сказать, записывает ли каждое состояние количество сокращений, связанных с ним, и этот счет необходим для практических версий L (AL) R в любом случае.
- ОШИБКА: если ни SHIFT, ни REDUCE невозможны, объявляется синтаксическая ошибка.
Итак, если они все используют один и тот же механизм, какой смысл?
Предполагаемое значение в SLR - это его простота в реализации; вам не нужно сканировать возможные сокращения, проверяя наборы предварительного просмотра, потому что их самое большее, и это единственное жизнеспособное действие, если нет состояний SHIFT, выходящих из состояния. То, какое сокращение применяется, может быть привязано конкретно к государству, так что механизм синтаксического анализа SLR не должен охотиться за ним. На практике парсеры L (AL) R обрабатывают полезно больший набор языков, и для их реализации так мало дополнительной работы, что никто не реализует SLR, кроме как для академического упражнения.
Разница между LALR и LR связана с таблицей генератора . Генераторы синтаксического анализатора LR отслеживают все возможные сокращения от определенных состояний и их точный предварительный набор; в итоге вы получите состояния, в которых каждое сокращение связано с его точным прогнозным набором из левого контекста. Это имеет тенденцию создавать довольно большие наборы состояний. Генераторы синтаксических анализаторов LALR готовы объединять состояния, если таблицы GOTO и наборы элементов поиска для сокращений совместимы и не конфликтуют; это приводит к значительно меньшему количеству состояний за счет невозможности различить определенные последовательности символов, которые может различать LR. Таким образом, парсеры LR могут анализировать больший набор языков, чем парсеры LALR, но имеют намного большие таблицы парсеров. На практике можно найти грамматики LALR, которые достаточно близки к целевым языкам, так что размер конечного автомата стоит оптимизировать; места, где парсер LR был бы лучше, обрабатываются специальной проверкой вне парсера.
Итак: все трое используют один и тот же механизм. SLR «легок» в том смысле, что вы можете проигнорировать чуть-чуть машины, но это не стоит хлопот. LR анализирует более широкий набор языков, но таблицы состояний имеют тенденцию быть довольно большими. Это оставляет LALR в качестве практического выбора.
Сказав все это, стоит знать, что GLR-парсеры могут анализировать любой контекстно-свободный язык, используя более сложную технику , но точно такие же таблицы (включая уменьшенную версию, используемую LALR). Это означает, что GLR строго более мощный, чем LR, LALR и SLR; в значительной степени, если вы можете написать стандартную грамматику BNF, GLR будет анализировать в соответствии с ней. Разница в механизме заключается в том, что GLR желает попробовать несколько разборов, когда есть конфликты между таблицей GOTO и / или наборами предвкушения. (То, как GLR делает это эффективно, является чистым гением [не моим], но не вписывается в этот пост SO).
Это для меня чрезвычайно полезный факт. Я строю анализаторы программ, и преобразователи кода и анализаторы необходимы, но "неинтересны"; интересная работа - это то, что вы делаете с проанализированным результатом, поэтому основное внимание уделяется выполнению работы после разбора. Использование GLR означает, что я могу относительно легко создавать рабочие грамматики по сравнению со взломом грамматики, чтобы получить LALR-форму. Это очень важно, когда вы пытаетесь работать с неакадемическими языками, такими как C ++ или Fortran, где вам буквально нужны тысячи правил для правильной работы со всем языком, и вы не хотите тратить свою жизнь на попытки взломать грамматические правила, чтобы соответствовать ограничениям LALR (или даже LR).
В качестве своего рода известного примера, C ++ считается чрезвычайно сложным для анализа ... парнями, занимающимися анализом LALR. C ++ легко анализировать, используя механизм GLR, используя в значительной степени правила, приведенные в конце справочного руководства по C ++. (У меня есть именно такой синтаксический анализатор, и он обрабатывает не только ванильный C ++, но и различные диалекты вендоров. Это возможно только на практике, потому что мы используем анализатор GLR, ИМХО).
[РЕДАКТИРОВАТЬ Ноябрь 2011: Мы расширили наш синтаксический анализатор для обработки всего C ++ 11. GLR сделал это намного проще. РЕДАКТИРОВАТЬ Авг 2014: Теперь обрабатывает все C ++ 17. Ничего не сломалось и не стало хуже, GLR по-прежнему кошачий мяукан.]