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

редактировать

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

Правила логической грамматики имеют вид

$A → α 1 … α m ¬ β 1 … ¬ β n {\ displaystyle A \ to \ alpha _ {1} \ And \ ldots \ And \ alpha _ {m} \ And \ lnot \ beta _ {1} \ And \ ldots \ And \ lnot \ beta _ {n}}$ $A \ to \ alpha _ {1} \ And \ ldots \ And \ alpha _ { m} \ And \ lnot \ beta _ {1} \ And \ ldots \ And \ lnot \ beta _ {n}$

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

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

Литература

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

См. Также

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

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

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