资源描述：
《编译原理第二章 (2).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第2章文法和形式语言2.1符号和符号串2.2文法和语言2.3语法树和二义性2.4文法的实用限制2.5扩充的BNF2.6文法和语言分类2.7正则表达式与正则集任何一个程序设计语言都包含语法、语义和语用三个方面。语法：涉及语言的构成规律，即程序的结构或形式。语义：指语言所代表的含义。语用：涉及到语言的实际应用。例如：对于赋值语句x:=a+b*c非形式描述如下：1)语法：赋值语句有一个变量，后随一个符号“:=”，再在后跟一个表达式所构成。2)语义：赋值语句执行的过程是先对语句右部的表达式求值，然后把所得的结果与语句左部变量相结合，并取代该变量的原有值。3)语用：赋值语句可用来计算和保存表达式的值。形
2、式化方法：简单地说，是用一整套带有严格规定的符号体系来描述问题的理论和方法。形式语言：是一种不考虑含义的符号语言，其理论主要研究组成这种符号串的集合，它们的表示法、结构及特性。只涉及符号的结构方式上的规定，而不涉及符号的含义，即形式语言只谈语法不谈语义。形式语言理论是编译理论的重要基础，但是仅用于程序设计语言的语法描述及语法分析。2.1符号和符号串任何一种语言都是由该语言的基本符号组成的符号串集合。1.字母表和符号串：字母表：是一个非空有穷集合。习惯上用大写字母表示。字母表中至少要包含一个元素。例：字母表∑和V∑={a，b，c，d} V={0，1}符号：字母表中的元素成为符号或字符。不同的语言
3、有不同的字母表，它都说明了该语言中所允许出现的一切字符。例：由上述字母表∑={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,y是字母表∑上的两个符号串，若x与y的诸符号依次相等，则符
4、号串x,y相等。记为：x=y符号串的长度：设x为字母表∑上的符号串，符号串中包含的符号的个数称为符号串x的长度。用
5、x
6、表示。符号串的连结：设x,y是字母表∑上的两个符号串，把y的所有符号相继写在x的符号之后所得到的符号串称之为x与y的连结。用xy表示。注：εx=xε=x（字母表上的任意一个符号串x与空串ε的连结仍然还是x。）xy≠yx(符号串的连结运算的交换律不成立。）符号串的逆：设x是字母表∑上的符号串，其逆为符号串x的倒置。记为：注：空串的逆仍为本身。x~符号串的前缀、后缀和子串：设x,y,z是字母表∑上的符号串，则称x为符号串xy的前缀。y是符号串xy的后缀。y是符号串xyz的子串。x
7、,y都是xy的子串。符号串集合的乘积：设A,B为两个符号串集合，其乘积为：AB={xy
8、x∈A,y∈B}注：由于εx=xε=x，则{ε}A=A{ε}=A。其中{ε}表示由空符号串ε组成的集合。空集不含任何元素的集合。记为：φ注：任何集合A有：φA=Aφ=φ而ε为空串（不含任何字符的字符串）ε为由空字符串ε组成的集合，有{ε}A=A{ε}=A空集合φ并不包含空串ε,即ε∈φ字符串的幂：设x是字母表∑上的符号串，则x的幂运算为：x0=ε x1=x x2=xx ……xn=xn-1x(=xxn-1)这里的an表示n个a相连结的符号串，而不是n个a相乘。符号串集合的幂：设A为符号串集合，则符号串集合A的
9、幂运算为：A0={ε} A1=A A2=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上的所有符号所能组成的一切符号串，而任何一个语言都是某字母表上的符号串集合。2.1文法和语言文法：是对语言结构的定义和描述，也就是说在形式上用以描述和规定语言结构的。例如：有英文单词串：I
10、lovemymotherland.从结构上完全符合英文文法。1.文法和推导规则(产生式)： 一个规则是一个二元组。写成：U::=x或U→x其中，U是规则的左部，为一个符号。x是规则的右部，为有穷符号串。“::=”或“→”表示“定义为”或“由…组成”。例如：如上例 <句子>::=<主语><谓语> <主语>::=<代词><代词>::=I <谓语>::=<动词><直接宾语> <动词>::=love <直
