Булева грамматика

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

Правила булевой грамматики имеют вид

$A\to \alpha _{1}\And \ldots \And \alpha _{m}\And \lnot \beta _{1}\And \ldots \And \lnot \beta _{n}$

где $A$ является нетерминалом, $m+n\geq 1$ и $\alpha _{1}$, ..., $\alpha _{m}$, $\beta _{1}$, ..., $\beta _{n}$ представляют собой строки, состоящие из символов в $\Sigma$ и $N$. Неформально такое правило утверждает, что каждая строка $w$ над $\Sigma$ который удовлетворяет каждому из синтаксических условий, представленных $\alpha _{1}$, ..., $\alpha _{m}$ и ни одно из синтаксических условий, представленных $\beta _{1}$, ..., $\beta _{n}$ следовательно, удовлетворяет условию, определенному $A$.

Существует несколько формальных определений языка, порожденных булевой грамматикой. Их объединяет одно: если грамматику представить в виде системы языковых уравнений с объединением, пересечением, дополнением и конкатенацией, то языки, порожденные грамматикой, должны быть решением этой системы. Семантика различается в деталях, некоторые определяют языки с помощью языковых уравнений, некоторые опираются на идеи из области логического программирования . Однако эти нетривиальные вопросы формального определения в большинстве случаев не имеют значения для практических соображений, и можно строить грамматики в соответствии с заданной неформальной семантикой. Практические свойства модели аналогичны свойствам конъюнктивных грамматик , а дескриптивные возможности дополнительно улучшены. В частности, сохраняются некоторые практически полезные свойства, унаследованные от контекстно-свободных грамматик , такие как эффективные алгоритмы синтаксического анализа, см. Охотин (2010) .

Ссылки

• Охотин, Александр (10 октября 2004 г.). «Булева грамматика» . Информация и вычисления . 194 (1): 19–48. дои : 10.1016/j.ic.2004.03.006 .
• Охотин, Александр (2006). Девять открытых задач по конъюнктивной и булевой грамматике (PDF) (Технический отчет). ТУКС. 794.
• Кунтуриотис, Василис; Номикос, Христос; Рондогианнис, Панос (2009). «Обоснованная семантика булевых грамматик» (PDF) . Информация и вычисления . 207 (9): 945–967. дои : 10.1016/j.ic.2009.05.002 .
• Охотин, Александр (2010). «Быстрый анализ булевых грамматик: обобщение алгоритма Валианта». Ин Гао, Ю.; Лу, Х.; Секи, С.; Ю, С. (ред.). Развитие теории языка . 14-я Международная конференция DLT 2010, Лондон, Онтарио, Канада, 17–20 августа 2010 г., Материалы . Конспекты лекций по информатике . Том. 6224. стр. 340–351. Препринт доступен онлайн, архивировано 3 марта 2016 г. в Wayback Machine .

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

• Okhotin's page on Boolean grammars