跳转到内容

确定上下文无关文法：修订间差异

维基百科，自由的百科全书
以互动方式浏览历史
←上一版本
删除的内容 添加的内容
可视化wikitext
TXiKiBoT（留言 | 贡献）
220,453次编辑
小 →参见：​ 修正内链
 
（未显示4个用户的4个中间版本）
第3行： 第3行：
它们在计算机科学领域中特别重要，因为这些文法可以有效的识别，而非确定上下文无关文法需要[[回溯]]或其他复杂的技术；非确定步骤的每次出现，栈都必须被复制并接着被传播(propagate)，消耗运行时间、内存或两者。在实践中，当你希望为非确定文法(比如用 [[YACC]])建立一个[[解析器]]的时候，你必须通过增加约束如优先级来改变分析器为确定的。
它们在计算机科学领域中特别重要，因为这些文法可以有效的识别，而非确定上下文无关文法需要[[回溯]]或其他复杂的技术；非确定步骤的每次出现，栈都必须被复制并接着被传播(propagate)，消耗运行时间、内存或两者。在实践中，当你希望为非确定文法(比如用 [[YACC]])建立一个[[解析器]]的时候，你必须通过增加约束如优先级来改变分析器为确定的。


确定上下文无关语言是拥有[[歧义文法|无歧义上下文无关文法]]的语言的集合的真子集。例如，无歧义文法 S → 0S0 | 1S1 | ε，它定义了在字母 0 和 1 上的偶数长度的[[回文]]的语言，它不能用确定下推自动机解析。<ref> {{cite book | last = [[John Hopcroft|Hopcroft]] | first = John | coauthors = [[Rajeev Motwani]] & [[Jeffrey Ullman]] | title = [[Introduction to automata theory, languages, and computation]] 2nd edition | year = 2001 | publisher = Addison-Wesley | pages = 246-253 }} </ref>
确定上下文无关语言是拥有[[歧义文法|无歧义上下文无关文法]]的语言的集合的真子集。例如，无歧义文法 S → 0S0 | 1S1 | ε，它定义了在字母 0 和 1 上的偶数长度的[[回文]]的语言，它能用确定下推自动机解析。<ref> {{cite book | last = [[John Hopcroft|Hopcroft]] | first = John | coauthors = [[Rajeev Motwani]] & [[Jeffrey Ullman]] | title = [[Introduction to automata theory, languages, and computation]] 2nd edition | year = 2001 | publisher = Addison-Wesley | pages = 246-253 }} </ref>


==参见==
==参见==
*[[确定分析]]
*[[确定分析]]
*[[确定下推自动机]]
*[[确定下推自动机]]
*[[LR 分析器]]
*[[LR分析器]]


==引用==
==引用==
第17行： 第17行：


{{形式语言与形式文法}}
{{形式语言与形式文法}}
[[Category:形式语言]]
[[Category:形式语言|Q]]

[[en:Deterministic context-free grammar]]
[[hr:Deterministička kontekstno neovisna gramatika]]
[[sr:Детерминистичка контекстно слободна граматика]]

2019年11月23日 (六) 01:08的最新版本

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

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

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

参见

[编辑]

引用

[编辑]
  1. ^ Hopcroft, John; Rajeev Motwani & Jeffrey Ullman. Introduction to automata theory, languages, and computation 2nd edition. Addison-Wesley. 2001: 246–253. 


检索自“https://zh.wikipedia.org/zhwiki/w/index.php?title=确定上下文无关文法&oldid=56981253”