Conjunctive Grammars
Conjunctive Grammars
复制标题
连接语法
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
A. Okhotin
中科院分区：
文献类型：
--
作者：
A. Okhotin
本文引入了一类形式文法，它是通过用一个显式的集合论交运算扩充上下文无关文法的形式而形成的。结果表明，合取语法可以产生一些重要的非上下文无关的语言结构，包括那些不属于上下文无关语言的交集闭包，并且它们可以提供非常简洁的描述，一些上下文无关语言和有限的上下文无关语言的交集。另一方面，证明了合取语法仍然可以在立方时间内解析，并且保留了派生树的概念，这为它们的实际适用性提供了合理的希望。
This paper introduces a class of formal grammars made up by augmenting the formalism of context-free grammars with an explicit set-theoretic intersection operation. It is shown that conjunctive grammars can generate some important non-contextfree language constructs, including those not in the intersection closure of context-free languages, and that they can provide very succinct descriptions of some context-free languages and finite intersections of context-free languages. On the other hand, it is proved that conjunctive grammars can still be parsed in cubic time and that the notion of the derivation tree is retained, which gives reasonable hope for their practical applicability.