编译原理第2章 编译基础.ppt

编译原理第2章 编译基础.ppt

ID:51497021

大小:160.50 KB

页数:53页

时间:2020-03-25

编译原理第2章 编译基础.ppt_第1页
编译原理第2章 编译基础.ppt_第2页
编译原理第2章 编译基础.ppt_第3页
编译原理第2章 编译基础.ppt_第4页
编译原理第2章 编译基础.ppt_第5页
资源描述:

《编译原理第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易错:

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。