Индексированная грамматика - Indexed grammar

Индексированные грамматики являются обобщением контекстно-свободные грамматики в этом нетерминалы снабжены списками флаги, или же индексные символы.Язык, созданный индексированной грамматикой, называется индексированный язык.

Определение

Современное определение Хопкрофта и Ульмана

В современных публикациях после Хопкрофта и Ульмана (1979),^[2]индексированная грамматика формально определяется как 5-кортеж грамм = ⟨N,Т,F,п,S⟩ куда

• N набор переменных или нетерминальные символы,
• Т это набор ("алфавит ") терминальных символов,
• F представляет собой набор так называемых индексные символы, или же индексы,
• S ∈ N это начальный символ, и
• п конечный набор постановки.

В продуктах, а также в производных индексированных грамматик строка ("стек") σ ∈ F^* индексных символов присоединяется к каждому нетерминальному символу А ∈ N, обозначаемый А[σ].^{[примечание 1]}За терминальными символами не могут следовать стеки индексов. σ ∈ F^* и строка α ∈ (N ∪ Т)^* нетерминальных и терминальных символов, α[σ] обозначает результат прикрепления [σ] на каждый нетерминал в α; например, если α равно а B C d E с а,d ∈ Т терминал, и B,C,E ∈ N нетерминальные символы, то α[σ] обозначает а B[σ] C[σ] d E[σ].Используя эти обозначения, каждая продукция в п должен иметь форму

1. А[σ] → α [σ],
2. А[σ] → B[жσ], или
3. А[жσ] → α [σ],

куда А, B ∈ N нетерминальные символы, ж ∈ F это индекс, σ ∈ F^* строка индексных символов, а α ∈ (N ∪ Т)^* представляет собой строку нетерминальных и терминальных символов. Некоторые авторы пишут ".." вместо "σ"для стека индекса в производственных правилах; правило типа 1, 2 и 3 затем читает А[..]→α[..],   А[..]→B[ж..], и А[ж..]→α[..], соответственно.

Выводы аналогичны тем, что в контекстно-свободная грамматика за исключением стека индексов, прикрепленного к каждому нетерминальному символу. А[σ] → B[σ]C[σ] применяется индексный стек А копируется на оба B и CБолее того, правило может помещать индексный символ в стек или выталкивать свой «самый верхний» (т. Е. Крайний левый) индексный символ.

Формально отношение ⇒ («прямой вывод») определено на множестве (N[F^*]∪Т)^* "предложений" следующим образом:

1. Если А[σ] → α[σ] - продукция типа 1, то β А[φ] γ ⇒ β α[φ] γ, используя приведенное выше определение. То есть стек индекса левой стороны правила φ копируется в каждый нетерминал правой части.
2. Если А[σ] → B[fσ] - продукция типа 2, то β А[φ] γ ⇒ β B[fφ] γ. То есть стек индекса правой стороны получается из стека левой стороны φ толкая ж на него.
3. Если А[fσ] → α[σ] - продукция типа 3, то β А[fφ] γ ⇒ β α[φ] γ, снова используя определение α[σ]. То есть первый индекс ж извлекается из стека левой стороны, который затем распределяется по каждому нетерминалу правой стороны.

Как обычно, выводное соотношение ∗⇒ определяется как рефлексивное переходное замыкание прямого происхождения ⇒. L(грамм) = { ш ∈ Т^*: S ∗⇒ ш } - это набор всех строк терминальных символов, производных от начального символа.

Оригинальное определение Ахо

Исторически концепция индексированных грамматик была впервые введена Альфред Ахо (1968)^[3] используя другой формализм: он определил индексированную грамматику как набор из 5 (N,Т,F,п,S) куда

1. N конечный алфавит переменных или нетерминальные символы
2. Т конечный алфавит терминальных символов
3. F ⊆ 2^{N × (N ∪ Т)*} конечный набор так называемых флаги (каждый флаг сам по себе представляет собой набор так называемых индекс производства)
4. п ⊆ N × (NF^* ∪ Т)^* конечный набор постановки
5. S ∈ N это начальный символ

Прямые производные были следующими:

• Производство п = (А → Икс₁η₁…Икс_kη_k) из п соответствует нетерминальному А ∈ N за которой следует (возможно, пустая) строка флагов ζ ∈ F^*. В контексте, γ Aζ δ, через п, происходит от γ Икс₁θ₁…Икс_kθ_k δ, куда θ_я = η_яζ если Икс_я было нетерминальным и пустым словом в противном случае. Старые флаги А поэтому скопировано к каждому новому нетерминалу, производимому п. Каждое такое производство может быть смоделировано соответствующими производствами типа 1 и 2 в формализме Хопкрофта / Ульмана.
• Индекс производства п = (А → Икс₁…Икс_k) ∈ ж совпадения Afζ (флаг ж он должен соответствовать первому символу, следующему за нетерминальным А) и копирует оставшуюся строку индекса ζ к каждому новому нетерминалу: γ Afζ δ происходит от γ Икс₁θ₁…Икс_kθ_k δ, куда θ_я это пустое слово, когда Икс_я это терминал и ζ когда это нетерминал. Каждая такая продукция соответствует продукции типа 3 в формализме Хопкрофта / Ульмана.

