111

我正在为我的计算语言测试而学习，并且有一个想法是我遇到了问题。

我明白常规语法更简单，不能包含歧义，但不能完成编程语言所需的大量任务。我还理解上下文无关语法允许歧义，但允许一些编程语言所必需的东西（如回文）。

我遇到的问题是通过知道常规语法非终结符可以映射到终结符或非终结符后跟终结符或上下文无关的非终结符映射到终结符和非终结符的任何组合来了解我如何推导出上述所有内容.

有人可以帮我把所有这些放在一起吗？

4

8 回答 8

82

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

因此，例如，回文的形式是，

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

您可以清楚地看到回文不能用常规语法表示，因为它需要是右线性或左线性，因此两边都不能有非终结符。

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

于 2009-02-18T05:35:47.783 回答
60

我认为您要考虑的是各种抽水引理。正则语言可以被有限自动机识别。上下文无关语言需要一个栈，上下文相关语言需要两个栈（相当于说它需要一个完整的图灵机。）

因此，如果我们考虑常规语言的抽引引理，它本质上是说，任何常规语言都可以分解为三部分，x、y和z，其中语言的所有实例都在xy*z（其中 * 是 Kleene 重复，即y的 0 个或多个副本。）您基本上有一个可以扩展的“非终结符”。

现在，上下文无关语言呢？对于上下文无关语言，有一个类似的抽水引理，它将语言中的字符串分成五个部分，uvxyz，并且语言的所有实例都在uv i xy i z中，因为 i ≥ 0。现在，你有两个“非终结符” “只要你有相同的号码，就可以复制或抽水。

于 2009-02-18T05:36:43.147 回答
20

正则文法和上下文无关文法的区别： (N, Σ, P, S)：终结符、非终结符、产生式、起始状态终结符

● 由形式文法定义的语言的基本符号

● 美国广播公司

非终结符号（或句法变量）

● 根据生产规则替换成组的端子符号

● ABC

正则文法：右或左正则文法 右正则文法，所有规则服从形式

  1. B → a 其中 B 是 N 中的非终结符，a 是 Σ 中的终结符
  2. B → aC 其中 B 和 C 在 N 中，a 在 Σ 中
  3. B → ε 其中B在N中，ε表示空字符串，即长度为0的字符串

左正则文法，所有规则服从形式

  1. A → a 其中 A 是 N 中的非终结符，a 是 Σ 中的终结符
  2. A → Ba 其中 A 和 B 在 N 中，a 在 Σ 中
  3. A → ε 其中 A 在 N 中，ε 是空字符串

上下文无关语法 (CFG)

○ 形式文法，其中每个产生式规则的形式为 V → w

○ V 是单个非终结符

○ w 是一串终结符和/或非终结符（w 可以为空）

于 2015-05-13T19:29:42.230 回答
7

正则语法：-包含如下产生式的语法是 RG：

V->TV or VT
V->T

其中 V = 变量和 T = 终端

RG 可能是左线性语法或右线性语法，但不是中间线性语法。

众所周知，所有 RG 都是线性语法，但只有左线性或右线性语法是 RG。

常规语法可能是模棱两可的。

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

歧义语法：-对于字符串 x，它们存在多个 LMD 或多个 RMD 或多个 Parse 树或一个 LMD 和一个 RMD，但两者都产生不同的 Parse 树。

                S                   S

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

这个语法是模棱两可的语法，因为有两个解析树。

CFG:- 如果它的生产形式为 CFG，则称其为 CFG 的语法：

   V->@   where @ belongs to (V+T)*

DCFL： -众所周知，所有 DCFL 都是 LL(1) 语法，所有 LL(1) 都是 LR(1)，所以它永远不会模棱两可。所以 DCFG 永远不会模棱两可。

我们也知道所有 RL 都是 DCFL，所以 RL 永远不会模棱两可。请注意，RG 可能是模棱两可的，但 RL 不是。

CFL: CFl 可能有歧义，也可能没有歧义。

注意： RL 永远不会是固有的模棱两可。

于 2013-07-26T20:07:38.823 回答
5

常用表达

  • 词法分析的基础
  • 代表常规语言

上下文无关语法

  • 解析基础
  • 表示语言结构

在此处输入图像描述

于 2013-01-16T05:07:36.233 回答
3

如果所有产生式规则都具有以下形式，则文法是上下文无关的：A（即，规则的左侧只能是单个变量；右侧不受限制，可以是终端和变量的任何序列）。我们可以将语法定义为 4 元组，其中 V 是有限集（变量），_ 是有限集（终端），S 是起始变量，R 是有限规则集，每个规则都是一个映射V
正则文法是右线性或左线性，而上下文无关文法基本上是终结符和非终结符的任意组合。因此我们可以说正则文法是上下文无关文法的一个子集。在这些属性之后，我们可以说上下文无关语言集还包含常规语言集

于 2011-06-30T15:28:41.527 回答
-1

基本上正则语法是上下文无关语法的一个子集，但我们不能说每个上下文无关语法都是正则语法。主要是上下文无关语法是模棱两可的，而常规语法可能是模棱两可的。

于 2013-03-03T14:51:22.367 回答
-4

正则语法永远不会模棱两可，因为它要么是左线性的，要么是右线性的，所以我们不能为正则语法制作两个决策树，所以它总是明确的。但除了正则语法之外，所有这些都可能是正则的，也可能不是正则的

于 2011-04-21T09:46:46.583 回答