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

Канонический парсер LR (также называемый парсером LR(1) ) — это тип восходящего алгоритма синтаксического анализа, используемый в информатике для анализа и обработки языков программирования . Он основан на методе анализа LR , который означает «вывод слева направо, крайний правый в обратном порядке».

Формально канонический анализатор LR — это анализатор LR(k) для k=1 , т.е. с одним просмотра вперед терминалом . Особенностью этого парсера является то, что любая грамматика LR(k) с k>1 может быть преобразована в грамматику LR(1). Однако для уменьшения k необходимы обратные замены, и по мере увеличения обратных замен грамматика может быстро стать большой, повторяющейся и трудной для понимания. LR(k) может работать со всеми детерминированными контекстно-свободными языками . В прошлом от этого парсера LR(k) избегали из-за его огромных требований к памяти в пользу менее мощных альтернатив, таких как парсер LALR и LL(1) . Однако недавно появился «минимальный анализатор LR(1)», требования к пространству которого близки к анализаторам LALR. , предлагается несколькими генераторами парсеров.

Как и большинство парсеров, парсер LR(1) автоматически генерируется компиляторами-компиляторами, такими как GNU Bison , MSTA, Menhir, ХАЙАКК, и ЛРСТАР.

История

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

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

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

Обзор

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

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

A1 → A B

это означает, что если мы введем вход A, за которым следует B , то мы сократим пару до A1 независимо от того, что будет дальше. После параметризации такого правила с предварительным просмотром мы имеем:

A1 → A B, a

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

A1 → A B, a

А2 → АВ, б

А3 → АВ, в

А4 → АВ, д

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

E1 → BC, д

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

A1 → A B, a

A1 → A B, b

A1 → A B, c

Е1 → АВ, д

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

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

• Последовательность ввода: ABC
• Правила:

A1 → A B

А2 → БК

последовательность можно сократить до

И А2

вместо

A1 C

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

х → у

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

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

х → у

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

A1 → A B

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

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

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

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

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

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

С → Е

Э → Т

Е → (Е)

Т → п

Т → + Т

Т → Т + п

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

[S → • E, $]

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

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

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

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

[С → • Э]

[Э → • Т]

[Э → • ( Е )]

[Т → • н]

[Т → • + Т]

[Т → • Т + п]

Наборы FIRST и FOLLOW

Для определения терминалов просмотра вперед используются так называемые наборы FIRST и FOLLOW.FIRST(A) — это набор терминалов, которые могут появиться в качестве первого элемента любой цепочки правил, соответствующих нетерминалу A. FOLLOW(I) элемента I [A → α • B β, x] — это набор терминалов, которые могут появляются сразу после нетерминала B, где α, β — произвольные строки символов, а x — произвольный терминал просмотра вперед. FOLLOW(k,B) набора элементов k и нетерминала B представляет собой объединение следующих наборов всех элементов из k, где за '•' следует B. Наборы FIRST могут быть определены непосредственно из замыканий всех нетерминалов в язык, а наборы FOLLOW определяются из элементов, используемых в наборах FIRST.

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

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

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

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

Определение терминалов просмотра вперед

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

СЛЕДУЙТЕ(0,S) = { $ }

СЛЕДУЮЩИЙ(0,E) = { $, ')'}

СЛЕДУЮЩИЙ(0,T) = { $, '+', ')' }

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

[S → • E, $]

[Е → • Т, $]

[Е → • Т, )]

[Е → • (Е), $]

[Е → • ( Е ), )]

[Т → • n, $]

[Т → • н, +]

[Т → • n, )]

[Т → • + Т, $]

[Т → • + Т, +]

[Т → • + Т, )]

[Т → • Т + n, $]

[Т → • Т + n, +]

[Т → • Т + 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):

[Е → Т*, $]

[Т → Т•+n,$]

[Т → Т • + n, +]

·

·

·

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

[Т → n•,$]

[Т → n*, +]

[Т → n •, )]

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

[Т → + • Т, $]

[Т → + • Т, +]

[Т → • n, $]

[Т → • н, +]

[Т → • + Т, $]

[Т → • + Т, +]

[Т → • Т + n, $]

[Т → • Т + n, +]

·

·

·

Набор элементов 5 ('('):

[Е → ( • Е ), $]

[Е → • Т, )]

[Е → • ( Е ), )]

[Т → • n, )]

[Т → • н, +]

[Т → • + Т, )]

[Т → • + Т, +]

[Т → • Т + n, )]

[Т → • Т + 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

[Е → Т*, $]

[Т → Т•+n,$]

[Т → Т • + n, +]

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

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

Согласно Гото, в каждом состоянии есть переходы.

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

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

действие[I _k , b] = "сдвиг м"

Сокращение действий

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

action[I _k , a] = «уменьшить A → α»

Внешние ссылки

• HTML-страница практического построения парсера LR(k) , Дэвид Триббл
• Создание первых и последующих наборов на Python (Нараяна Чиккам)