定期与上下文无关文法
我正在学习我的计算机语言testing，有一个想法，我有问题包扎我的头。
我明白， 正规的语法比较简单，不能含有歧义，但是不能完成许多编程语言所需的任务。 我也明白， 上下文无关语法允许含糊不清，但允许编程语言（如回文）所需的一些东西。
我遇到的麻烦是理解如何通过知道规则语法非终止符可以映射到一个terminal或一个非终结符跟随terminal或上下文无关非终结符映射到任何terminal和非终结符的组合。
有人能帮我把所有这些放在一起吗？
正则语法既可以是正确的也可以是左边的，而上下文无关语法基本上是terminal和非terminal的任意组合。 因此，您可以看到正则语法是上下文无关语法的一个子集。
所以对于回文来说，就是这样的forms，
S->ABA A->something B->something 您可以清楚地看到，回文不能用正则语法expression，因为它需要是正确的或者是左边的线性的，因此两边都不能有非terminal。
由于常规语法是非歧义的，对于给定的非terminal，只有一个生产规则，而在上下文无关语法的情况下可以有多于一个。
我想你想要的是各种抽油烟机。 普通语言可以被有限自动机识别。 上下文无关的语言需要一个堆栈，上下文敏感的语言需要两个堆栈（这相当于说它需要一个完整的图灵机）。
因此，如果我们考虑普通语言的抽象引理 ，它实质上就是说任何正规的语言都可以被分解为三部分， x ， y和z ，其中语言的所有实例都是xy * z （其中*是Kleene重复，即y的 0个或更多个副本）。基本上有一个可以扩展的“非终结点”。
现在，上下文无关的语言呢？ 对于上下文无关的语言 ，有一个类似的抽象 引理 ，将语言中的string分为五个部分， uvxyz ，当语言的所有实例都在uv i xy i z中时 ，i≥0。现在，有两个 “非终结符“ 只要你有相同的号码 ，就可以复制或抽取。
规则和上下文无关语法的区别： （N，Σ，P，S）：terminal，非terminal，产品，起始状态terminal符号
●由正式语法定义的语言的基本符号
●abc
非终结符号（或者语法variables）
●根据生产规则，由terminal符号组代替
●ABC
正规语法：正确的语法或正确的语法正确的语法，所有的规则都遵守forms
- B→a其中B是N中的非终结符，a是Σ中的终结符
- B→aC其中B和C在N中，a在Σ中
- B→ε其中B在N中，ε表示空串，即长度为0的串
留下正规的语法，所有的规则都遵从这些forms
- A→a其中A是N中的非终结符，a是Σ中的终结符
- A→Ba其中A和B在N中，a在Σ中
- A→ε其中A在N中，ε是空串
上下文无关语法（CFG）
○正式语法，其中每个生产规则的formsV→W
○V是单个非终结符号
○w是一串terminal和/或非terminal（w可以是空的）
常用expression
- 词法分析的基础
- 代表常规语言
上下文无关文法
- parsing的基础
- 代表语言结构
如果所有生产规则的forms如下：A（也就是说，规则的左边只能是单个variables，右边是不受限制的，可以是任何terminal和variables的序列），语法是上下文无关的。 我们可以将一个语法定义为一个四元组，其中V是一个有限集（variables），_是一个有限集（terminal），S是起始variables，R是一组有限的规则，每个规则都是一个映射V
正则语法既可以是正确的也可以是左边的，而上下文无关语法基本上是terminal和非terminal的任意组合。 因此我们可以说正则语法是上下文无关语法的一个子集。 在这些属性之后，我们可以说上下文自由语言集也包含正则语言集
常规语法： –包含生产的语法如下：RG：
V->TV or VT V->T
其中V =variables和T =terminal
RG可以是左线性语法或右线语法，但不是中线性语法。
我们知道所有的RG都是线性语法，但只有左线性或右线性语法是RG。
正则语法可能不明确。
S->aA|aB A->a B->a
不明确的语法： –对于一个stringx，它们存在多于一个的LMD或者多于RMD或多于一个的分析树或者一个LMD和一个RMD，但是都产生不同的分析树。
SS / \ / \ a A a B \ \ aa
这个语法是因为两个parsing树而模棱两可的语法。
CFG： –如果产品的forms是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永远不会固有含糊。
基本上，规则语法是上下文无关语法的一个子集，但是我们不能说每个上下文的自由语法都是一个正规的语法。 主要是上下文无关语法是模棱两可的，正则语法可能是模糊的。
一个规则的语法从不含糊，因为它是左线性或右线性的，所以我们不能为正规语法做出两个决策树，所以它总是毫不含糊。但是比正规语法其他都可能是或不是常规的
