logo标签列表

正则文法与上下文无关文法的区别

context-free-grammarregular-languageautomata
116

我正在为我的计算语言测试学习，有一个概念让我难以理解。

我知道正则语法更简单且不能包含歧义，但无法处理编程语言所需的大部分任务。我也知道上下文无关语法允许歧义存在，但可以处理编程语言中一些必要的东西（如回文）。

我不明白的是，如何通过知道正则语法非终结符可以映射到终结符或终结符和非终结符的组合、或者上下文无关语法非终结符可以映射到任意终结符和非终结符的组合，来推导出上述所有内容。

能否有人帮助我将所有这些内容整合起来？

8个回答
84

正则文法要么是右线性的，要么是左线性的，而上下文无关文法基本上是终结符和非终结符的任意组合。因此您可以看到，正则文法是上下文无关文法的子集。

因此，例如回文就是这种形式：

S->ABA
A->something
B->something

很明显，回文串不能用正则语法表示，因为它必须是右线性或左线性的，因此不能在两侧使用非终结符。

由于正则文法是无歧义的，对于给定的非终结符只有一条产生式规则，而在上下文无关文法的情况下可以有多个产生式规则。

16
首先，常规文法可能存在歧义（例如Kai Kuchenbecker提出的例子：S -> aA | aB，B -> a，A -> a）。但唯一的限制是在语法树中节点的位置只有一种方式（例如使用常规文法时不存在结合性歧义）。其次，一个非终结符可以有多个右侧表达式（A -> a，A -> aA；维基百科甚至将epsilon作为第三种备选方案：http://en.wikipedia.org/wiki/Regular_grammar）。 - user764754
2
歧义出现在一个句子可以从你的语法中以多个派生路径推导出来时。仅仅为一个非终端符号拥有多个产生式规则并不会使语法具有歧义。 - Sujoy
13
这个例子实际上是错的。如果我们想象完整的规则为 A->a | c 和 B->b，那么这个语法允许非回文字符串。例如，我可以生成：S->ABA->aBA->abA->abc。问题在于我们不想在第一条规则中生成两个变量，而应该是两个终结符。一个允许回文字符串的语法可能是：S -> aSa | bSb | a | b。 - gdiazc
有回文可以用正则语法表达：由单个字符组成的回文。例如，S -> aSa | e 和 a(aa)*a 都描述了一个正则语言。这表明，即使违反左线性或右线性，CFG也可以描述正则语言。不可否认，这是一个不太明显的回文。 - Martijn
想一想，这个答案实际上是错误的。它说“无上下文”语法基本上是任何终端和非终端的组合。然而，tu^nvw^mxy^kz是终端和非终端的组合，但不是无上下文的。 - Charlie Martin
60
我认为你需要考虑的是各种泵引理。一个正则语言可以被有限自动机识别。一个上下文无关的语言需要一个栈，而一个上下文有关的语言需要两个栈（这等价于说它需要一个完整的图灵机）。
因此，如果我们考虑正则语言的泵引理，它实际上是在说任何正则语言都可以分解成三个部分，x、y和z，其中所有语言实例都在xy*z中（其中 * 是 Kleene 重复，即y的0个或多个副本）。你基本上只有一个可以扩展的“非终端符号”。
现在，对于上下文无关的语言呢？有一个类似的上下文无关语言的泵引理，将语言中的字符串分成五个部分，uvxyz，其中所有语言实例都在uvixyiz中，i≥0。现在，你有两个“非终端符号”可以复制或泵，只要你有相同数量的非终端符号。
11
一个上下文敏感语言并不需要完整的图灵机，一个线性有界自动机已经足够。这是一种图灵机，其纸带是有限的，并且大小受输入字符串上某个线性函数的限制。 - Dave Clarke
20
常规文法和上下文无关文法的区别：(N, Σ, P, S)：终端、非终端、产生式、起始状态终止符号。
● 由形式语法定义的语言的基本符号。
● abc。
非终端符号（或句法变量）。
● 根据产生规则替换为终端符号组。
● ABC。 常规文法：右或左常规文法
  1. 当B是N中的非终端符号，a是Σ中的终端符号时，B → a。
  2. 当B和C在N中，a是Σ中的终端符号时，B → aC。
  3. 当B在N中时，ε表示空字符串，即长度为0的字符串，则B → ε。
左常规文法：所有规则遵循以下形式
  1. 当A是N中的非终端符号，a是Σ中的终端符号时，A → a。
  2. 当A和B在N中，a是Σ中的终端符号时，A → Ba。
  3. 当A在N中，ε表示空字符串时，则A → ε。
上下文无关文法（CFG） ○ 每个产生式规则的形式为V → w的形式的正式文法。
○ V是单个非终端符号。
○ w是终端符号和/或非终端符号的字符串（w可以为空）。
7

正则文法：包含以下产生式的文法是RG：

V->TV or VT
V->T

其中V代表变量，T代表终端

RG可以是左线性文法或右线性文法，但不是中间线性文法。

我们知道所有的RG都是线性文法，但只有左线性或右线性文法才是RG。

正则文法可能是有歧义的。

S->aA|aB
A->a
B->a

歧义语法：对于一个字符串x，可能存在多个左最深推导或多个右最深推导或多个解析树或一个左最深推导和一个右最深推导但是它们产生不同的解析树。

                S                   S

              /   \               /   \
             a     A             a     B
                    \                   \
                     a                   a

这个语法是有歧义的语法，因为有两棵解析树。
CFG（上下文无关文法）是指其产生式形式如下的语法：
   V->@   where @ belongs to (V+T)*

DCFL：- 我们知道所有的DCFL都是LL(1)文法，而所有的LL(1)文法都是LR(1)，因此它永远不会有歧义。因此，DCFG永远不会有歧义。

我们还知道所有的RL都是DCFL，所以RL永远不会有歧义。请注意，RG可能存在歧义，但RL不会。

CFL： CFL可能有歧义，也可能没有。

Note： RL从本质上来说永远不会有歧义。

4

正则表达式

  • 词法分析的基础
  • 代表正则语言

上下文无关文法

  • 解析的基础
  • 代表语言结构

enter image description here

不是的，那只是简短的描述，请再仔细阅读并检查图片。 - Ahmed Salem
3

如果所有的产生式规则都具有以下形式：A （即，产生式规则的左侧只能是一个变量；右侧没有限制，可以是任何终结符和变量序列），则语法是上下文无关的。

我们可以将语法定义为一个四元组，其中V是一个有限集（变量），T是一个有限集（终结符），S是起始变量，R是一组有限规则，每个规则都是一个映射V
。

正则语法要么是右线性的，要么是左线性的，而上下文无关语法基本上是终结符和非终结符的任意组合。因此，我们可以说正则语法是上下文无关语法的子集。

在这些属性之后，我们可以说上下文无关语言集也包含正则语言集。

-1

基本上，常规语法是上下文无关语法的一个子集，但我们不能说每个上下文无关语法都是一般语法。主要的上下文无关语法是有歧义的，而常规语法可能也是有歧义的。

-4

一个正则文法从不会有歧义，因为它要么是左线性的，要么是右线性的，所以我们不能为正则文法制作两个决策树，因此它总是无歧义的。但除了正则文法之外，其他文法可能是正则的也可能不是。

5
一个常规语法可能是有歧义的。回想一下，如果存在两棵不同的语法树并且这些语法树被标记了，那么该语法就是有歧义的。因此，同构树是不同的树。例如，像 S -> aA | aB, B -> a, A -> a 这样简单的语法就是有歧义的，因为对于单词 'aa' 存在两棵同构但不同的语法树。 - Kai Kuchenbecker
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接