Этот формализм, например, использовался Хаяси (1973, с. 65-66).^[4]

Примеры

На практике стопки индексов могут подсчитывать и запоминать, какие правила применялись и в каком порядке. Например, индексированные грамматики могут описывать контекстно-зависимый язык троек слов { www : ш ∈ {а,б}^* }:

S[σ]	→	S[fσ]	Т[fσ]	→	а Т[σ]
S[σ]	→	S[gσ]	Т[gσ]	→	б Т[σ]
S[σ]	→	Т[σ] Т[σ] Т[σ]	Т[]	→	ε

Вывод abbabbabb затем

S[] ⇒ S[грамм] ⇒ S[gg] ⇒ S[фгг] ⇒ Т[фгг] Т[фгг] Т[фгг] ⇒ а Т[gg] Т[фгг] Т[фгг] ⇒ ab Т[грамм] Т[фгг] Т[фгг] ⇒ abb Т[] Т[фгг] Т[фгг] ⇒ abb Т[фгг] Т[фгг] ⇒ ... ⇒ abb abb Т[фгг] ⇒ ... ⇒ abb abb abb.

Другой пример: грамматика грамм = ⟨ {S,Т,А,B,C}, {а,б,c}, {ж,грамм}, п, S ⟩ Производит язык { а^пб^пc^п: п ≥ 1}, где производственное множество п состоит из

S[σ] → Т[gσ]	А[fσ] → а А[σ]	А[gσ] → а
Т[σ] → Т[fσ]	B[fσ] → б B[σ]	B[gσ] → б
Т[σ] → А[σ] B[σ] C[σ]	C[fσ] → c C[σ]	C[gσ] → c

Пример вывода:

S[] ⇒ Т[грамм] ⇒ Т[фг] ⇒ А[фг] B[фг] C[фг] ⇒ аА[грамм] B[фг] C[фг] ⇒ аА[грамм] bB[грамм] C[фг] ⇒ аА[грамм] bB[грамм] cC[грамм] ⇒ аа bB[грамм] cC[грамм] ⇒ аа bb cC[грамм] ⇒ аа bb cc.

Оба примера языков не являются контекстно-независимыми по лемма о накачке.

Характеристики

Хопкрофт и Ульман склонны рассматривать индексированные языки как «естественный» класс, поскольку они порождаются несколькими формализмами, отличными от индексированных грамматик, а именно.^[5]

• Ахо односторонний вложенные стековые автоматы^[6]
• Фишер макро грамматики^[7]
• Greibach автоматы со стопками стопок^[8]
• Майбаум алгебраическая характеристика^[9]

Хаяси^[4] обобщил лемма о накачке к индексированным грамматикам. И наоборот, Гилман^[10][11] дает «лемму сжатия» для индексированных языков.

Линейные индексированные грамматики

Джеральд Газдар определил второй класс, линейные индексированные грамматики (LIG),^[14] требуя, чтобы не более одного нетерминала в каждом продукте указывалось как принимающее стек,^{[заметка 2]}тогда как в обычной индексированной грамматике все нетерминалы получают копии стека. Формально линейная индексированная грамматика определяется так же, как и обычная индексированная грамматика, но требования к форме продукта изменены на:

1. А[σ] → α[] B[σ] β[],
2. А[σ] → α[] B[fσ] β[],
3. А[fσ] → α[] B[σ] β[],

куда А, B, ж, σ, α используются как над, и β ∈ (N ∪ Т)^* представляет собой строку нетерминальных и конечных символов, например α.^{[заметка 3]} Кроме того, отношение прямого вывода ⇒ определяется аналогично приведенному выше. Этот новый класс грамматик определяет строго меньший класс языков,^[15] который принадлежит слегка контекстно-зависимый классы.

Язык { www : ш ∈ {а,б}^* } генерируется индексированной грамматикой, но не линейной индексированной грамматикой, в то время как оба { ww : ш ∈ {а,б}^* } и { а^п б^п c^п : n ≥ 1} порождаются линейной индексированной грамматикой.

Если допускаются как исходные, так и измененные производственные правила, языковой класс остается индексируемыми языками.^[16]

Пример

Обозначая σ произвольный набор символов стека, мы можем определить грамматику для языка L = {а^п б^п c^п | п ≥ 1 }^{[примечание 4]} в качестве

S[σ]	→	в качестве[fσ] c
S[σ]	→	Т[σ]
Т[fσ]	→	Т[σ] б
Т[]	→	ε

Чтобы получить строку abc у нас есть шаги:

S[] ⇒ в качестве[ж]c ⇒ в[ж]c ⇒ в[]до н.э ⇒ abc

По аналогии:

S[] ⇒ в качестве[ж]c ⇒ aaS[ff]cc ⇒ ааТ[ff]cc ⇒ ааТ[ж]скрытая копия ⇒ ааТ[]bbcc ⇒ aabbcc

Вычислительная мощность

