Канонический LR-парсер (также называемый LR(1)-парсером ) — это тип алгоритма синтаксического анализа снизу вверх, используемый в информатике для анализа и обработки языков программирования . Он основан на технике синтаксического анализа LR , которая означает «слева направо, самый правый вывод в обратном порядке».
Формально канонический парсер LR — это парсер LR(k) для k=1 , т. е. с одним опережающим терминалом . Особым свойством этого парсера является то, что любая грамматика LR(k) с k>1 может быть преобразована в грамматику LR(1). [1] Однако для уменьшения k требуются обратные подстановки, и по мере увеличения обратных подстановок грамматика может быстро стать большой, повторяющейся и трудной для понимания. LR(k) может обрабатывать все детерминированные контекстно-свободные языки . [1] В прошлом этот парсер LR(k) избегали из-за его огромных требований к памяти в пользу менее мощных альтернатив, таких как парсер LALR и LL(1) . Однако в последнее время «минимальный парсер LR(1)», требования к пространству которого близки к парсерам LALR [ требуется ссылка ] , предлагается несколькими генераторами парсеров.
Как и большинство парсеров, парсер LR(1) автоматически генерируется компиляторами-компиляторами, такими как GNU Bison , MSTA, Menhir, [2] HYACC, [3] и LRSTAR. [4]
В 1965 году Дональд Кнут изобрел парсер LR(k) ( слева направо, самый правый парсер вывода ), тип парсера сдвига-сведения , как обобщение существующих парсеров предшествования . Этот парсер имеет потенциал распознавания всех детерминированных контекстно-свободных языков и может производить как левые, так и правые выводы операторов, встречающихся во входном файле. Кнут доказал, что он достигает своей максимальной мощности распознавания языка при k=1, и предоставил метод преобразования грамматик LR(k), k > 1 в грамматики LR(1). [1]
Канонические парсеры LR(1) имеют практический недостаток в виде огромных требований к памяти для их внутреннего представления парсер-таблицы. В 1969 году Фрэнк ДеРемер предложил две упрощенные версии парсера LR, названные LALR и SLR . Эти парсеры требуют гораздо меньше памяти, чем канонические парсеры LR(1), но имеют немного меньшую мощность распознавания языка. [5] Парсеры LALR(1) были наиболее распространенными реализациями парсера LR.
Однако новый тип парсера LR(1), который некоторые называют «Минимальным парсером LR(1)», был представлен в 1977 году Дэвидом Пейджером [6], который показал, что можно создавать парсеры LR(1), чьи требования к памяти соперничают с требованиями парсеров LALR(1). Недавно [ когда? ] некоторые генераторы парсеров предлагают парсеры Minimal LR(1), которые не только решают проблему требований к памяти, но и загадочную проблему конфликта, присущую генераторам парсеров LALR(1). [ необходима цитата ] Кроме того, парсеры Minimal LR(1) могут использовать действия сдвига-свертки, что делает их быстрее, чем канонические парсеры LR(1).
Анализатор LR(1) является детерминированным автоматом , и как таковой его работа основана на статических таблицах переходов состояний . Они кодифицируют грамматику языка, который он распознает, и обычно называются «таблицами анализа».
Таблицы синтаксического анализа LR(1) параметризованы с помощью терминала просмотра вперед. Простые таблицы синтаксического анализа, такие как те, которые используются LR(0) -анализатором, представляют собой правила грамматики в форме
что означает, что если мы имеем вход A, за которым следует B , то мы сократим пару до A1 независимо от того, что последует. После параметризации такого правила с помощью просмотра вперед мы имеем:
что означает, что сокращение теперь будет выполняться только в том случае, если терминалом просмотра вперед является . Это позволяет использовать более богатые языки, где простое правило может иметь разные значения в зависимости от контекста просмотра вперед. Например, в грамматике LR(1) все следующие правила выполняют разное сокращение, несмотря на то, что основаны на одной и той же последовательности состояний.
Это не было бы верно, если бы не учитывался опережающий терминал. Ошибки анализа можно определить без необходимости анализатору читать весь ввод, объявив некоторые правила ошибками. Например,
может быть объявлено ошибкой, что приведет к остановке парсера. Это означает, что информация о просмотре вперед может также использоваться для обнаружения ошибок, как в следующем примере:
В этом случае AB будет сокращен до A1, если опережающий просмотр равен a, b или c, и будет выдано сообщение об ошибке, если опережающий просмотр равен d.
Опережающий просмотр также может быть полезен при принятии решения о том, когда следует сократить правило. Опережающий просмотр может помочь избежать сокращения определенного правила, если опережающий просмотр недействителен, что, вероятно, означало бы, что текущее состояние должно быть объединено со следующим, а не с предыдущим состоянием. Это означает в следующем примере
последовательность может быть сокращена до
вместо
если предварительный просмотр после того, как анализатор перешел в состояние B, был неприемлем, т.е. не существовало правила перехода. Сокращения могут быть получены непосредственно из терминала, как в
что позволяет отображать несколько последовательностей.
LR(1) парсеры имеют требование, чтобы каждое правило было выражено в полной LR(1) манере, т.е. последовательность из двух состояний с определенным просмотром вперед. Это делает простые правила, такие как
требуя большого количества искусственных правил, которые по сути перечисляют комбинации всех возможных состояний и терминалов просмотра вперед, которые могут следовать. Похожая проблема возникает при реализации правил без просмотра вперед, таких как
где все возможные опережающие просмотры должны быть перечислены. Вот почему парсеры LR(1) не могут быть реализованы на практике без значительной оптимизации памяти. [6]
Таблицы синтаксического анализа LR(1) построены так же, как и таблицы синтаксического анализа LR(0), с той разницей, что каждый элемент содержит опережающий терминал . Это означает, в отличие от парсеров LR(0), что может быть выполнено другое действие, если за обрабатываемым элементом следует другой терминал.
Начиная с правил производства языка, сначала должны быть определены наборы элементов для этого языка. Проще говоря, набор элементов — это список правил производства, частью которых может быть текущий обрабатываемый символ. Набор элементов имеет однозначное соответствие состоянию парсера, в то время как элементы внутри набора вместе со следующим символом используются для определения того, какие переходы состояний и действия парсера должны быть применены. Каждый элемент содержит маркер, чтобы отметить, в какой точке текущий обрабатываемый символ появляется в правиле, которое представляет элемент. Для парсеров LR(1) каждый элемент относится к терминалу просмотра вперед, поэтому терминал просмотра вперед также отмечен внутри каждого элемента.
Например, предположим, что язык состоит из терминальных символов «n», «+», «(», «)», нетерминалов «E», «T», начального правила «S» и следующих правил вывода:
Наборы элементов будут генерироваться по аналогии с процедурой для парсеров LR(0). Набор элементов 0, представляющий начальное состояние, будет создан из начального правила:
Точка '•' обозначает маркер текущей позиции разбора в этом правиле. Ожидаемый терминал просмотра вперед для применения этого правила указан после запятой. Знак '$' используется для обозначения ожидаемого 'конца ввода', как и в случае с начальным правилом.
Однако это не полный набор элементов 0. Каждый набор элементов должен быть «закрыт», что означает, что все правила производства для каждого нетерминала, следующего за «•», должны быть рекурсивно включены в набор элементов, пока все эти нетерминалы не будут обработаны. Результирующий набор элементов называется замыканием набора элементов, с которого мы начали.
Для LR(1) для каждого правила производства элемент должен быть включен для каждого возможного терминала просмотра вперед, следующего за правилом. Для более сложных языков это обычно приводит к очень большим наборам элементов, что является причиной больших требований к памяти парсеров LR(1).
В нашем примере начальный символ требует нетерминал 'E', который в свою очередь требует 'T', поэтому все правила производства появятся в наборе элементов 0. Сначала мы игнорируем проблему поиска предпросмотров и просто рассматриваем случай LR(0), элементы которого не содержат предпросмотров терминалов. Таким образом, набор элементов 0 (без предпросмотров) будет выглядеть следующим образом:
Для определения опережающих терминалов используются так называемые наборы FIRST и FOLLOW. FIRST(A) — это набор терминалов, которые могут появляться в качестве первого элемента любой цепочки правил, соответствующих нетерминалу A. FOLLOW(I) элемента I [A → α • B β, x] — это набор терминалов, которые могут появляться сразу после нетерминала B, где α, β — произвольные строки символов, а x — произвольный опережающий терминал. FOLLOW(k,B) набора элементов k и нетерминала B — это объединение последующих наборов всех элементов в k, где за '•' следует B. Наборы FIRST можно определить непосредственно из замыканий всех нетерминалов в языке, в то время как наборы FOLLOW определяются из используемых элементов наборов FIRST.
В нашем примере, как можно убедиться из полного списка наборов элементов ниже, первыми наборами являются:
В наборе элементов 0 можно обнаружить следующие наборы:
Из этого можно создать полный набор элементов 0 для анализатора LR(1), создав для каждого элемента в наборе элементов LR(0) одну копию для каждого терминала в последующем наборе нетерминала LHS. Каждый элемент последующего набора может быть допустимым опережающим терминалом:
Остальные наборы предметов можно создать по следующему алгоритму
В этом примере мы получаем еще 5 наборов из набора элементов 0, набора элементов 1 для нетерминала E, набора элементов 2 для нетерминала T, набора элементов 3 для терминала n, набора элементов 4 для терминала '+' и набора элементов 5 для '('.
Набор предметов 1 (E):
Набор предметов 2 (T):
Набор предметов 3 (сущ.):
Набор предметов 4 ('+'):
Набор предметов 5 ('('):
Из наборов элементов 2, 4 и 5 будет создано еще несколько наборов элементов. Полный список довольно длинный и поэтому не будет здесь приведен. Подробную обработку LR(k) этой грамматики можно найти, например, в [1].
Опережающий просмотр элемента LR(1) используется напрямую только при рассмотрении действий сокращения (т. е. когда маркер • находится в правом конце).
Ядром элемента LR(1) [S → a A • B e, c] является элемент LR(0) S → a A • B e. Различные элементы LR(1) могут иметь одно и то же ядро.
Например, в наборе предметов 2
парсер должен выполнить редукцию [E → T], если следующим символом будет '$', но выполнить сдвиг, если следующим символом будет '+'. Обратите внимание, что парсер LR(0) не сможет принять это решение, поскольку он рассматривает только ядро элементов и, таким образом, сообщит о конфликте сдвига/свертки.
Состояние, содержащее [A → α • X β, a], перейдет в состояние, содержащее [A → α X • β, a] с меткой X.
Согласно Гото, каждое состояние имеет переходы.
Если [A → α • b β, a] находится в состоянии I k и I k переходит в состояние I m с меткой b, то мы добавляем действие
Если [A→α •, a] находится в состоянии I k , то мы добавляем действие