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

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

• 1 Определение
  • 1.1 Современное определение Хопкрофта и Уллмана
  • 1.2 Исходное определение Ахо
• 2 Примеры
• 3 Свойства
• 4 Линейные индексированные грамматики
  • 4.1 Пример
  • 4.2 Вычислительная мощность
  • 4.3 Связь с другим формализмом
• 5 Грамматики распределенного индекса
• 6 См. Также
• 7 Примечания
• 8 R ссылки
• 9 Внешние ссылки

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

В современных публикациях, следующих за Хопкрофтом и Ульманом (1979), индексированная грамматика формально определяется как 5-кортеж. G = ⟨N, T, F, P, S⟩, где

• N - набор переменных или нетерминальных символов,,
• T - набор («алфавит ») терминальных символов,
• F - это набор так называемых индексных символов или индексов,
• S ∈ N - начальный символ, а
• P - конечный набор продукций.

В продукциях, а также в порождениях индексированных грамматик, строка («стек») σ ∈ F индексных символов присоединяется к каждому нетерминальному символу A ∈ N, обозначаемый A [σ]. За терминальными символами нельзя ставить стеки индексов. Для индексного стека σ ∈ F и строки α ∈ (N ∪ T) нетерминальных и терминальных символов α [σ] обозначает результат присоединения [σ] к каждому нетерминалу в α; например, если α равно B C d E с a, d ∈ T терминальным и нетерминальными символами B, C, E ∈ N, то α [σ] обозначает B [σ] C [σ] d E [σ]. Используя эти обозначения, каждое производство в P должно иметь вид

1. A [σ] → α [σ],
2. A [σ] → B [fσ] или
3. A [fσ] → α [σ],

где A, B ∈ N - нетерминальные символы, f ∈ F - индекс, σ ∈ F - строка индексных символов, а α ∈ (N ∪ T) - строка нетерминальных и терминальных символов. Некоторые авторы пишут ".." вместо "σ" для стека индекса в производственных правилах; тогда правило типа 1, 2 и 3 читается как A [..] → α [..], A [..] → B [f..] и A [f..] → α [..] соответственно.

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

Формально отношение ⇒ («прямое происхождение») определяется на множестве (N [F] ∪T) «сентенциальных форм» следующим образом:

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

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

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

Исторически концепция индексированных грамматик была впервые введена Альфредом Ахо (1968) с использованием другого формализма. Ахо определил индексированную грамматику как 5-кортеж (N, T, F, P, S), где

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

Прямые деривации были следующими:

• Производство p = (A → X 1η1…Xkηk) из P соответствует нетерминальному A ∈ N, за которым следует его (возможно, пустая) строка флагов ζ ∈ F. В контексте, γ Aζ δ через p переходит в γ X 1θ1…Xkθkδ, где θ i = η i ζ, если X i было нетерминалом, и пустым словом в противном случае. Поэтому старые флаги A копируются в каждый новый нетерминал, созданный p. Каждое такое производство может быть смоделировано соответствующими продукциями типа 1 и 2 в формализме Хопкрофта / Ульмана.
• Индекс производства p = (A → X 1…Xk) ∈ f соответствует Afζ (флаг f from должен соответствовать первому символу, следующему за нетерминалом A), и копирует оставшуюся строку индекса ζ в каждый новый нетерминал: γ Afζ δ происходит от γ X 1θ1…Xkθkδ, где θ i - пустое слово, когда X i - терминал, а ζ - нетерминал. Каждая такая продукция соответствует продукции типа 3 в формализме Хопкрофта / Уллмана.

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

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

S [σ]	→	S [fσ]	T [fσ ]	→	a T [σ]
S [σ]	→	S [gσ]	T [gσ]	→	b T [σ]
S [σ]	→	T [σ] T [σ] T [σ]	T	→	ε

Тогда вывод abbabbabb следующий:

S ⇒ S [g] ⇒ S [gg] ⇒ S [fgg] ⇒ T [fgg] T [fgg] T [fgg] ⇒ a T [gg] T [fgg] T [fgg] ⇒ ab T [g] T [fgg] T [fgg] ⇒ abb TT [fgg] T [fgg] ⇒ abb T [fgg] T [ fgg] ⇒... ⇒ abb abb T [fgg] ⇒... ⇒ abb abb abb.

