编译原理第3章.ppt

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

1、第3章　词法分析本章介绍编译第一个阶段词法分析的设计原理和设计方法，要求明确此阶段的任务。理解通常的单词分类和构词规则。会使用单词的描述和识别机制。要求掌握正规文法、状态图、DFA、NFA、正规式和正规集的基本概念和它们之间的关系。掌握词法分析程序的手工实现方法。教学目标3.1有穷自动机3.2正规式正规文法和正规集3.3正规文法与有穷自动机3.4正规式与DFA3.5DFA的化简3.63.73.8词法分析器的构造教学内容S.PO.P语义分析及生成中间代码程序代码生成程序代码优化程序语法分析程序词法分析程序错误处理符号表管理（1）分析和识别单词及属性，包括识别语言的关键字、标识符、常数、运算符

2、等；（2）跳过各种分隔符，如空格，回车，制表符等；（3）删除注释；（4）进行词法检查，报告所发现的错误；（5）建立符号表。课程导入：词法分析的任务main()/*ADD*/{intx=10,y=20,sum;sum=x+y;}main、(、)、{、int、x、=、10、,、y、=、20、,、sum、;、sum、=、x、+、y、;、}词法分析词法分析程序的设计与实现？词法规则词法分析程序为识别单词而专门设计的有向图，是设计词法分析程序的一种好途径。（1）根据词法规则写出正规文法；（2）将正规文法转换成状态图；（3）将状态图转换成流程图。状态图3.1有穷自动机1.状态图（补充）定义在∑上的有向

3、图，满足以下条件a.至少存在一个初始结点b.存在一些终止结点（也可为空）c.每条边上标有∑上的符号（也可为ε）一张状态图包含有穷个状态，至少有一个初态，至少要有一个终态（用双圈表示）SUVZ111000例3-1：识别的符号串：从某一初始结点到某一终止结点的序列。L（TG）={ab，bab，babbb，abbb，……}∑={a，b}结点代表状态，用圆圈表示。有向弧表示状态转移弧上的标记表示在射出弧的结点状态下可能出现的输入字符2.正规文法（左线性文法）转换状态图（重点）:教材3.3②以每个非终结符号做其它状态③对于形如Q→q的规则,对于形如Q→Rq的规则,④以文法开始符号为终止状态例3-2：

4、文法G[Z]：Z→Za

5、Aa

6、BbA→Ba

7、aB→Ab

8、b①构造S做初始状态SABZaaaabbb状态------文法的非终结符终止状态-----文法开始符号边------转换关系------终结符号QqR例3-3已知文法G[Z]:Z→U1

9、V1U→Z0

10、1V→Z0

11、0（1）画出状态图（5分）（2）是NFA吗？为什么？（3分）2型文法（不确定的下推自动机）1型文法（不确定的界限自动机）0型文法（图灵机）3型文法（有限自动机）有穷自动机是一种数学模型，具有离散的输入与输出，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合引入有穷自动机这个理论，正是为词法分析程序的自动构造

12、寻找特殊的方法和工具有穷自动机分为两类：确定的有穷自动机（DFA）(DeterministicFiniteAutomata)不确定的有穷自动机（NFA）(NondeterministicFiniteAutomata)3.1.1确定的有穷自动机（DFA）M=(Q,Σ,δ,S,Z)Σ：有穷字母表，它的每个元素称为一个输入符号Q：有穷集，它的每个元素称为一个状态S∈K，是唯一的初态ZK是一个终态集，终态也称可接受状态或结束状态δ是转换函数，是Q×Σ→Q上的单值映射：δ（q1，a）=q2例3-1状态转换图①构造DFA如下:=({S,Z,A,B},{a,b},,S,{Z})其中：(S,a)=A,

13、(S,b)=B(A,a)=Z,(A,b)=B(B,a)=A,(B,b)=Z(Z,a)=Z例3-1文法G[Z]：Z→Za

14、Aa

15、BbA→Ba

16、aB→Ab

17、bSABZaaaabbb②状态转移函数可用一矩阵来表示：输入字符状态abSABAZBBAZZZΦ若存在一条初始状态到某一终止状态的路径，且这条路径上所有弧的标记符号连接成符号串α，则称α为DFAM（接受）识别。DFAM所能接受的符号串的全体记为L(M)例3-4DFA的状态图表示：1032aabba,bba符号串abaab？和abab？能被此DFA识别吗？例3-5画出能够识别C语言注释/**/的DFA12453othersothers/***

18、/6othersothersallall12453othersothers/***/状态1：注释开始状态。状态2：进入注释体前的中间状态。状态3：表明目前正在注释体中的状态。状态4：离开注释前的中间状态。状态5：注释结束状态，即接受状态。δ是一个多值函数，是从Q×Σ*到Q的子集的映射：δ：Q×Σ→2Q其中2Q是Q的幂集，即Q中所有子集组成的集合。3.1.2不确定的有穷自动机（NFA）M=(Σ,Q,δ,S,Z)有穷自动机