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

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

Определение [ править ]

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

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

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

В продуктах, а также в производных индексированных грамматик, строка («стек») σ ∈ F ^* индексных символов присоединяется к каждому нетерминальному символу A ∈ N , обозначаемому A [ σ ]. ^{[примечание 1]} Терминальные символы не могут сопровождаться индексными стеками. Для индексного стека σ ∈ F ^* и строки α ∈ ( N ∪ T ) ^* нетерминальных и терминальных символов α [ σ ] обозначает результат присоединения [ σ ] к каждому нетерминалу в α; например , если α равен в B C D E с , д ∈ T терминала и B , C , E ∈ N нетерминальные символы, то α [ σ ] обозначает В [ σ ] С [ σ ] 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 ..] →α [..] соответственно.

Выводы аналогичны таковым в контекстно-свободной грамматике, за исключением стека индексов, прикрепленного к каждому нетерминальному символу. Когда производство , как , например , [ сг ] → B [ σ ] С [ σ ] применяется, стек индекс 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) ^[3] с использованием другого формализма. Ахо определил индексированную грамматику как 5-кортеж ( N , T , F , P , S ), где

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

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

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

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

Примеры [ править ]

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

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

Производное от 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 T [] T [ fgg ] T [ fgg ] ⇒ abb T [ fgg ] T [ fgg ] ⇒ ... ⇒ abb abb T [ fgg ] ⇒ ... ⇒ abb abb abb .

В качестве другого примера, грамматика G = ⟨{ S , Т , , В , С }, { , Ь , с }, { е , г }, P , S ⟩ производит язык { а ^п б ^н гр ^н : 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 .

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

Свойства [ править ]

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

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

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

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

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

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

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

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

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

Пример [ править ]

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

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

Чтобы получить строку 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 относительно просто. ^[17] Правила LIG в целом выглядят примерно так , по модулю push / pop части правила перезаписи. Символы и представляют собой строки терминальных и / или нетерминальных символов, и любой нетерминальный символ в любом из них должен иметь пустой стек по определению LIG. Это, конечно, противоречит тому, как определены IG: в IG нетерминалы, чьи стеки не передаются или не извлекаются, должны иметь точно такой же стек, что и перезаписанный нетерминал. Таким образом, каким-то образом нам нужно иметь нетерминалы в и${\ Displaystyle Х [\ сигма] \ к \ альфа Y [\ сигма] \ бета}$${\ displaystyle \ alpha}$${\ displaystyle \ beta}$${\ displaystyle \ alpha}$${\ displaystyle \ beta}$ которые, несмотря на непустые стеки, ведут себя так, как если бы у них были пустые стеки.

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

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

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

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

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

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

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

${\displaystyle U[\sigma f]\to bU[\sigma ]}$

${\displaystyle U[]\to \epsilon }$

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

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

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

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

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

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

${\displaystyle U[\sigma f]\to bU[\sigma ]}$

${\displaystyle U[]\to \epsilon }$

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

Отношение к другому формализму [ править ]

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

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

Грамматики распределенного индекса [ править ]

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

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

X [ f ₁ ... f _i f _{i +1} ... f _n ] → α Y [f ₁ ... f _i ] β Z [ f _{i +1} ... f _n ] γ

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

X [ f ₁ ... f _i f _{i +1} ... f _j f _{j +1} ... f _n ] → α Y [f ₁ ... f _i ] β Z [ f _{i +1} ... f _j ] γ W [ f _{j +1} ... f _n ] η

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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

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