Канонический парсер LR - Canonical LR parser

В Информатика, а канонический парсер LR или же Парсер LR (1) является 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, МСТА, Менгир,[2] HYACC,[3].

История

В 1965 г. Дональд Кнут изобрел парсер LR (k) (Lслева направо, рсамое правильное происхождение парсер) тип парсер сдвиг-уменьшение, как обобщение существующих парсеры приоритета. Этот синтаксический анализатор имеет потенциал распознавания всех детерминированных контекстно-свободных языков и может производить как левые, так и правые производные операторов, встречающихся во входном файле. Кнут доказал, что он достигает максимальной мощности распознавания языка при k = 1, и предоставил метод преобразования грамматик LR (k), k> 1 в грамматики LR (1).[1]

Канонические парсеры LR (1) имеют практический недостаток в виде огромных требований к памяти для их внутреннего представления таблицы парсеров. В 1969 году Франк ДеРемер предложил две упрощенные версии парсера LR, названные LALR и SLR. Эти парсеры требуют гораздо меньше памяти, чем парсеры Canonical LR (1), но имеют немного меньшую способность распознавания языка.[4] Парсеры LALR (1) были наиболее распространенными реализациями LR Parser.

Однако новый тип синтаксического анализатора LR (1), который некоторые называют «минимальным синтаксическим анализатором LR (1)», был представлен в 1977 году Дэвидом Пейджером.[5] кто показал, что могут быть созданы парсеры LR (1), требования к памяти которых не уступают требованиям парсеров LALR (1). Недавно[когда? ], некоторые генераторы парсеров предлагают парсеры Minimal LR (1), которые не только решают проблему требований к памяти, но и проблему загадочного конфликта, присущую генераторам парсеров LALR (1).[нужна цитата ] Кроме того, синтаксические анализаторы Minimal LR (1) могут использовать действия по уменьшению сдвига, что делает их быстрее, чем синтаксические анализаторы Canonical LR (1).

Обзор

Парсер LR (1) - это детерминированный автомат и поэтому его работа основана на статических таблицы перехода состояний. Они кодируют грамматику распознаваемого языка и обычно называются «таблицами синтаксического анализа».

Таблицы синтаксического анализа синтаксического анализатора LR (1) параметризованы с помощью опережающего терминала. Простые таблицы синтаксического анализа, подобные тем, которые используются LR (0) парсер представляет грамматические правила в форме

А1 → А, В

что означает, что если мы выйдем из состояния А заявить B тогда мы перейдем к состоянию A1[непонятный ]. После параметризации такого правила с опережением мы имеем:

A1 → A, B, а

что означает, что переход теперь будет выполняться, только если опережающий терминал а. Это позволяет использовать более богатые языки, где простое правило может иметь различное значение в зависимости от контекста опережающего просмотра. Например, в грамматике LR (1) все следующие правила переходят в другое состояние, несмотря на то, что они основаны на одной и той же последовательности состояний.

A1 → A, B, а
A2 → A, B, b
A3 → A, B, c
A4 → A, B, d

То же самое было бы неверно, если бы опережающий терминал не принимался во внимание. Ошибки синтаксического анализа можно определить без необходимости считывания парсером всего ввода, объявив некоторые правила ошибками. Например,

E1 → B, C, d

может быть объявлен ошибкой, вызывающей остановку анализатора. Это означает, что предварительную информацию также можно использовать для обнаружения ошибок, как в следующем примере:

A1 → A, B, а
A1 → A, B, b
A1 → A, B, c
E1 → A, B, d

В этом случае A, B будут уменьшены до A1, когда опережающий просмотр равен a, b или c, и будет сообщено об ошибке, когда опережающий просмотр будет d.

Предварительный просмотр также может быть полезен при принятии решения о сокращении правила. Предварительный просмотр может помочь избежать сокращения конкретного правила, если предварительный просмотр недействителен, что, вероятно, означает, что текущее состояние следует объединить со следующим, а не с предыдущим состоянием. Это означает, что в следующем примере

  • Последовательность состояний: A, B, C
  • Правила:
А1 → А, В
A2 → B, C

последовательность состояний может быть уменьшена до

А, А2

вместо

A1, C

если опережающий просмотр после того, как синтаксический анализатор перешел в состояние B, был неприемлем, т.е. не существовало правила перехода. Состояния могут быть созданы непосредственно из терминала, как в

X → y

что позволяет отображать последовательности состояний.

