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

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

Определение

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

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

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

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

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

где 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. Ф ⊆ 2 ^{Н × ( Н ∪ Т ) *} — это конечное множество так называемых флагов (каждый флаг сам по себе является набором так называемых индексных продукций )
4. P ⊆ N × ( NF ^* ∪ Т ) ^* это конечное множество продукций
5. S ∈ N — начальный символ

Прямые выводы заключались в следующем:

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

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

Примеры

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

С [ σ ]	→	С [ fσ ]	Т [ fσ ]	→	а Т [ σ ]
С [ σ ]	→	S [ gσ ]	Т [ гσ ]	→	бТ ] [ σ
С [ σ ]	→	Т [ с ] Т [ с ] Т [ с ]	Т []	→	е

производным от abbabbabb Тогда будет

S [] ⇒ S [ g ] ⇒ S [ гг ] ⇒ S [ fgg ] ⇒ T [ fgg ] T [ fgg ] T [ fgg ] ⇒ a T [ gg ] T [ fgg ] T [ fgg ] ⇒ ab T [ g ] T [ fgg ] T [ fgg ] ⇒ abb T [] T [ fgg ] T [ fgg ] ⇒ abb T [ fgg ] T [ fgg ] ⇒ ... ⇒ abb abb T [ fgg ] ⇒ ... ⇒ abb abb абб .

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

S [ σ ] → Т [ gσ ]	А [ fσ ] → а А [ σ ]	А [ gσ ] → а
Т [ σ ] → Т [ fσ ]	B [ fσ ] → б B [ σ ]	Б [ гσ ] → б
Т [ σ ] → А [ σ ] 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 .

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

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

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

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

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

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

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

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

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

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

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

Пример

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

С [ σ ]	→	а S [ fσ ] c
С [ σ ]	→	Т [ с ]
Т [ fσ ]	→	Т [ п ] б
Т []	→	е

Чтобы получить строку abc, нам нужно выполнить следующие действия:

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

Сходным образом:

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

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

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

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

$Y^{\prime }[\sigma f]\to Y^{\prime }[\sigma ]$

$Y^{\prime }[]\to Y[]$

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

$S[\sigma ]\to T[\sigma ]V[]$

$V[]\to d~|~dV[]$

$T[\sigma ]\to aT[\sigma f]c~|~U[\sigma ]$

$U[\sigma f]\to bU[\sigma ]$

$U[]\to \epsilon$

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

$S[\sigma ]\to T[\sigma ]V^{\prime }[\sigma ]$

$V^{\prime }[\sigma f]\to V^{\prime }[\sigma ]$

$V^{\prime }[]\to V[]$

$V[]\to d~|~dV[]$

$T[\sigma ]\to aT[\sigma f]c~|~U[\sigma ]$

$U[\sigma f]\to bU[\sigma ]$

$U[]\to \epsilon$

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

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

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

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

Распределенные индексные грамматики

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

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

X[f₁...f_if_i+1...f_n] → α Y[f₁...f_i] β Z[f_i+1...f_n[

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

[ f₁...f_if_i+1...f_jf_j+1...f_n] → α Y[f₁...f_i] β Z[f_i+1...​​​​​​​​​​​​​​​​​​​​​​​​​​​​f _j ] γ W [ f _{j +1} ... f _n ] η

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

См. также

• Иерархия Хомского

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

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