Линейно индексированные языки являются подмножеством индексированных языков, и, таким образом, все LIG могут быть перекодированы как IG, что делает LIG строго менее мощными, чем IG. Преобразование LIG в IG относительно просто.^[17] Правила LIG в целом выглядят примерно так ${displaystyle X [сигма] или альфа Y [сигма] эта}$, по модулю push / pop часть правила перезаписи. Символы ${displaystyle alpha}$ и ${displaystyle eta}$ представляют строки терминальных и / или нетерминальных символов, и любой нетерминальный символ в любом из них должен иметь пустой стек по определению LIG. Это, конечно, противоречит тому, как определены IG: в IG нетерминалы, чьи стеки не передаются или не извлекаются, должны иметь точно такой же стек, что и перезаписанный нетерминал. Таким образом, каким-то образом нам нужно иметь нетерминалы в ${displaystyle alpha}$ и ${displaystyle eta}$ которые, несмотря на непустые стеки, ведут себя так, как если бы у них были пустые стеки.

Рассмотрим правило ${displaystyle X [сигма] o Y [] Z [сигма f]}$ в качестве примера. При преобразовании этого в IG замена для ${displaystyle Y []}$ должно быть несколько ${displaystyle Y ^ {prime} [сигма]}$ это ведет себя точно так же, как ${displaystyle Y []}$ независимо от того, что ${displaystyle sigma}$ является. Для этого мы можем просто иметь пару правил, которые принимают любые ${displaystyle Y ^ {prime} [сигма]}$ куда ${displaystyle sigma}$ не пуст, а выталкивает символы из стека. Затем, когда стек пуст, его можно переписать как ${displaystyle Y []}$.

${displaystyle Y ^ {prime} [sigma f] o Y ^ {prime} [sigma]}$

${displaystyle Y ^ {prime} [] o Y []}$

Мы можем применить это в целом, чтобы получить IG из LIG. Так, например, если LIG для языка ${displaystyle {a ^ {n} b ^ {n} c ^ {n} d ^ {m} | ngeq 1, mgeq 1}}$ как следует:

${displaystyle S [сигма] o T [сигма] V []}$

${displaystyle V [] o d ~ | ~ dV []}$

${displaystyle T [сигма] o aT [сигма f] c ~ | ~ U [сигма]}$

${displaystyle U [sigma f] o bU [sigma]}$

${displaystyle U [] o эпсилон}$

Правило предложения здесь не является правилом IG, но, используя приведенный выше алгоритм преобразования, мы можем определить новые правила для ${displaystyle V ^ {prime}}$, изменив грамматику на:

${displaystyle S [сигма] o T [сигма] V ^ {prime} [сигма]}$

${displaystyle V ^ {prime} [sigma f] o V ^ {prime} [sigma]}$

${displaystyle V ^ {prime} [] o V []}$

${displaystyle V [] o d ~ | ~ dV []}$

${displaystyle T [сигма] o aT [сигма f] c ~ | ~ U [сигма]}$

${displaystyle U [sigma f] o bU [sigma]}$

${displaystyle U [] o эпсилон}$

Каждое правило теперь соответствует определению IG, в котором все нетерминалы в правой части правила перезаписи получают копию стека перезаписанного символа. Таким образом, индексированные грамматики могут описывать все языки, которые могут описывать линейно индексированные грамматики.

Отношение к другому формализму

Виджай-Шанкер и Вейр (1994)^[18] демонстрирует, что линейные индексированные грамматики, Комбинаторные категориальные грамматики, Грамматики, примыкающие к дереву, и Головные грамматики все они определяют один и тот же класс строковых языков. Их формальное определение линейных индексированных грамматик^[19] отличается от над.^{[требуется разъяснение ]}

LIG (и их слабо эквиваленты ) строго менее выразительны (то есть они порождают собственное подмножество), чем языки, порожденные другим семейством слабоэквивалентного формализма, которые включают: LCFRS, MCTAG, MCFG и минималистская грамматика (MG). Последнее семейство может (также) быть проанализировано в полиномиальное время.^[20]

Грамматики распределенного индекса

Другая форма индексированных грамматик, введенная Штаудахером (1993),^[12] - это класс грамматик распределенного индекса (DIG). Что отличает DIG от индексированных грамматик Aho, так это распространение индексов. В отличие от IG Aho, которые распределяют весь стек символов всем нетерминалам во время операции перезаписи, DIG делят стек на подстаки и распределяют подстаки по выбранным нетерминалам.

Общая схема правила для бинарно распределяемого правила DIG - это форма

Икс[ж₁...ж_яж_я+1...ж_п] → α Y[f₁...ж_я] β Z[ж_я+1...ж_п] γ

Где α, β и γ - произвольные терминальные строки. Для строки с тройным распределением:

Икс[ж₁...ж_яж_я+1...ж_jж_j+1...ж_п] → α Y[f₁...ж_я] β Z[ж_я+1...ж_j] γ W[ж_j+1...ж_п] η

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

Смотрите также

• Иерархия Хомского
• Индексированный язык

Примечания

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

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

• Глава "НЛП в Прологе" об индексированных грамматиках и языках