正则语法与上下文无关语法

我正在为 电脑语言测试做准备，有一个想法我不太明白。

我知道 常规语法比较简单，不能包含歧义，但是不能完成编程语言所需的许多任务。我也理解 上下文无关语法允许歧义，但是允许一些编程语言所必需的东西(比如回文)。

我遇到的问题是，如果我知道 正则语法非终结语法可以映射到一个终端或非终端后面跟着一个终端，或者一个上下文无关的非终端映射到终端和非终端的任意组合，那么我如何能够推导出上述所有内容。

有人能帮我把这些拼起来吗？

136783 次浏览
小开
最佳答案

规则文法是右线性或左线性，而上下文无关文法基本上是终端和非终端的任意组合。因此，你可以看到，规则语法是上下文无关文法的一个子集。

比如回文，它的形式是,

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

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

Since regular grammars are non-ambiguous, there is only one production rule for a given non-terminal, whereas there can be more than one in the case of a context-free grammar.

小开

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

所以，如果我们考虑一下 为常规语言抽取引理，它实际上说的是，任何一种常规语言都可以被分解成三个部分: X、 嘿和 Z，其中所有的语言实例都在 Xy * z中(其中 * 是 Kleene 重复，即 嘿的0个或更多的副本)你基本上有一个可以展开的“非终端”。

那么，无上下文语言呢？还有一个类似的 抽取上下文无关语言的引理，它将语言中的字符串分成五个部分，即 嗡嗡，其中语言的所有实例都在 Uv < sup > i xy < sup > i z中，即 i & ge; 0。现在，你有 二“非终端”，可以复制，或泵，只要你有相同的号码。

小开

一个正则语法从来不会有歧义，因为它要么是左线性的，要么是右线性的，所以我们不能为正则语法建立两个决策树，所以它总是不歧义的。但是除了正则语法之外，所有的语法都可能是正则的，也可能不是正则的

小开

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

小开

正则表达式

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

上下文无关语法

  • 解析的基础
  • 表示语言构造

enter image description here

小开

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

小开

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

V->TV or VT
V->T

其中 V = 变量 T = 终端

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

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

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

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

Ambiguous Grammar:- for a string x their exist more than one LMD or More than RMD or More than one Parse tree or One LMD and One RMD but both Produce different Parse tree.

                S                   S


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

这种语法之所以有二义性文法，是因为有两个解析树。

一种语法，如果它的结果是在形式上的，那么它就是 CFG:

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

DCFL:- as we know all DCFL are LL(1) Grammar and all LL(1) is LR(1) so it is Never be ambiguous. so DCFG is Never be ambiguous.

We also know all RL are DCFL so RL never be ambiguous. Note that RG may be ambiguous but RL not.

可以或不可以模棱两可。

注意: RL 永远不会有固有的二义性。

小开

规则语法和上下文无关语法的区别: (N，Σ，P，S) : 终端，非终端，产品，起始状态终端符号

* 正式语法所界定的语言的基本符号

●

非终止符号(或语法变量)

* 根据生产规则用一组终端符号代替

● ABC

规则语法: 右边或左边的规则语法 正确的规则语法，所有的规则都遵守形式

  1. 其中 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 中 ε 是空字符串

上下文无关文法

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

○ V 是一个单一的非终端符号

○ w 是终端和/或非终端的字符串(w 可以为空)


提交答案