第三章文法和语言第三章文法和语言3.1文法的直观概念以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语。“我是大学生”。是汉语的一个句子〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉｜〈名词〉〈代词〉∷=我｜你｜他〈名词〉∷=王明｜大学生｜工人｜英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是｜学习〈直接宾语〉∷=〈代词〉｜〈名词〉3.2符号和符号串符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积定义为AB=xy|xA且yB。若集合A=ab,cde，B=0,1，则AB=ab1,ab0,cde0,cde1。使用*表示上的一切符号串（包括ε）组成的集合。Σ*称为Σ的闭包。上的除ε外的所有符号串组成的集合记为+。Σ+称为Σ的正闭包。例：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}指定字母表Σ，Σ*表示Σ上的所有有穷长的串的集合。Σ={0，1}Σ*={ε，0，1，00，01，10，11，000，001，010，…}Σ*=Σ0UΣ1UΣ2U…UΣnU…Σ*称为集合Σ的闭包:正闭包:Σ+=Σ1UΣ2U…UΣnU…Σ*=Σ0UΣ+Σ+=ΣΣ*=Σ*Σ3.3文法和语言的形式定义3.3文法和语言的形式定义3.3文法和语言的形式定义例例文法G=（VN，VT，P，S）VN={标识符，字母，数字}VT={a,b,c,…x,y,z,0,1,…,9}P={<标识符>→<字母><标识符>→<标识符><字母><标识符>→<标识符><数字><字母>→a,…,<字母>→z<数字>→0,…,<数字>→9}S=<标识符>很多时候不用将文法的四元组显式地表示出来，而只将产生式写出。一般约定：第一条产生式的左部是识别符号；用尖括号括起来的是非终结符号；不用尖括号括起来的是终结符号。或者用大写字母表示非终结符号，小写字母表示终结符号。如：G:S0S1S01文法的写法1G：S→aAbA→abA→aAbA→ε2G[S]：S→aAbA→abA→aAbA→ε3G[S]：S→aAbA→ab|aAb|ε3.3文法和语言的形式定义推导的举例例：G：S→0S1，S→010S100S1100S11000S111000S11100001111S0S100S11000S11100001111S=>+00001111S=>*S00S11=>*00S113.3文法和语言的形式定义例：G[E]：E→E+T|TT→T*F|FF→(E)|aEE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a句子：用符号a，+，*，(和)构成的算术表达式3.3文法和语言的形式定义例1：G：S→0S1，S→01L(G)={0n1n|n≥1}例2文法G[S]：（1）S→aSBE（2）S→aBE（3）EB→BE（4）aB→ab（5）bB→bb（6）bE→be（7）eE→eeL（G）={anbnen|n≥1}使用产生式(1)n-1次，得到推导序列：S=>*an-1S(BE)n-1，然后使用产生式(2)一次，得到：S=>*an-1S(BE)n-1an(BE)n。然后从an(BE)n继续推导，总是对EB使用产生式(3)的右部进行替换，而最终在得到的串中，所有的B都先于所有的E。例如，若n=3,aaaBEBEBEaaaBBEEBEaaaBBEBEEaaaBBBEEE。即有：S=>*anBnEn接着，使用产生式(4)一次，得到S=>*anbBn-1En，然后使用产生式(5)n-1次得到：S=>*anbnEn，最后使用产生式(6)一次，使用产生式(7)n-1次，得到：S=>*anbnen也能证明，对于n≥1，串anbnen是唯一形式的终结符号串文法的等价3.4文法的类型3.4文法的类型文法的类型文法的类型3型文法文法和语言文法和语言3.5上下文无关文法及其语法树例文法G=(｛E｝,｛+,*,i,(,)｝,P,E)其中P为：{E→i,E→E+E,E→E*E,E→(E),〈赋值语句〉→i∶=E}E表示算术表达式,i表示程序的“变量”，该文法定义了由变量，+，*,(和)组成的算术表达式的语法结构，即：变量是算术表达式；若E1和E2是算术表达式，则E1+E2，E1*E2和(E1)也是算术表达式描述一种简单