常规语法与上下文无关语法

Question

我正在学习计算语言测试，有一个想法我无法理解。

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

我遇到的困难是理解如何通过知道常规语法非终结符可以映射到一个终结符或一个非终结符后跟一个终结符或一个上下文无关的非终结符映射来导出上述所有内容终结符和非终结符的任意组合。

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

Answer 1

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

例如，对于回文，其形式为，

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

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

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

Answer 2

我认为你要考虑的是各种泵引理。 常规语言可以被有限自动机识别。 上下文无关语言需要一个堆栈，而上下文相关语言需要两个堆栈（这相当于说它需要一个完整的图灵机。）

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

现在，上下文无关语言怎么样？ 有一个类似的上下文无关语言的泵引理，它将语言中的字符串分成五个部分，uvxyz，并且该语言的所有实例都在 uvⁱxyⁱz 中，其中 i ≥ 0. 现在，您有两个可以复制或泵送的“非终结符”，只要您具有相同的数字。

Answer 3

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

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

● abc

非终结符（或句法变量）

● 根据以下规则被终结符组替换产生式规则

● ABC

正则语法：右正则或左正则语法
正确的正则语法，所有规则都遵循以下形式

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

左正则语法，所有规则遵循形式

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

上下文无关语法 (CFG)

○ 正式语法，其中每个产生式规则都是形式为 V → w

○ V 是单个非终结符

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

Answer 4

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

V->TV or VT
V->T

其中 V=变量且 T=终端

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

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

常规语法可能是二义性的。

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

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

                S                   S

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

这个语法是二义性语法，因为有两个解析树。

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

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

：- 正如我们所知，所有 DCFL 都是 LL(1) 语法并且所有 LL(1)是 LR(1) 所以它永远不会有歧义。 所以DCFG是Never be ambigful。

我们还知道所有 RL 都是 DCFL，因此 RL 永远不会含糊不清。 请注意，RG 可能不明确，但 RL 则不然。

CFL： CFL 可能含糊，也可能不含糊。

注意： RL 本质上永远不会含糊不清。

Answer 5

正则表达式

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

上下文无关语法 解析

• 基础
• 表示语言结构

Answer 6

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

Answer 7

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

Answer 8

常规语法永远不会含糊，因为它要么是左线性的，要么是右线性的，所以我们不能为常规语法制作两个决策树，所以它总是明确的。但除了常规语法之外，所有语法都可能是或可能不是常规的