Логическая грамматика - Boolean grammar

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

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

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

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

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

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

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

Смотрите также

• Уравнения языка

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

• Страница Охотина о булевых грамматиках