《编译原理》第4章课件.ppt

ID:58216143

大小:1.36 MB

页数:103页

时间:2020-09-05

《编译原理》第4章课件.ppt_第1页
《编译原理》第4章课件.ppt_第2页
《编译原理》第4章课件.ppt_第3页
《编译原理》第4章课件.ppt_第4页
《编译原理》第4章课件.ppt_第5页
资源描述:

《《编译原理》第4章课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第四章词法分析学习目标:理解通常的单词分类和构词规则会使用单词的描述和识别机制明确词法分析在编译过程所处的阶段和作用掌握词法分析程序的手工实现方法1【学习指南】词法分析程序是编译程序的一个构成成分,它的主要任务是扫描源程序,按构词规则识别单词,并报告发现的词法错误。词法分析也是语法分析的一部分,把词法分析从语法分析中独立出来是为了使编译程序结构清晰,也是为了便于使用自动构造工具,提高编译效率。本章首先介绍正规式和其对单词的描述,然后讲述有穷自动机理论,最后介绍词法分析程序的功能和设计原则。2【难重点】

2、正规式的定义——如何用作单词的描述工具有穷自动机的定义和分类——如何用作单词的识别系统正规式到有穷自动机的转换算法——词法分析程序的自动构造原理如何设计和实现词法分析程序3知识体系词法分析功能-分割符号串形式的源程序,得到单词串输入-字符串形式的源程序输出-单词串分析方法-超前搜索程序设计方法-步(1)画框图-最小化DFA的状态转换图步(2)由框图编写程序NFADFA子集法化简最小化DFA正规文法正规式转换规则转换规则其中“步(1)”画框图涉及的内容如下:44.1单词的描述工具程序设计语言中的单词是基

3、本语法成分。单词符号的语法可以用有效的工具加以描述,并且基于这类描述工具,实现词法分析程序的自动构造。词法单词符号的文法,用来描述高级语言中的标识符、常数、运算符、分界符、关键字单词的描述工具正规文法正规式识别工具:有穷自动机(FiniteAutomata)5为什么要用正规式而不用上下文无关文法来定义语言的词法?语言的词法规则通常非常简单,不必用强大的文法来描述;对于单词,正规式比上下文无关文法提供了更简洁且易于理解的定义;从正规式可自动地构造出有效的词法分析器,其它文法很难;把语言的语法结构分成词法

4、和非词法两部分为编译其前端的模块划分提供了方便的途径。6(右线性):AaBAa(左线性):ABaAaaVT{}如:程序设计语言(l表示a~z中的任一英文字母,d表示0~9中的任一数字。)<标识符>l<字母数字>

5、l<字母数字>l

6、d

7、l<字母数字>

8、d<字母数字><无符号整数>d

9、d<无符号整数><运算符>+

10、-

11、*

12、/

13、=

14、<<等号>

15、><等号><等号>=<保留字>if

16、while

17、else一、正规文法(3型文法)7在一个正规文法中不允许既用右线性文法又用左线性文法。由正规

18、文法产生的语言称作正规集。正规集是一个有穷或者无穷的集合,可用正规式(RegularExpression,Re)来描述。正规式也称正则表达式,正规表达式是说明单词的模式(pattern)的一种重要表示法(记号),是定义正规集的数学工具。正规式描述的集合称作正规集。说明:8正规文法、正规集与正规式三个概念间关系一个正规语言可以用正规文法定义,也可以用正规式定义,对任意一个正规文法,存在一个定义同一个语言的正规式;同样,对每个正规式,存在一个生成同一语言的正规文法;有些正规语言很容易用文法定义,有些则用正

19、规式定义更容易;两者之间是可以转换的,结构上具有等价性。由正规文法或正规式定义的正规语言的集合构成正规集。9是字母表={,,,,*,(,)}正规式正规式表达的语言(正规集)1.,{},2.a,a{a}3.若e1,e2L(e1),L(e2)则(a)e1e2(或)L(e1)L(e2)(b)e1e2(连接)L(e1)L(e2)(c)e1*(闭包)(L(e1))*(d)(e1)L(e1)4.仅由有限次使用上述三步骤而定义的表达式才是正规式二、正规式的定义(递归定义)10注(1)