В качестве другого примера грамматика G = ⟨{S, T, A, B, C}, {a, b, c}, {f, g}, P, S⟩ порождает язык {abc: n ≥ 1}, где производственное множество P состоит из

S [σ] → T [gσ]	A [fσ] → a A [σ]	A [gσ] → a
T [σ] → T [fσ]	B [fσ] → b B [σ]	B [gσ] → b
T [σ] → A [σ] B [σ] C [σ]	C [fσ] → c C [σ]	C [gσ] → c

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

S ⇒ T [g] ⇒ T [fg] ⇒ A [fg] B [fg] C [fg] ⇒ aA [g] B [fg] C [fg] ⇒ aA [g] bB [g] C [fg] ⇒ aA [g] bB [g] cC [g] ⇒ aa bB [g] cC [g] ⇒ aa bb cC [g] ⇒ aa bb cc.

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

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

• односторонние вложенные стековые автоматы
• макрограмматики Фишера
• автоматы Грейбаха со стеками stacks
• Алгебраическая характеристика Майбаума

Хаяши обобщил лемму о накачке на индексированные грамматики. Наоборот, Гилман дает «лемму о сжатии» для индексированных языков.

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

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

где A, B, f, σ, α используются как выше, и β ∈ (N ∪ T) - последовательность нетерминальных и терминальных символов, таких как α. Кроме того, отношение прямого вывода ⇒ определяется аналогично приведенному выше. Этот новый класс грамматик определяет строго меньший класс языков, который принадлежит к умеренно контекстно-зависимым классам.

Язык {www: w ∈ {a, b}} порождается индексированной грамматикой, но не линейной индексированной грамматикой, в то время как {ww: w ∈ {a, b}} и {abc : n ≥ 1} порождаются линейной индексированной грамматикой.

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

Пример

Если обозначить σ произвольный набор символов стека, мы может определить грамматику языка L = {abc | n ≥ 1} как

S [σ]	→	a S [fσ] c
S [σ]	→	T [σ]
T [fσ]	→	T [σ] b
T	→	ε

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

S ⇒ aS [f] c ⇒ aT [f] c ⇒ aT bc ⇒ abc

Аналогично:

S ⇒ aS [f] c ⇒ aaS [ff] cc ⇒ aaT [ff] cc ⇒ aaT [f] bcc ⇒ aaT bbcc ⇒ aabbcc

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

Языки с линейной индексацией являются подмножеством индексированных языков, и, таким образом, все LIG могут перекодироваться как IG, что делает LIG строго менее мощными, чем IG. Преобразование LIG в IG относительно просто. Правила LIG в целом выглядят примерно так: $X\; [\sigma ]\; \to \; \alpha \; Y\; [\sigma ]\; \beta \; \{\backslash \; displaystyle\; X\; [\backslash \; sigma]\; \backslash \; to\; \backslash \; alpha\; Y\; [\backslash \; sigma]\; \backslash \; beta\}$, по модулю push / pop часть правила перезаписи. Символы $\alpha \; \{\backslash \; displaystyle\; \backslash \; alpha\}$и $\beta \; \{\backslash \; displaystyle\; \backslash \; beta\}$представляют строки терминальных и / или нетерминальных символов, а также любые -терминальный символ в любом из них должен иметь пустой стек по определению LIG. Это, конечно, противоречит тому, как определены IG: в IG нетерминалы, чьи стеки не передаются или не извлекаются, должны иметь точно такой же стек, что и перезаписанный нетерминал. Таким образом, каким-то образом нам нужно иметь нетерминалы в $\alpha \; \{\backslash \; displaystyle\; \backslash \; alpha\}$и $\beta \; \{\backslash \; displaystyle\; \backslash \; beta\}$, которые, несмотря на отсутствие -пустые стеки, ведут себя так, как если бы они были пустыми.

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

$Y\; \prime \; [\sigma \; f]\; \to \; Y\; \prime \; [\sigma ]\; \{\backslash \; displaystyle\; Y\; ^\; \{\backslash \; prime\}\; [\backslash \; сигма\; f]\; \backslash \; к\; Y\; ^\; \{\backslash \; prime\}\; [\backslash \; sigma]\}$