Парсеры LR (1) требуют, чтобы каждое правило было выражено полным LR (1) способом, то есть последовательностью двух состояний с определенным опережением. Это делает простые правила, такие как

X → y

требуя множества искусственных правил, которые по существу перечисляют комбинации всех возможных состояний и опережающих терминалов, которые могут следовать. Аналогичная проблема возникает при реализации правил без предварительного просмотра, таких как

А1 → А, В

где должны быть перечислены все возможные опережающие просмотры. По этой причине парсеры LR (1) не могут быть практически реализованы без значительной оптимизации памяти.[5]

Создание таблиц синтаксического анализа LR (1)

Таблицы синтаксического анализа LR (1) строятся так же, как Таблицы синтаксического анализа LR (0) с модификацией, что каждый Элемент содержит прогноз Терминал. Это означает, что, в отличие от парсеров LR (0), может быть выполнено другое действие, если за обрабатываемым элементом следует другой терминал.

Элементы парсера

Начиная с правила производства языка, сначала необходимо определить наборы элементов для этого языка. Проще говоря, набор элементов - это список производственных правил, частью которых может быть текущий обрабатываемый символ. Набор элементов имеет однозначное соответствие состоянию синтаксического анализатора, в то время как элементы в наборе вместе со следующим символом используются для принятия решения о том, какие переходы между состояниями и действие синтаксического анализатора должны применяться. Каждый элемент содержит маркер, чтобы отметить, в какой момент обрабатываемый в данный момент символ появляется в правиле, которое представляет элемент. Для парсеров LR (1) каждый элемент специфичен для терминала просмотра вперед, поэтому терминал просмотра вперед также отмечен внутри каждого элемента.

Например, предположим, что язык состоит из терминальных символов 'n', '+', '(', ')', нетерминалов 'E', 'T', начального правила 'S' и следующих производственных правил:

S → E
E → T
E → (E)
Т → п
Т → + Т
Т → Т + п

Наборы элементов будут сгенерированы аналогично процедуре для парсеров LR (0). Набор элементов 0, который представляет начальное состояние, будет создан из начального правила:

[S → • E, $]

Точка «•» обозначает маркер текущей позиции синтаксического анализа в этом правиле. Ожидаемый терминал опережающего просмотра для применения этого правила отмечается после запятой. Знак «$» используется для обозначения «ожидается конец ввода», как и в случае правила запуска.

Однако это не полный набор элементов 0. Каждый набор элементов должен быть «закрытым», что означает, что все производственные правила для каждого нетерминала, следующего за символом «•», должны быть рекурсивно включены в набор элементов до тех пор, пока не будут обработаны все эти нетерминалы. Результирующий набор элементов называется закрытием набора элементов, с которого мы начали.

Для LR (1) для каждого производственного правила должен быть включен элемент для каждого возможного опережающего терминала, следующего за правилом. Для более сложных языков это обычно приводит к очень большим наборам элементов, что является причиной больших требований к памяти парсеров LR (1).

В нашем примере для начального символа требуется нетерминал «E», который, в свою очередь, требует «T», поэтому все производственные правила появятся в наборе элементов 0. Сначала мы игнорируем проблему поиска опережающих просмотров и просто рассмотрим случай LR (0), элементы которого не содержат опережающих терминалов. Таким образом, набор элементов 0 (без просмотра вперед) будет выглядеть так:

[S → • E]
[E → • T]
[E → • (E)]
[T → • n]
[T → • + T]
[T → • T + n]

Наборы FIRST и FOLLOW

Для определения опережающих терминалов используются так называемые наборы FIRST и FOLLOW. FIRST (A) - это набор терминалов, который может появляться как первый элемент любой цепочки правил, соответствующих нетерминальному A. FOLLOW (I) элемента I [A → α • B β, x] - множество терминалов, которые могут появиться сразу после нетерминальный B, где α, β - произвольные строки символов, а x - произвольный упреждающий терминал. FOLLOW (k, B) набора элементов k и нетерминала B является объединением следующих наборов всех элементов в k, где за символом «•» следует B. ПЕРВЫЕ множества могут быть определены непосредственно из замыканий всех нетерминалов в язык, в то время как наборы FOLLOW определяются из элементов, используемых в наборах FIRST.

В нашем примере, как видно из полного списка наборов элементов ниже, первые наборы:

ПЕРВЫЙ (S) = {n, '+', '('}
ПЕРВЫЙ (E) = {n, '+', '('}
ПЕРВЫЙ (T) = {n, '+'}

Определение опережающих терминалов

В наборе элементов 0 можно найти следующие наборы:

