上下文无关文法:在编译原理中，什么是上下文无关文法？什么是语言？

1.在编译原理中，什么是上下文无关文法？什么是语言？

二型文法如下:S->AcS->ScA->abA->aAb三型文法如下:S->aSA->bAB->cBB->cA->BbA、2型文法是上下文无关文法，表现在产生式上就是产生式的左部只有一个非终结符；3型文法从广义上讲包括左线形文法、右线形文法和正规文法。B、左线形文法产生式的右部要么没有非终结符，如果有非终结符也只能有一个，且必须位于产生式右部的最左端。C、右线形文法产生式的右部要么没有非终结符，如果有非终结符也只能有一个，且必须位于产生式右部的最右端。D、正规文法是右线形文法的一个子集，其产生式右部只有三种情况：1）空串2）只有一个终结符3）只有一个终结符后接一个非终结符E、所有的3型文法都是2型文法。

2.一个上下文无关文法G包括四个组成部分依次为：一组——，一个——，一组——，一组——。

上下文无关文法CFG包含：一组终结符，一组非终结符，一个文法的开始符号。

3.如何定义上下文无关文法？

上下文无关文法（Content-Free Grammar,上下文无关文法取名为“一个形式语言是上下文无关的，如果它是由上下文无关文法生成的（条目上下文无关语言）。上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法；几乎所有程序设计语言都是通过上下文无关文法来定义的。上下文无关文法又足够简单，使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的。BNF （巴克斯-诺尔范式）经常用来表达上下文无关文法。文法规则使用相似的表示法。名字用斜体表示（但它是一种不同的字体，所以可与正则表达式相区分）。竖线仍表示作为选择的元符号。但是这里没有重复的元符号（如正则表达式中的星号*），表示法中的另一个差别是现在用箭头符号“代替了等号来表示名字的定义。这是由于现在的名字不能简单地由其定义取代，而需要更为复杂的定义过程来表示，这是由定义的递归本质决定的。同正则表达式类似，文法规则是定义在一个字母表或符号集之上。这些符号通常就是字符。

4.用上下文无关文法表示： 所有不是ww形式的a和b的串的集合，也就是所有不是一个串重复两遍的串的集合。

S->aAb三型文法如下:S->bAB->cBB->cA->表现在产生式上就是产生式的左部只有一个非终结符；3型文法从广义上讲包括左线形文法、右线形文法和正规文法。B、左线形文法产生式的右部要么没有非终结符，且必须位于产生式右部的最左端。C、右线形文法产生式的右部要么没有非终结符，如果有非终结符也只能有一个，且必须位于产生式右部的最右端。

5.一个上下文无关文法生成句子abbaa的推导树如图

(1)串abbaa最左推导:ABS=>abbS=>abbaa最右推导：S=>ABS=>Abbaa=>abbaa(2)产生式有：S→ABS|Aa|εA→a B→SBB|b可能元素有：εaa ab abbaa aaabbaa……(3)该句子的短语有：

6.{wcw^R|w∈{a,b}*}编译原理上下文无关文法怎么做?

S -> aSa | bSb | c

7.上下文无关文法的文法形式

在两种符号置换的意义下(终结符和非终结符分别替换),把一组彼此相似的文法抽象成一个更高级的形式体系，文法形式的研究主要集中在上下文无关文法上。文法形式的具体定义是：给定无限的终结符表Σ∞和无限的非终结符表V∞。任取Σ∞和V∞的非空子集Σ和V,按构造普通文法的方法定义一个四元组G=(Σ，任取映射函数ψ，把Σ中每一元素a映为Σ∞中一有限子集ψ(a)，把V中每一元素A映为V∞中一个有限子集ψ(A),且当A厵B时有ψ(A)∩ψ(B)=φ。ψ就是所需的置换。通过它得到一个具体文法ψ(G)=【ψ(Σ)，ψ(V),ψ(S),ψ(P)】,其中ψ(P)是把P中所有产生式中的符号作ψ置换后得到的一组新产生式，ψ(Σ),ψ(V)和ψ(S)分别是ψ(P)中出现的终结符集，这样的G称为文法形式，ψ称为G的一个解释，ψ(G)是G的一个解释文法，令ψ遍历各种可能的解释,得到的ψ(G)集合称为G的文法性语言族，由此生成的语言集合(ψ(G))称为G的文法性语言族。文法形式{S→aS，S→a}的文法性语言族是正则语言集;{S→SS，S→a}的文法性语言族是上下文无关语言集。若文法形式G作为普通文法时生成的语言(G)是无限集，则称G为非平凡的。此时文法性语言族(G)是一个满主半AFL，如满主半AFL({ab│n≥1})，以G1·G2表文法性语言族G1和G2的乘积,正则语言集和线性语言集都是素文法性语言族。任一文法性语言族G必可唯一地分解为它的素因子乘积和：G=(11…1n1)∪…∪(m1…mnm)。这个分解在乘积运算∪可交换的意义下是唯一的。