第2章文法和形式语言任何一个程序设计语言都包含语法、语义和语用三个方面。语法：涉及语言的构成规律，即程序的结构或形式。语义：指语言所代表的含义。语用：涉及到语言的实际应用。例如：对于赋值语句x:=a+b*c非形式描述如下：1)语法：赋值语句有一个变量，后随一个符号“:=”，再在后跟一个表达式所构成。2)语义：赋值语句执行的过程是先对语句右部的表达式求值，然后把所得的结果与语句左部变量相结合，并取代该变量的原有值。3)语用：赋值语句可用来计算和保存表达式的值。形式化方法：简单地说，是用一整套带有严格规定的符号体系来描述问题的理论和方法。形式语言：是一种不考虑含义的符号语言，其理论主要研究组成这种符号串的集合，它们的表示法、结构及特性。只涉及符号的结构方式上的规定，而不涉及符号的含义，即形式语言只谈语法不谈语义。形式语言理论是编译理论的重要基础，但是仅用于程序设计语言的语法描述及语法分析。1.字母表和符号串：字母表：是一个非空有穷集合。习惯上用大写字母表示。字母表中至少要包含一个元素。例：字母表∑和V∑={a，b，c，d}V={0，1}符号：字母表中的元素成为符号或字符。不同的语言有不同的字母表，它都说明了该语言中所允许出现的一切字符。例：由上述字母表∑={a，b，c，d}则a、b、c、d即为该字母表的符号。符号串：符号的有穷序列。例：字母表Σ={a,b}ε,a,b,aa,ab,aabba,…,都是上的符号串。ε表示空符号串，不包含任何符号。与空格符号不同。此外，符号串中符号出现的顺序不同，符号串也不同。符号串集合：字母表∑上若干个符号串组成的集合。我们约定：小写字母：a,b,c,…,r表示符号小写字母：s,t,u,…,z表示符号串大写字母：A,B,C,…,Z表示符号串集合2.符号串的运算符号串的逆：设x是字母表∑上的符号串，其逆为符号串x的倒置。记为：注：空串的逆仍为本身。符号串集合的乘积：设A,B为两个符号串集合，其乘积为：AB={xy|x∈A,y∈B}注：由于εx=xε=x，则{ε}A=A{ε}=A。其中{ε}表示由空符号串ε组成的集合。空集不含任何元素的集合。记为：φ注：任何集合A有：φA=Aφ=φ这里的an表示n个a相连结的符号串，而不是n个a相乘。符号串集合的幂：设A为符号串集合，则符号串集合A的幂运算为：A0={ε}A1=AA2=AA……An=An-1A(=AAn-1)集合A的闭包与正闭包：集合A的闭包：用A*表示，也称为自反闭包或星闭包。其数学定义为：A*=A0∪A1∪A2∪…∪An∪…集合A的正闭包：用A+表示，其数学定义为:A+=A1∪A2∪…∪An∪…于是，A*=A0∪A+A+=AA*=A*A注：若A为字母表，则A*为长度为任意(包括空串)的所有符号串集，也即A*包含了字母表A上的所有符号所能组成的一切符号串，而任何一个语言都是某字母表上的符号串集合。1.文法和推导规则(产生式)：一个规则是一个二元组。写成：U::=x或U→x其中，U是规则的左部，为一个符号。x是规则的右部，为有穷符号串。“::=”或“→”表示“定义为”或“由…组成”。例如：如上例<句子>::=<主语><谓语><主语>::=<代词><代词>::=I<谓语>::=<动词><直接宾语><动词>::=love<直接宾语>::=<物主代词><名词><物主代词>::=my<名词>::=motherland其中，带有尖括号的称为语法成分或语法类，不带尖括号的称为单词符号或单词。文法与字汇表：文法(G[Z])是规则的非空有穷集合。通常称Z为识别符号或开始符号，它至少要在一条规则中作为左部出现。在所有的规则中，规则的左部和右部中的所有符号组成一个集合，称之为文法的字汇表，记为：V。例：设有文法G[<无符号整数>]由下列组成：<无符号整数>::=<数字串><数字串>::=<数字串><数字><数字串>::=<数字><数字>::=0<数字>::=1……<数字>::=9该文法的字汇表V为：V={0,1,…,9,<无符号整数>,<数字串>,<数字>}文法的BNF表示法(巴科斯范式表示)：引进“::=”和“|”符号，其中“::=”表示“定义为”。“|”表示“或”运用她把左部相同的规则缩写在一起。例如在上例也可以用以下的方法表示：<无符号整数>::=<数字串><数字串>::=<数字串><数字>|<数字><数字>::=0|1|2|…|9直接推导与直接归约：通过推导，可得到合乎文法的句子。定义：对于文法G，有规则：U::=ux和y是V上的符号串(可以是空串)，若V上存在另外两个符号串v和w，使v=xUy,w=xuy则称v可直接推导出w，或称w可直接归约到v。分别记为：vw，wv特别地，若x=y=ε，则Uu，uU。其实