常规vs上下文免费语法

我正在攻读我的计算语言测试,并且有一个想法我遇到了问题.

我知道常规语法更简单,不能包含歧义,但不能完成编程语言所需的大量任务.我也理解无上下文语法允许模糊,但允许编程语言(如回文)所需的一些东西.

我遇到的问题是通过了解常规语法非终结符可以映射到终端或非终结符后跟终端,或者无上下文非终结符映射到终端和非终结符的任意组合,从而理解我如何得到以上所有内容.

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

1> Sujoy..：

---

常规语法是右或左线性的,而无上下文语法基本上是终端和非终端的任何组合.因此,您可以看到常规语法是无上下文语法的子集.

所以对于一个回文,例如,形式,

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

您可以清楚地看到,回文不能用常规语法表达,因为它需要是正确的或左对齐的,因此两侧都不能有非终端.

由于常规语法是非模糊的,因此对于给定的非终端只有一个生成规则,而在无上下文语法的情况下可以有多个生成规则.

---

第一:常规语法可能含糊不清(例如来自Kai Kuchenbecker:S - > aA | aB,B - > a,A - > a).唯一的问题是语法树中的节点只有一种方式可以定位(例如,当使用常规语法时,不存在关联性歧义).第二:非终端可以有多个右侧(A - > a,A - > aA;维基百科甚至包括epsilon作为第三种选择:http://en.wikipedia.org/wiki/Regular_grammar )

---

这个例子实际上是错误的.如果我们想象完整的规则是'A-> a | c`和`B-> b`然后这个语法允许非回文.例如,我可以产生:`S-> ABA-> aBA-> abA-> abc`.问题是我们不想在第一个规则中产生两个变量,而是两个终端.允许回文的语法的可能性是:`S - > aSa | bSb | a | B`

2> Charlie Mart..：

---

我想你想要考虑的是各种泵浦引理.常规语言可以通过有限自动机识别.无上下文语言需要堆栈,而上下文敏感语言需要两个堆栈(相当于说它需要一个完整的图灵机.)

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

现在,无上下文语言呢？对于无上下文语言,有一个类似的泵浦引理,它将语言中的字符串分为五个部分,uvxyz,并且语言的所有实例都在uv ⁱ xy ⁱ z中,因为i≥0.现在,你有两个 "非终结符号" " 只要您拥有相同的号码,就可以复制或抽取.

---

上下文敏感语言不需要完整的图灵机.线性有界自动机就足够了.这是一台图灵机,其磁带是有限的,其大小受输入字符串上的某些线性函数的限制.

3> stringRay201..：

---

常规和上下文自由语法之间的区别: (N,Σ,P,S):终端,非终端,产生,起始状态终端符号

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

●abc

非终结符号(或句法变量)

●根据生产规则由终端符号组替换

●ABC

常规语法:正确或左边的常规语法,正规语法,所有规则都遵循形式

B→a其中B是N中的非终结符,a是Σ中的终端

B→aC,其中B和C在N中,a在Σ中

B→ε其中B在N中,ε表示空字符串,即长度为0的字符串

留下常规语法,所有规则都遵守表格

A→a其中A是N中的非终结符,a是Σ中的终结符

A→Ba,其中A和B在N中,a在Σ中

A→ε,其中A是N,ε是空串

上下文无关语法(CFG)

○正式语法,其中每个生产规则的形式为V→w

○V是单个非终结符号

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

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：- 如果语法形式为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永远不会固有地模棱两可。