Введение
Тип парсера в информатике
В информатике, LALR-парсер (look ahead, left-to-right, rightmost derivation parser – просмотр вперед, слева направо, парсер на основе правостороннего вывода) является частью процесса компиляции, где текст, читаемый человеком, преобразуется в структурированное представление для обработки компьютерами. LALR-парсер – это программный инструмент для обработки (разбора) текста в специфическое внутреннее представление, с которым могут работать другие программы, такие как компиляторы. Этот процесс происходит в соответствии с набором производственных правил, заданных формальной грамматикой для компьютерного языка. LALR-парсер является упрощенной версией канонического LR-парсера. LALR-парсер был изобретен Фрэнком ДеРемером в его докторской диссертации 1969 года «Практические трансляторы для языков LR(k)», где он рассматривал практические трудности, возникавшие в то время при реализации LR(1)-парсеров. Он показал, что LALR-парсер обладает большей способностью распознавать языки, чем LR(0)-парсер, при этом требуя такого же количества состояний, как и LR(0)-парсер для языка, который может быть распознан обоими парсерами. Это делает LALR-парсер эффективной альтернативой LR(1)-парсеру для языков, которые могут быть обработаны LALR-парсером. Также было доказано, что существуют языки LR(1), которые не являются LALR-языками. Несмотря на это ограничение, мощности LALR-парсера достаточно для многих распространенных компьютерных языков, включая Java, хотя эталонные грамматики для многих языков не соответствуют требованиям LALR из-за неоднозначности. В 1982 году ДеРемер и Том Пеннелло опубликовали алгоритм, который генерировал высокоэффективные LALR-парсеры с точки зрения использования памяти. LALR-парсеры могут быть автоматически сгенерированы из грамматики с помощью генератора LALR-парсеров, такого как Yacc или GNU Bison. Автоматически сгенерированный код может быть дополнен вручную написанным кодом для расширения возможностей полученного парсера.
История
В 1965 году Дональд Кнут изобрел LR-парсер (слева направо, правосторонний вывод). LR-парсер способен распознавать любой детерминированный контекстно-свободный язык за линейно ограниченное время. Правосторонний вывод требует очень больших затрат памяти, и реализация LR-парсера была непрактичной из-за ограниченных возможностей памяти компьютеров того времени. Чтобы решить эту проблему, в 1969 году Фрэнк ДеРемер предложил две упрощенные версии LR-парсера, а именно Look Ahead LR (LALR) и Simple LR parser (SLR), которые требовали значительно меньше памяти, но при этом обладали меньшей мощностью распознавания языка, причём LALR-парсер был наиболее мощной альтернативой. В 1977 году были изобретены оптимизации памяти для LR-парсера, но он всё равно оставался менее эффективным по использованию памяти, чем упрощённые альтернативы. В 1979 году Фрэнк ДеРемер и Том Пеннелло объявили о серии оптимизаций для LALR-парсера, которые должны были ещё больше повысить его эффективность по использованию памяти. Их работа была опубликована в 1982 году, но не получила практического применения. Как и другие типы LR-парсеров, LALR-парсер достаточно эффективно находит единственный правильный синтаксический анализ снизу вверх за один проход слева направо по входному потоку, поскольку ему не требуется использовать возврат к предыдущим шагам (backtracking). Являясь по определению парсером с просмотром, он всегда использует просмотр, причём LALR(1) является наиболее распространённым вариантом.
ЛЛ-парасеры
Парсеры LALR(j) несравнимы с парсерами LL(k): для любых j и k, больших 0, существуют грамматики LALR(j), которые не являются грамматиками LL(k), и наоборот. Более того, не существует алгоритма, позволяющего определить, является ли заданная LL(1)-грамматика LALR(k)-грамматикой для любого k.