Конъюнктивная грамматика - Conjunctive grammar

Конъюнктивные грамматики класс формальной грамматики, изучаемый в формальный язык Они расширяют базовый тип грамматики, контекстно-свободные грамматики, с соединение Помимо явного соединения, конъюнктивные грамматики допускают неявное дизъюнкция представлен несколькими правилами для одного нетерминального символа, который является единственной логической связкой, выражаемой в контекстно-свободных грамматиках. Соединение может использоваться, в частности, для определения пересечения языков. Дальнейшее расширение конъюнктивных грамматик, известное как Булевы грамматики дополнительно допускает явное отрицание.

Правила конъюнктивной грамматики имеют вид

${\displaystyle A\to \alpha _{1}\And \ldots \And \alpha _{m}}$

куда ${\displaystyle A}$ нетерминал и${\displaystyle \alpha _{1}}$, ..., ${\displaystyle \alpha _{m}}$строки, состоящие из символов в ${\displaystyle \Sigma }$ и ${\displaystyle V}$ (конечные наборы терминальные и нетерминальные символы соответственно). Формально такое правило утверждает, что каждая строка ${\displaystyle w}$ над ${\displaystyle \Sigma }$который удовлетворяет каждому из синтаксических условий, представленных ${\displaystyle \alpha _{1}}$, ..., ${\displaystyle \alpha _{m}}$поэтому удовлетворяет условию, определенному ${\displaystyle A}$.

Формальное определение

Конъюнктивная грамматика ${\displaystyle G}$ определяется 4-кортеж ${\displaystyle G=(V,\Sigma ,R,S)}$ куда

1. V - конечное множество; каждый элемент ${\displaystyle v\in V}$ называется нетерминальный символ или Переменная. Каждая переменная представляет отдельный тип фразы или предложения в предложении. Переменные также иногда называют синтаксическими категориями.
2. Σ конечный набор Терминалs, не пересекается с V, которые составляют фактическое содержание предложения. Набор терминалов - это алфавит языка, определенный грамматикой грамм.
3. р - конечное множество продукций, каждая из которых имеет вид ${\displaystyle A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}}$ для некоторых ${\displaystyle A}$ в ${\displaystyle V}$ и ${\displaystyle \alpha _{i}\in (V\cup \Sigma )^{*}}$. Члены р называются правилоs или производствоs грамматики.
4. S - это начальная переменная (или начальный символ), используемая для представления всего предложения (или программы). Это должен быть элемент V.

Обычно перечисляют все правые части одной и той же левой части в одной строке, используя | (в символ трубы ), чтобы разделить их. Правила ${\displaystyle A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}}$ и ${\displaystyle A\rightarrow \beta _{1}\&\ldots \&\beta _{n}}$ следовательно, можно записать как ${\displaystyle A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}\ |\ \beta _{1}\&\ldots \&\beta _{n}}$.

Существуют два эквивалентных формальных определения языка, заданных конъюнктивной грамматикой, одно из которых основано на представлении грамматик как системы языковые уравнения с объединением, пересечением и конкатенацией и рассматривая его наименьшее решение. Другое определение обобщаетХомского генеративное определение контекстно-свободных грамматик с использованием переписывания терминов вместо соединения и конкатенации.

Определение по происхождению

Для любых струн ${\displaystyle u,v\in (V\cup \Sigma \cup \{{\text{“(”}},{\text{“}}\&{\text{”}},{\text{“)”}}\})^{*}}$, мы говорим ты непосредственно дает v, записанный как ${\displaystyle u\Rightarrow v\,}$, если

• либо есть правило ${\displaystyle A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}\in R}$ такой, что ${\displaystyle u\,=u_{1}Au_{2}}$ и ${\displaystyle v\,=u_{1}(\alpha _{1}\&\ldots \&\alpha _{m})u_{2}}$,
• или существует строка ${\displaystyle w\in (V\cup \Sigma )^{*}}$ такой, что ${\displaystyle u\,=u_{1}(w\&\ldots \&w)u_{2}}$ и ${\displaystyle v\,=u_{1}wu_{2}}$.

Для любой строки ${\displaystyle w\in \Sigma ^{*},}$ мы говорим грамм генерирует ш, записанный как ${\displaystyle S\ {\stackrel {*}{\Rightarrow }}\ w}$, если ${\displaystyle \exists k\geq 1\,\exists \,u_{1},\cdots ,u_{k}\in (V\cup \Sigma \cup \{{\text{“(”}},{\text{“}}\&{\text{”}},{\text{“)”}}\})^{*}}$ такой, что ${\displaystyle S=\,u_{1}\Rightarrow u_{2}\Rightarrow \cdots \Rightarrow u_{k}\,=w}$.

Язык грамматики ${\displaystyle G=(V,\Sigma ,R,S)}$ - это набор всех генерируемых им строк.

Пример