$Y\; \text{'}[]\; \to \; Y\; []\; \{\backslash \; displaystyle\; Y\; ^\; \{\backslash \; prime\}\; \backslash \; to\; Y\}$

Мы можем применить это в общем к получить IG от LIG. Так, например, если LIG для языка $\{a\; n\; b\; n\; c\; n\; d\; m\; |\; n\; \ge \; 1,\; m\; \ge \; 1\}\; \{\backslash \; displaystyle\; \backslash \; \{a\; ^\; \{n\}\; b\; ^\; \{n\}\; c\; ^\; \{n\}\; d\; ^\; \{m\}\; |\; n\; \backslash \; geq\; 1,\; m\; \backslash \; geq\; 1\; \backslash \}\}$выглядит следующим образом:

$S\; [\sigma ]\; \to \; T\; [\sigma ]\; V\; []\; \{\backslash \; displaystyle\; S\; [\backslash \; sigma]\; \backslash \; to\; T\; [\backslash \; sigma]\; V\}$

$V\; []\; \to \; d\; |\; d\; V\; []\; \{\backslash \; displaystyle\; V\; \backslash \; к\; d\; ~\; |\; ~\; dV\}$

$T\; [\sigma ]\; \to \; a\; T\; [\sigma \; f]\; c\; |\; U\; [\sigma ]\; \{\backslash \; Displaystyle\; Т\; [\backslash \; sigma]\; \backslash \; к\; АТ\; [\backslash \; sigma\; f]\; с\; ~\; |\; ~\; U\; [\backslash \; sigma]\}$

$U\; [\sigma \; f]\; \to \; б\; U\; [\sigma ]\; \{\backslash \; Displaystyle\; U\; [\backslash \; sigma\; f]\; \backslash \; to\; bU\; [\backslash \; sigma]\}$

$U\; []\; \to \; ϵ\; \{\backslash \; displaystyle\; U\; \backslash \; to\; \backslash \; epsilon\}$

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

$S\; [\sigma ]\; \to \; T\; [\sigma ]\; V\; \prime \; [\sigma ]\; \{\backslash \; displaystyle\; S\; [\backslash \; sigma]\; \backslash \; к\; T\; [\backslash \; sigma]\; V\; ^\; \{\backslash \; prime\}\; [\backslash \; sigma]\}$

$V\; \text{'}[\sigma \; f]\; \to \; V\text{'}\; [\sigma ]\; \{\backslash \; displaystyle\; V\; ^\; \{\backslash \; prime\}\; [\backslash \; сигма\; f]\; \backslash \; к\; V\; ^\; \{\backslash \; prime\}\; [\backslash \; sigma]\}$

$V\; \text{'}[]\; \to \; V\; []\; \{\backslash \; displaystyle\; V\; ^\; \{\backslash \; prime\}\; \backslash \; к\; V\}$

$V\; []\; \to \; d\; |\; d\; V\; []\; \{\backslash \; displaystyle\; V\; \backslash \; к\; d\; ~\; |\; ~\; dV\}$

$T\; [\sigma ]\; \to \; a\; T\; [\sigma \; f]\; c\; |\; U\; [\sigma ]\; \{\backslash \; Displaystyle\; Т\; [\backslash \; sigma]\; \backslash \; к\; АТ\; [\backslash \; sigma\; f]\; с\; ~\; |\; ~\; U\; [\backslash \; sigma]\}$

$U\; [\sigma \; f]\; \to \; б\; U\; [\sigma ]\; \{\backslash \; Displaystyle\; U\; [\backslash \; sigma\; f]\; \backslash \; to\; bU\; [\backslash \; sigma]\}$

$U\; []\; \to \; ϵ\; \{\backslash \; displaystyle\; U\; \backslash \; to\; \backslash \; epsilon\}$

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

Связь с другим формализмом

Виджай-Шанкер и Вейр (1994) демонстрируют, что линейные индексированные грамматики, комбинаторные категориальные грамматики, древовидные грамматики и Головные грамматики определяют один и тот же класс строковых языков. Их формальное определение линейных индексированных грамматик отличается от выше.

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

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

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

X [f 1... f ifi + 1... f n ] → α Y [f 1... f i ] β Z [f i + 1... f n ] γ

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

X [f 1... f ifi + 1... f jfj + 1... f n ] → α Y [f 1... f i ] β Z [f i + 1... f j ] γ W [f j + 1... f n ] η

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

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

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