ПОСЛЕДУЮЩИЕ (0; S) = {$}
ПОСЛЕДУЮЩИЕ (0; E) = {$, ')'}
ПОСЛЕДУЮЩИЕ (0, T) = {$, '+', ')'}

Из этого может быть создан полный набор элементов 0 для анализатора LR (1) путем создания для каждого элемента в наборе элементов LR (0) по одной копии для каждого терминала в следующем наборе нетерминала LHS. Каждый элемент следующего набора может быть допустимым опережающим терминалом:

[S → • E, $]
[E → • T, $]
[E → • T,)]
[E → • (E), $]
[E → • (E),)]
[T → • n, $]
[T → • n, +]
[T → • n,)]
[T → • + T, $]
[T → • + T, +]
[T → • + T,)]
[T → • T + n, $]
[T → • T + n, +]
[T → • T + n,)]

Создание новых наборов предметов

Остальные наборы предметов можно создать по следующему алгоритму

1. Для каждого терминального и нетерминального символа A, появляющегося после символа «•» в каждом уже существующем наборе элементов k, создайте новый набор элементов m, добавив к m все правила k, где за символом «•» следует A, но только если m не будет таким же, как уже существующий элемент, установленный после шага 3.
2. сдвиньте все '•' для каждого правила в новом элементе, установите один символ вправо
3. создать закрытие нового набора элементов
4. Повторите действия с шага 1 для всех вновь созданных наборов предметов, пока новые наборы не перестанут появляться.

В этом примере мы получаем еще 5 наборов из набора элементов 0, набора элементов 1 для нетерминала E, набора элементов 2 для нетерминала T, набора элементов 3 для терминала n, набора элементов 4 для терминала '+' и набора элементов 5 для '(' .

Набор предметов 1 (E):

[S → E •, $]

Набор предметов 2 (T):

[E → T •, $]
[T → T • + n, $]
[T → T • + n, +]
·
·
·

Набор предметов 3 (n):

[T → n •, $]
[T → n •, +]
[T → n •,)]

Набор предметов 4 ('+'):

[T → + • T, $]
[T → + • T, +]
[T → • n, $]
[T → • n, +]
[T → • + T, $]
[T → • + T, +]
[T → • T + n, $]
[T → • T + n, +]
·
·
·

Набор предметов 5 ('('):

[E → (• E), $]
[E → • T,)]
[E → • (E),)]
[T → • n,)]
[T → • n, +]
[T → • + T,)]
[T → • + T, +]
[T → • T + n,)]
[T → • T + n, +]
·
·
·

Из наборов 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 •, $]
[T → T • + n, $]
[T → T • + n, +]

синтаксический анализатор должен выполнить сокращение [E → T], если следующим символом является '$', но выполнить сдвиг, если следующий символ - '+'. Обратите внимание, что синтаксический анализатор LR (0) не сможет принять это решение, поскольку он учитывает только ядро ​​элементов и, таким образом, сообщит о конфликте сдвига / уменьшения.

Состояние, содержащее [A → α • X β, a], перейдет в состояние, содержащее [A → α X • β, a] с меткой X.

Каждое состояние имеет переходы согласно Goto.

Сдвиг действия

Если [A → α • b β, a] находится в состоянии Ik и яk переходит в состояние Iм с меткой b, затем мы добавляем действие

действие [яk, b] = "сдвиг м"

Уменьшить действия

Если [A → α •, a] находится в состоянии Ik, затем добавляем действие

действие [яk, a] = "уменьшить A → α"

Рекомендации

  1. ^ а б c Кнут, Д. Э. (Июль 1965 г.). «О переводе языков слева направо» (PDF). Информация и контроль. 8 (6): 607–639. Дои:10.1016 / S0019-9958 (65) 90426-2. Архивировано из оригинал (PDF) 15 марта 2012 г.. Получено 29 мая 2011.CS1 maint: ref = harv (связь)
  2. ^ "Что такое Менгир?". INRIA, CRISTAL проект. Получено 29 июн 2012.
  3. ^ "HYACC, генератор минимального парсера LR (1)".
  4. ^ Франклин Л. Де Ремер (1969). «Практические переводчики языков LR (k)» (PDF). Массачусетский технологический институт, кандидатская диссертация. Архивировано из оригинал (PDF) 5 апреля 2012 г.
  5. ^ а б Пейджер, Д. (1977), "Практический общий метод построения LR (k) парсеров", Acta Informatica 7, стр. 249–268

внешняя ссылка