Грамматика ${\displaystyle G=(\{S,A,B,C,D\},\{a,b,c\},R,S)}$, с постановками

${\displaystyle S\rightarrow AB\&DC}$,

${\displaystyle A\rightarrow aA\ |\ \epsilon }$,

${\displaystyle B\rightarrow bBc\ |\ \epsilon }$,

${\displaystyle C\rightarrow cC\ |\ \epsilon }$,

${\displaystyle D\rightarrow aDb\ |\ \epsilon }$,

конъюнктивно. Типичный вывод:

${\displaystyle S\Rightarrow (AB\&DC)\Rightarrow (aAB\&DC)\Rightarrow (aB\&DC)\Rightarrow (abBc\&DC)\Rightarrow (abc\&DC)\Rightarrow (abc\&aDbC)\Rightarrow (abc\&abC)\Rightarrow (abc\&abcC)\Rightarrow (abc\&abc)\Rightarrow abc}$

Можно показать, что ${\displaystyle L(G)=\{a^{n}b^{n}c^{n}:n\geq 0\}}$. Язык не является контекстно-зависимым, что доказано лемма о прокачке для контекстно-свободных языков.

Алгоритмы парсинга

Хотя выразительная сила конъюнктивных грамматик больше, чем у контекстно-свободных грамматик, конъюнктивные грамматики сохраняют некоторые из последних. Что наиболее важно, существуют обобщения основных алгоритмов контекстно-свободного синтаксического анализа, включая линейно-временные. рекурсивный спуск, кубическое время обобщенный LR кубическое время Петух-Касами-младший,а также Доблестный алгоритм работает так же быстро, как умножение матриц.

Теоретические свойства

Свойство, которое неразрешимо уже для контекстно-свободных языков или их конечных пересечений, должно быть неразрешимым и для конъюнктивных грамматик; к ним относятся: пустота, конечность, регулярность, контекстная свобода,^{[n 1]} включение и эквивалентность.^{[n 2]}

Семейство конъюнктивных языков замкнуто относительно объединения, пересечения, конкатенация и Клини звезда, но не под гомоморфизм струн, префикс, суффикс и подстрока. Замыкание при дополнении и при гомоморфизме строк без ε все еще остаются открытыми проблемами (по состоянию на 2001 г.).^[1]:533

Исследована выразительная сила грамматики над однобуквенным алфавитом.^{[нужна цитата ]}

Эта работа послужила основой для изучения языковые уравнения более общего вида.

Синхронизированные чередующиеся автоматические выталкиватели

Айзиковиц и Камински^[2] представил новый класс выталкивающие автоматы (КПК) называется синхронизированные автоматы с попеременным опусканием (САПДА). Они доказали, что он эквивалентен конъюнктивным грамматикам точно так же, как недетерминированные КПК эквивалентны контекстно-свободным грамматикам.

Примечания

1. Учитывая конъюнктивную грамматику, является ли созданный ею язык пустым / конечным / регулярным / контекстно-свободным?
2. Учитывая две конъюнктивные грамматики, является ли сгенерированный первый язык подмножеством / равным второму?

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

1. Александр Охотин (2001). "Конъюнктивные грамматики" (PDF). Журнал автоматов, языков и комбинаторики. 6 (4): 519–535.
2. Айзиковиц, Тамар; Камински, Майкл (2011). "LR (0) Конъюнктивные грамматики и детерминированные синхронизированные чередующиеся автоматы выталкивания вниз". Компьютерные науки - теория и приложения. Конспект лекций по информатике. 6651. С. 345–358. Дои:10.1007/978-3-642-20712-9_27. ISBN  978-3-642-20711-2. ISSN  0302-9743.

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

• Артур Дже (2007). «Конъюнктивные грамматики порождают нерегулярные унарные языки» (PDF) (Слайды выступления на Международная конференция по развитию теории языка ). Получено 5 ноября 2019.
• "Страница Александра Охотина о конъюнктивных грамматиках". 9 октября 2011 г.. Получено 5 ноября 2019.
• Александр Охотин (2007). «Девять открытых задач для конъюнктивных и булевых грамматик». Бюллетень EATCS. Архивировано из оригинал 29 сентября 2007 г.
• Александр Охотин (2013). «Конъюнктивная и логическая грамматики: истинный общий случай контекстно-свободных грамматик». Обзор компьютерных наук. 9: 27–59. Дои:10.1016 / j.cosrev.2013.06.001. Эта статья заменяет более ранние обзоры «Обзор конъюнктивных грамматик» (Бюллетень EATCS, 2004) и «Девять открытых проблем для конъюнктивных и булевых грамматик»
• Jeż, Артур (2008). «Конъюнктивные грамматики порождают нерегулярные унарные языки». Международный журнал основ информатики. 19 (3): 597–615. Дои:10.1142 / S012905410800584X. Версия технического отчета (pdf)^{[постоянная мертвая ссылка ]}