Индексированные грамматики являются обобщением контекстно-свободных грамматик в том смысле, что нетерминалы снабжены списками флагов или индексных символов . Язык, созданный с помощью индексированной грамматики, называется индексированным языком .
Определение
Современное определение Хопкрофта и Ульмана
В современных публикациях следующих 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 должна иметь вид
- A [σ] → α [σ],
- A [σ] → B [ f σ], или
- 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 ) * «сентенциальных форм» следующим образом:
- Если A [ σ ] → α [ σ ] - продукция типа 1, то β A [ φ ] γ ⇒ β α [ φ ] γ , используя приведенное выше определение. То есть индексный стек φ левой стороны правила копируется в каждый нетерминал правой части.
- Если A [ σ ] → B [ fσ ] - продукция типа 2, то β A [ φ ] γ ⇒ β B [ fφ ] γ . То есть индексный стек правой стороны получается из левого стека φ путем нажатия на него f .
- Если A [ fσ ] → α [ σ ] является продукцией типа 3, то β A [ fφ ] γ ⇒ β α [ φ ] γ , снова используя определение α [ σ ]. То есть первый индекс f извлекается из стека левой стороны, который затем распределяется на каждый нетерминал правой стороны.
Как обычно, выводное соотношение определяется как рефлексивное транзитивное замыкание прямого вывода ⇒. Язык L ( G ) = { w ∈ T * : S w } - это набор всех строк терминальных символов, производных от начального символа.
Оригинальное определение Ахо
Исторически концепция индексированных грамматик была впервые введена Альфредом Ахо (1968) [3] с использованием другого формализма. Ахо определил индексированную грамматику как 5-кортеж ( N , T , F , P , S ), где
- N - конечный алфавит переменных или нетерминальных символов
- T - конечный алфавит терминальных символов
- F ⊆ 2 N × ( N ∪ T ) * - конечный набор так называемых флагов (каждый флаг сам по себе является набором так называемых индексных производств )
- P ⊆ N × ( NF * ∪ T ) * - конечное множество продукций
- S ∈ N - начальный символ
Прямые производные были следующими:
- Продукции p = ( A → X 1 η 1 … X k η k ) из P соответствует нетерминал A ∈ N, за которым следует его (возможно, пустая) строка флагов ζ ∈ F * . В контексте, γ Aζ δ через p переходит в γ X 1 θ 1 … X k θ k δ , где θ i = η i ζ, если X i было нетерминальным, и пустым словом в противном случае. Старые флаги А поэтому копируются в каждый новый нетерминал производимого р . Каждое такое производство может быть смоделировано соответствующими производствами типа 1 и 2 в формализме Хопкрофта / Ульмана.
- Продукция индекса p = ( A → X 1 … X k ) ∈ f соответствует Afζ (флаг f должен соответствовать первому символу, следующему за нетерминалом A ) и копирует оставшуюся строку индекса ζ в каждый новый нетерминал: γ Afζ δ происходит от γ X 1 θ 1 … 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 абб .
В качестве другого примера, грамматика 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], тогда как в обычной индексированной грамматике все нетерминалы получают копии стопки. Формально линейная индексированная грамматика определяется так же, как и обычная индексированная грамматика, но требования к форме продукта изменены на:
- A [ σ ] → α [] B [ σ ] β [],
- A [ σ ] → α [] B [ fσ ] β [],
- A [ fσ ] → α [] B [ σ ] β [],
где A , B , f , σ , α используются, как указано выше , а β ∈ ( N ∪ T ) * - строка нетерминальных и конечных символов, таких как α . [примечание 3] Кроме того, отношение прямого вывода ⇒ определяется аналогично приведенному выше. Этот новый класс грамматик определяет строго меньший класс языков [15], который принадлежит к умеренно зависимым от контекста классам.
Язык { www : w ∈ { a , b } * } порождается индексированной грамматикой, но не линейной индексированной грамматикой, в то время как как { ww : w ∈ { a , b } * }, так и { a n b n c n : n ≥ 1} порождаются линейной индексированной грамматикой.
Если допускаются как исходные, так и измененные производственные правила, языковой класс остается индексируемыми языками. [16]
Пример
Обозначив σ произвольный набор символов стека, мы можем определить грамматику для языка L = { a n b n c n | 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 нетерминалы, чьи стеки не передаются или не извлекаются, должны иметь точно такой же стек, что и перезаписанный нетерминал. Таким образом, каким-то образом нам нужно иметь нетерминалы в а также которые, несмотря на непустые стеки, ведут себя так, как если бы у них были пустые стеки.
Рассмотрим правило в качестве примера. При преобразовании этого в IG замена для должно быть что-то это ведет себя точно так же, как независимо от того, что является. Для этого мы можем просто иметь пару правил, которые принимают любые где не пуст, а выталкивает символы из стека. Затем, когда стек пуст, его можно переписать как.
Мы можем применить это в целом для получения IG из LIG. Так, например, если LIG для языка составляет:
Правило предложения здесь не является правилом IG, но, используя приведенный выше алгоритм преобразования, мы можем определить новые правила для , изменив грамматику на:
Каждое правило теперь соответствует определению IG, в котором все нетерминалы в правой части правила перезаписи получают копию стека перезаписанного символа. Таким образом, индексированные грамматики могут описывать все языки, которые могут описывать линейно индексированные грамматики.
Отношение к другому формализму
Виджай-Шанкер и Вейр (1994) [18] демонстрируют, что линейные индексированные грамматики, комбинаторные категориальные грамматики , древовидные грамматики и главные грамматики определяют один и тот же класс строковых языков. Их формальное определение линейных индексированных грамматик [19] отличается от приведенного выше . [ требуется разъяснение ]
LIG (и их слабые эквиваленты ) строго менее выразительны (что означает, что они генерируют собственное подмножество), чем языки, порожденные другим семейством слабо эквивалентного формализма, которое включает: LCFRS , MCTAG , MCFG и минималистские грамматики (MG). Последнее семейство можно (также) проанализировать за полиномиальное время . [20]
Грамматики распределенного индекса
Другая форма индексированных грамматик, представленная Staudacher (1993), [12], - это класс грамматик с распределенным индексом (DIG). Что отличает DIG от индексированных грамматик Aho, так это распространение индексов. В отличие от IG Aho, которые распределяют весь стек символов по всем нетерминалам во время операции перезаписи, DIG делят стек на субпакеты и распределяют субпакеты выбранным нетерминалам.
Общая схема правила для бинарно распределяемого правила DIG - это форма
- X [ f 1 ... f i f i +1 ... f n ] → α Y [f 1 ... f i ] β Z [ f i +1 ... f n ] γ
Где α, β и γ - произвольные терминальные строки. Для строки с тройным распределением:
- X [ f 1 ... f i f i +1 ... f j f j +1 ... f n ] → α Y [f 1 ... f i ] β Z [ f i +1 ... f j ] γ W [ f j +1 ... f n ] η
И так далее для большего количества нетерминалов в правой части правила перезаписи. В общем, если есть m нетерминалов в правой части правила перезаписи, стек разбивается m способами и распределяется среди новых нетерминалов. Обратите внимание, что существует особый случай, когда раздел пуст, что фактически делает правило правилом LIG. Таким образом, языки с распределенным индексом являются надмножеством языков с линейным индексом.
Смотрите также
- Иерархия Хомского
- Индексированный язык
Заметки
- ^ «[» и «]» - это метасимволы для обозначения стека.
- ^ все остальные нетерминалы получают пустой стек
- ^ a b Для того, чтобы вообще сгенерировать любую строку, необходимо разрешить некоторые произведения, не имеющие нетерминального символа справа. Однако Газдар не стал обсуждать этот вопрос.
- ^ Ср. правильно проиндексированная грамматика для того же языка, указанная выше . Последнее правило, а именно. T [] → ε линейной индексированной грамматики не соответствует определению Газдара в строгом смысле, ср. [заметка 3]
Рекомендации
- ^ а б Хопкрофт, Джон Э .; Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Эддисон-Уэсли. ISBN 978-0-201-02988-8.
- ^ Hopcroft и Ульмана (1979), [1] Sect.14.3, p.389-390. Этот раздел опущен во 2-м издании 2003 г.
- ^ Ахо, Альфред (1968). «Индексированные грамматики - расширение контекстно-свободных грамматик». Журнал ACM . 15 (4): 647–671. DOI : 10.1145 / 321479.321488 .
- ^ а б Хаяси, Такеши (1973). «О деревьях происхождения индексированных грамматик: расширение uvwxy -теоремы» . Публикации НИИ математических наук . 9 : 61–92. DOI : 10.2977 / Призмы / 1195192738 .
- ↑ Hopcroft and Ullman (1979), [1] Библиографические примечания, стр. 394-395.
- ^ Альфред Ахо (1969). «Вложенные автоматы стека». Журнал ACM . 16 (3): 383–406. DOI : 10.1145 / 321526.321529 .
- ^ Майкл Дж. Фишер (1968). "Грамматики с Macro-Like Productions". Proc. 9-я Энн. IEEE Symp. по теории коммутации и автоматов (SWAT) . С. 131–142. DOI : 10.1109 / SWAT.1968.12 .
- ^ Шейла А. Грейбах (1970). «Полная AFL и вложенная итерационная замена» . Информация и контроль . 16 (1): 7–35. DOI : 10.1016 / s0019-9958 (70) 80039-0 .
- ^ TSE Maibaum (1974). «Обобщенный подход к формальным языкам». Журнал компьютерных и системных наук . 8 (3): 409–439. DOI : 10.1016 / s0022-0000 (74) 80031-0 .
- ^ Роберт Х. Гилман (1996). «Лемма о сжатии для индексированных языков». Теоретическая информатика . 163 (1–2): 277–281. arXiv : math / 9509205 . DOI : 10.1016 / 0304-3975 (96) 00244-7 .
- ^ Роберт Х. Гилман (сентябрь 1995 г.). «Лемма о сжатии для индексированных языков». arXiv : math / 9509205 .
- ^ а б Staudacher, Питер (1993), Новые границы за пределами контекстной свободы: DI-грамматики (DIG) и DI-автоматы. (PDF) , стр. 358–367, архивировано из оригинального (PDF) 19 июля 2006 г. Неизвестный параметр
|book-title=
игнорируется ( справка ) - ^ Дэвид Дж. Вейр; Аравинд К. Джоши (1988). «Комбинированные категориальные грамматики: порождающая сила и связь с линейными бесконтекстными системами перезаписи» (PDF) . Proc. 26-е заседание доц. Comput. Линг . С. 278–285.
- ^ Согласно Staudacher (1993, p.361 слева, Sect.2.2), [12] название «линейная индексированные грамматик» не был использован в 1988 году бумаги Gazdar, но появились позже, напримерв Вейр и Джоши (1988). [13]
- ^ Газдар, Джеральд (1988). «Применимость индексированных грамматик к естественным языкам». В У. Рейле и К. Рорере (ред.). Анализ естественного языка и лингвистические теории . Исследования в области лингвистики и философии. 35 . Издательство Д. Рейдел. С. 69–94. ISBN 978-1-55608-055-5.
- ^ Gazdar (1988), Приложение, стр.89
- ^ Gazdar 1988, Приложение, p.89-91
- ^ Виджай-Шанкер, К .; Вейр, Дэвид Дж. 1994. (1994). «Эквивалентность четырех расширений контекстно-свободных грамматик» . Математическая теория систем . 27 (6): 511–546. DOI : 10.1007 / bf01191624 .
- ^ стр.517-518
- ^ Йохан Ф.К. ван Бентем; Алиса тер Мёлен (2010). Справочник по логике и языку (2-е изд.). Эльзевир. п. 404. ISBN 978-0-444-53727-0.
Внешние ссылки
- Глава "НЛП в Прологе" об индексированных грамматиках и языках.