资源描述：
《编译原理第2章 编译基础.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第二章编译基础1§2.0概述对程序设计语言的描述是从语法、语义和语用三个因素来考虑。语法是对语言结构的定义。语用则是从使用的角度去描述语言。语义是描述了语言的含义。2§2.0概述例如赋值语句s＝2*3.1416*r的非形式化的描述为：语法：赋值语句由一个变量，后随一个赋值号“＝”，再在其后面跟一个表达式构成。语义：首先计算语句右部表达式的值，然后把所得结果送给左部变量中。语用：赋值语句可用来计算和保存表达式的值。这种非形式化的描述,不够清晰和准确,为了精确定义和描述程序设计语言,需采用形式化的方法。3形式化方法：是用一整套带有严格规定的符号体系来描述问
2、题的方法。§2.1符号表一．符号串与字母表1．字母表：元素的非空有穷集合。两含义：①字母表中至少包含一个元素。②字母表中元素可以是字母、数字或其它符号。例如：∑={a,b,c}42.符号（字符）：字母表中元素。3.符号串：用字母表中的符号组成的任何有穷序列，也称字。例如：a,ab,bba,acab,…注意：①符号串中符号的顺序是很重要的。②不包含任何符号的符号串称空串，记为ε。
3、ε
4、=0③一个字母表上全部符号的集合是无穷的。54.符号串的前缀、后缀以及子串：设x是一符号串，例如：x=abc符号串的前缀：从x的尾部删除若干个（>=0）符号后所余下的部分。
5、例如：ε，a，ab，abc符号串的后缀：从x的头部删除若干个（>=0）符号后所余下的部分。例如：ε，c，bc，abc子串：从x中删除前缀和后缀之后所余下的部分。例如：ε，a，b，ab，bc，abc6二.符号串的运算1．符号串的连接：设x，y是符号串，则串xy称为它们的连接。例如：设x=myy=computerxy=mycomputeryx=computermy注意：对任意xXε=εX=X2．集合的和与乘积：设A，B是符号串的集合，则：A∪B={ω
6、ω∈A或ω∈B}AB={xy
7、x∈A且y∈B}例如：设A={a,b}B={c,d}则：A∪B={a,b,c
8、,d}AB={ac,ad,bc,bd}注意：Φ∪A=A∪Φ=AΦA=AΦ=Φ{ε}A=A{ε}=AΦ={}≠{ε}73.符号串的幂运算：若x是符号串，则x0=ε,x1=x,x2=xx,…例如：设x=abc则：x0=ε,x1=abc,x2=abcabc,…4.集合的幂运算：若A是符号串的集合，则A0={ε},A1=A,A2=AA,…例如：设A={a,b}则：A0={ε},A1={a,b},A2={aa,ab,ba,bb},…5.集合的A＋(正闭包)和A*（自反传递闭包）:设A为任一集合，则：A＋=A1∪A2∪A3∪…∪An∪…（A上所有符号串所组成的集合
9、）A*=A0∪A＋={ε}∪A＋例如：设A={a,b,c}A＋={a,b,c,aa,ab,ac,ba,bb,bc,…}A*={ε,a,b,c,aa,ab,ac,ba,bb,bc,…}8§2.2文法和语言的形式定义一．形式语言：是一字母表上按某种规则构成的所有符号串的集合。反之，任一字母表上符号串的集合均可定义为一个形式语言。二．形式语言的描述：（三种方法）1．当语言为有穷集合时，用枚举法。例如：设有字母表A={a,b,c}则：L1={a,b}L2={a,aa,ab,ac}L3={c,cc}92．用文法描述语言例如：设有字母表∑={0，1}∑+={0，1
10、，00，01，11，10，000，100，…}用A表示∑+，A→0（定义为，生成，导出）用产生式表示∑+：A→0A→1A→A0A→A13．用自动机识别语言：构造一种装置来识别语言，它可以判断某符号串是否是该语言的句子。例如：1100→→是（接收）11ab→→不是（不接收）自动机10三．文法的形式定义1．规则（产生式）：是一个符号与一个符号串的有序对（A，α），通常写作：A→α或A∷=α2．非终结符与终结符：非终结符：出现在规则左部能派生出符号或符号串的那些符号。通常用大写字母表示。终结符：是组成语言不可再分的基本符号，通常用小写字母表示。113．文法的
11、形式定义：是规则的非空有穷集合，通常定义为四元组：G[S]=（Vn，Vt，P，S）其中：Vn：规则中非终结符的集合。Vn={A}Vt：规则中终结符的集合。Vt={0，1}P：文法规则式的集合。P:A→0A→1A→A0A→A1S：文法的开始符号（识别符号）由它开始识别我们所定义的语言。S=A例1例2例3例4例5继续12例1．设有字母表∑={a，b}，请为语言L={a2n,b2n
12、n>=1}设计一个文法。首先分析语言中串的结构特征：L={aa,bb,aaaa,bbbb,…}（偶数个a或偶数个b组成）G[S]=（Vn，Vt，P，S）其中：Vn={A,B,D}
13、Vt={a，b}P:A→aa
14、aaB
15、bb
16、bbDB→aa
17、aaBD→bb
18、bbDS=A易错：
