Канонические и минимальные LR(1) парсеры: обзор и развитие
Canonical LR parser
Канонический LR-парсер: алгоритм синтаксического анализа языков программирования. LR(1) грамматики, преимущества и недостатки, преобразования грамматик.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Канонический LR-парсер (также называемый LR(1)-парсер) — это тип алгоритма синтаксического анализа снизу вверх, используемый в информатике для анализа и обработки языков программирования. Он основан на технике LR-парсинга, которая расшифровывается как "чтение слева направо, построение правостороннего вывода в обратном порядке". Формально, канонический LR-парсер является LR(k)-парсером для k=1, то есть с одним символом предварительного просмотра. Особенность этого парсера заключается в том, что любая LR(k)-грамматика с k>1 может быть преобразована в LR(1)-грамматику. Однако для уменьшения k требуются обратные подстановки, и по мере их увеличения грамматика может быстро стать большой, повторяющейся и сложной для понимания. LR(k) может обрабатывать все детерминированные контекстно-свободные языки. HYACC и LRSTAR.
A canonical LR parser (also called a LR(1) parser) is a type of bottom up parsing algorithm used in computer science to analyze and process programming languages. It is based on the LR parsing technique, which stands for "left to right, rightmost derivation in reverse." Formally, a canonical LR parser is an LR(k) parser for k=1, i. e. with a single lookahead terminal. The special attribute of this parser is that any LR(k) grammar with k>1 can be transformed into an LR(1) grammar. However, back substitutions are required to reduce k and as back substitutions increase, the grammar can quickly become large, repetitive and hard to understand. LR(k) can handle all deterministic context free languages. HYACC, and LRSTAR.
История
В 1965 году Дональд Кнут изобрел LR(k)-парсер (парсер, выполняющий анализ слева направо с использованием правостороннего вывода), тип парсера сдвиг-сокращение, как обобщение существующих парсеров прецедентов. Этот парсер обладает потенциалом распознавания всех детерминированных контекстно-свободных языков и способен генерировать как левые, так и правые выводы выражений, встречающихся во входном файле. Кнут доказал, что максимальная мощность распознавания языка достигается при k=1, и предложил метод преобразования LR(k)-грамматик, где k > 1, в LR(1)-грамматики. LALR(1)-парсеры являются наиболее распространенной реализацией LR-парсера. Однако в 1977 году Дэвид Пейджер представил новый тип LR(1)-парсера, который некоторые называют "минимальным LR(1)-парсером", и показал, что LR(1)-парсеры могут быть созданы с требованиями к памяти, сопоставимыми с требованиями LALR(1)-парсеров. В последнее время некоторые генераторы парсеров предлагают минимальные LR(1)-парсеры, которые не только решают проблему с требованиями к памяти, но и устраняют проблему конфликтов, свойственную генераторам LALR(1)-парсеров. Кроме того, минимальные LR(1)-парсеры могут использовать действия сдвиг-сокращение, что делает их быстрее, чем канонические LR(1)-парсеры.
In 1965 Donald Knuth invented the LR(k) parser (Left to right, Rightmost derivation parser) a type of shift reduce parser, as a generalization of existing precedence parsers. This parser has the potential of recognizing all deterministic context free languages and can produce both left and right derivations of statements encountered in the input file. Knuth proved that it reaches its maximum language recognition power for k=1 and provided a method for transforming LR(k), k > 1 grammars into LR(1) grammars. LALR(1) parsers have been the most common implementations of the LR Parser. However, a new type of LR(1) parser, some people call a "Minimal LR(1) parser" was introduced in 1977 by David Pager who showed that LR(1) parsers can be created whose memory requirements rival those of LALR(1) parsers. Recently, some parser generators are offering Minimal LR(1) parsers, which not only solve the memory requirement problem, but also the mysterious conflict problem inherent in LALR(1) parser generators. In addition, Minimal LR(1) parsers can use shift reduce actions, which makes them faster than Canonical LR(1) parsers.
Создание таблиц анализа LR(1)
Таблицы разбора LR(1) строятся аналогично таблицам разбора LR(0), с той модификацией, что каждый элемент содержит символ предпросмотра (lookahead). Это означает, что в отличие от LR(0)-парсеров, может быть выполнено другое действие, если за обрабатываемым элементом следует другой терминальный символ.
LR(1) parsing tables are constructed in the same way as LR(0) parsing tables with the modification that each Item contains a lookahead terminal. This means, contrary to LR(0) parsers, a different action may be executed, if the item to process is followed by a different terminal.