woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

确定上下文无关文法

形式文法理论中,确定上下文无关文法(DCFG)上下文无关文法真子集。确定上下文无关文法是确定下推自动机可识别的文法。确定上下文无关语言是确定上下文无关文法所定义的形式语言

它们在计算机科学领域中特别重要,因为这些文法可以有效的识别,而非确定上下文无关文法需要回溯或其他复杂的技术;非确定步骤的每次出现,栈都必须被复制并接着被传播(propagate),消耗运行时间、内存或两者。在实践中,当你希望为非确定文法(比如用 YACC)建立一个解析器的时候,你必须通过增加约束如优先级来改变分析器为确定的。

确定上下文无关语言是拥有无歧义上下文无关文法的语言的集合的真子集。例如,无歧义文法 S 0S0 | 1S1 | ε,它定义了在字母 0 1 上的偶数长度的回文的语言,它不能用确定下推自动机解析。[1]

[编辑] 参见

[编辑] 引用

1.  ^ Hopcroft, JohnRajeev Motwani & Jeffrey Ullman2001).Introduction to automata theory, languages, and computation 2nd editionAddison-Wesley246-253 

 

clip_image001  這是與逻辑学相關的小作品。你可以通过编辑或修订扩充其内容。

自动机理论: 形式语言和形式文法

乔姆斯基层级

文法

语言

极小自动机

类型 0

无限制

递归可枚举

图灵机

n/a

(无公用名)

递归

判定器

类型 1

上下文有关

上下文有关

线性有界

n/a

附标

附标

嵌套堆栈

n/a

树-邻接

适度上下文有关

嵌入下推

类型 2

上下文无关

上下文无关

非确定下推

n/a

确定上下文无关

确定上下文无关

确定下推

类型 3

正则

正则

有限

每个语言或文法范畴都是其直接上面的范畴的真子集

来自“http://zh.wikipedia.org/wiki/%E7%A1%AE%E5%AE%9A%E4%B8%8A%E4%B8%8B%E6%96%87%E6%97%A0%E5%85%B3%E6%96%87%E6%B3%95

分类: 形式语言

1个隐藏分类: 逻辑学小作品

 

posted on 2009-10-30 15:04 肥仔 阅读(945) 评论(0)  编辑 收藏 引用 所属分类: 状态机 & 自动机 & 形式语言


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理