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

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

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

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

где есть нетерминал, и , ..., , ..., являются строки , сформированные из символов и . Неформально такое правило утверждает, что каждая строка, над которой удовлетворяет каждому из синтаксических условий, представленных , ..., и ни одно из синтаксических условий, представленных , ..., следовательно, не удовлетворяет условию, определенному .${\ displaystyle A}$${\ Displaystyle м + п \ 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 error: no target: CITEREFOkhotin2010 (help)

Ссылки [ править ]

• Охотин, Александр (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. Препринт доступен в Интернете.

См. Также [ править ]

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

Внешние ссылки [ править ]

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

Эта статья о формальных методах незавершена . Вы можете помочь Википедии, расширив ее .

• v
• t
• e