20、“*”,“”,“”运算左结合,优先级由高到低。(2)可省略。(3)不产生混乱的情况下,可将圆括号略去。如:((r(s*))r)=rs*rr*(s*r)圆括号不可略去(4)“(”,“)”并非正规式的运算符。例:=a,b(a)正规式:ab正规集:a,b(b)正规式:(ab)(ab)正规集:aa,ab,ba,bb11(c)正规式:a*正规集:,a,aa,aaa,aaaa,…(d)正规式:(ab)*正规集:{,a,b,aa,ab,ba,bb,aaa,...(e)

21、正规式:aab*正规集:a后跟随大于等于0个b的所有符号串(f)正规式:(ab)*(aabb)(ab)*正规集:所有含有两个相继a或b的符号串(g)正规式:(aabaabbb)*正规集:空串和任何长度为偶数的a,b符号串(h)正规式:(ab)*abb正规集:任何以abb结尾的a,b符号串12例:=A,B,…,Z,a,b,…,z,0,1,…,9正规式:letter=A

22、B…

23、Z

24、a

25、b…

26、z正规集:L(A)L(B)…L(Z)L(a

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

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

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

《《编译原理》第4章课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第四章词法分析学习目标:理解通常的单词分类和构词规则会使用单词的描述和识别机制明确词法分析在编译过程所处的阶段和作用掌握词法分析程序的手工实现方法1【学习指南】词法分析程序是编译程序的一个构成成分,它的主要任务是扫描源程序,按构词规则识别单词,并报告发现的词法错误。词法分析也是语法分析的一部分,把词法分析从语法分析中独立出来是为了使编译程序结构清晰,也是为了便于使用自动构造工具,提高编译效率。本章首先介绍正规式和其对单词的描述,然后讲述有穷自动机理论,最后介绍词法分析程序的功能和设计原则。2【难重点】

2、正规式的定义——如何用作单词的描述工具有穷自动机的定义和分类——如何用作单词的识别系统正规式到有穷自动机的转换算法——词法分析程序的自动构造原理如何设计和实现词法分析程序3知识体系词法分析功能-分割符号串形式的源程序,得到单词串输入-字符串形式的源程序输出-单词串分析方法-超前搜索程序设计方法-步(1)画框图-最小化DFA的状态转换图步(2)由框图编写程序NFADFA子集法化简最小化DFA正规文法正规式转换规则转换规则其中“步(1)”画框图涉及的内容如下:44.1单词的描述工具程序设计语言中的单词是基

3、本语法成分。单词符号的语法可以用有效的工具加以描述,并且基于这类描述工具,实现词法分析程序的自动构造。词法单词符号的文法,用来描述高级语言中的标识符、常数、运算符、分界符、关键字单词的描述工具正规文法正规式识别工具:有穷自动机(FiniteAutomata)5为什么要用正规式而不用上下文无关文法来定义语言的词法?语言的词法规则通常非常简单,不必用强大的文法来描述;对于单词,正规式比上下文无关文法提供了更简洁且易于理解的定义;从正规式可自动地构造出有效的词法分析器,其它文法很难;把语言的语法结构分成词法

4、和非词法两部分为编译其前端的模块划分提供了方便的途径。6(右线性):AaBAa(左线性):ABaAaaVT{}如:程序设计语言(l表示a~z中的任一英文字母,d表示0~9中的任一数字。)<标识符>l<字母数字>

5、l<字母数字>l

6、d

7、l<字母数字>

8、d<字母数字><无符号整数>d

9、d<无符号整数><运算符>+

10、-

11、*

12、/

13、=

14、<<等号>

15、><等号><等号>=<保留字>if

16、while

17、else一、正规文法(3型文法)7在一个正规文法中不允许既用右线性文法又用左线性文法。由正规

18、文法产生的语言称作正规集。正规集是一个有穷或者无穷的集合,可用正规式(RegularExpression,Re)来描述。正规式也称正则表达式,正规表达式是说明单词的模式(pattern)的一种重要表示法(记号),是定义正规集的数学工具。正规式描述的集合称作正规集。说明:8正规文法、正规集与正规式三个概念间关系一个正规语言可以用正规文法定义,也可以用正规式定义,对任意一个正规文法,存在一个定义同一个语言的正规式;同样,对每个正规式,存在一个生成同一语言的正规文法;有些正规语言很容易用文法定义,有些则用正

19、规式定义更容易;两者之间是可以转换的,结构上具有等价性。由正规文法或正规式定义的正规语言的集合构成正规集。9是字母表={,,,,*,(,)}正规式正规式表达的语言(正规集)1.,{},2.a,a{a}3.若e1,e2L(e1),L(e2)则(a)e1e2(或)L(e1)L(e2)(b)e1e2(连接)L(e1)L(e2)(c)e1*(闭包)(L(e1))*(d)(e1)L(e1)4.仅由有限次使用上述三步骤而定义的表达式才是正规式二、正规式的定义(递归定义)10注(1)

20、“*”,“”,“”运算左结合,优先级由高到低。(2)可省略。(3)不产生混乱的情况下,可将圆括号略去。如:((r(s*))r)=rs*rr*(s*r)圆括号不可略去(4)“(”,“)”并非正规式的运算符。例:=a,b(a)正规式:ab正规集:a,b(b)正规式:(ab)(ab)正规集:aa,ab,ba,bb11(c)正规式:a*正规集:,a,aa,aaa,aaaa,…(d)正规式:(ab)*正规集:{,a,b,aa,ab,ba,bb,aaa,...(e)

21、正规式:aab*正规集:a后跟随大于等于0个b的所有符号串(f)正规式:(ab)*(aabb)(ab)*正规集:所有含有两个相继a或b的符号串(g)正规式:(aabaabbb)*正规集:空串和任何长度为偶数的a,b符号串(h)正规式:(ab)*abb正规集:任何以abb结尾的a,b符号串12例:=A,B,…,Z,a,b,…,z,0,1,…,9正规式:letter=A

22、B…

23、Z

24、a

25、b…

26、z正规集:L(A)L(B)…L(Z)L(a

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