资源描述：
《第3章 词法分析(1)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章词法分析1S.PO.P语义分析及生成中间代码程序代码生成程序代码优化程序语法分析程序词法分析程序错误处理符号表管理词法分析2要求明确此阶段的任务;理解单词分类和构词规则;会使用单词的描述和识别机制;掌握正规文法、状态图、自动机、正规式和正规集的基本概念和它们之间的关系;掌握词法分析程序的实现方法。词法分析3词法分析词法分析程序概述正规文法与正规式有穷自动机正规式与有穷自动机的等价性正规文法与有穷自动机的等价性一个简单的词法分析器示例4（1）分析和识别单词及属性，包括识别语言的关键字、标识符、常数、运算符等；（2）跳过
2、各种分隔符，如空格，回车，制表符等；（3）删除注释；（4）进行词法检查，报告所发现的错误；（5）建立符号表。3.1词法分析程序概述词法分析的任务5main()/*ADD*/{intx=10,y=20,sum;sum=x+y;}main、(、)、{、int、x、=、10、，、y、=、20、，、sum、；、sum、=、x、+、y、；、}词法分析3.1词法分析程序概述6词法分析的基本思路将单词符号的语法用有效的工具描述；基于该描述建立单词的识别机制；设计和实现词法分析程序。3.1词法分析程序概述7词法分析程序的工作方式相对独立方
3、式（单遍）：把词法分析程序作为语法分析程序的一个独立子程序。语法分析程序需要新符号时调用这个子程序。完全独立方式（多遍）：词法分析程序作为单独一趟来实现。词法分析程序读入整个源程序，它的输出作为语法分析程序的输入。3.1词法分析程序概述82.词法分析单独作为一遍S.P.(字符串)词法分析第一遍语法分析第二遍S.P.(符号串)单词串优点:结构清晰、各遍功能单一缺点：效率低1.词法分析程序作为单独的子程序S.P.(字符串)词法分析程序语法分析程序取单词单词3.1词法分析程序概述9源程序字符串词法分析器符号表单词符号串程序字符单
4、词词法分析程序与语法分析程序的接口方式图示源程序字符串词法分析器符号表语法分析器字符单词取下一单词词法分析程序作为独立程序（多遍）词法分析程序作为语法分析 程序的子程序（单遍）3.1词法分析程序概述10单词的种类（1）关键字：if、for、while（2）标识符：（3）常数：（4）运算符：+、-、*（5）分界符：,、;、(、)词法分析程序的输出形式3.1词法分析程序概述11二元式：单词类别单词的属性值单词类别关键字标识符常数运算符分界符编码123453.1词法分析程序概述词法分析程序的输出形式单词类别可以用整数编码表示:一
5、类一种或一字一种12intx=10,y=20,sum;词法分析的结果3.1词法分析程序概述单词类别单词属性值1int2指向x的符号表入口指针4=3105，2指向y的符号表入口指针4=3205，2指向sum的符号表入口指针5；13词法规则状态图词法分析程序词法分析程序的设计与实现3.1词法分析程序概述（1）根据词法规则写出正规文法；（2）将正规文法转换成状态图；（3）将状态图转换成流程图；（4）写出词法分析程序。143.1词法分析程序概述正规文法及其状态图状态图：为识别单词而专门设计的有向图，是设计词法分析程序的一种好途径。
6、结点代表状态，用圆圈表示，为非终结符；有向弧表示状态转移；弧上的标记表示在射出弧的结点状态下可能出现的输入字符，为终结符。一张状态图包含有穷个状态，只能有一个初态，至少要有一个终态（用双圈表示）。SUVZ11100015例：某语言的标识符可使用以下正规文法G[S]来定义：S→lAA→ε
7、lA
8、dAl∈{a,b,…z}，d∈{1,2,…,9}试构造此文法的状态图。SAll
9、d3.1词法分析程序概述16由正规文法构造状态图3.1词法分析程序概述（1）对于右线性文法步骤1增加结点Z为终态；步骤2将每个非终结符号设置为一个对应的状
10、态；步骤3对于A→a，引一条从A到Z的弧，弧上标记为a；而对于A→aB，引一条从A到B的弧，弧上标记为a。S→lAA→ε
11、lA
12、dAl
13、dAZεSlAZll
14、d17由正规文法构造状态图（1）对于左线性文法步骤1增加结点S为初态；步骤2将每个非终结符号设置为一个对应的状态；步骤3对于A→a，引一条从S到A的弧，弧上标记为a；而对于A→Ba，引一条从B到A的弧，弧上标记为a。3.1词法分析程序概述A→l
15、Al
16、Adl
17、dASlS→lAA→ε
18、lA
19、dAl
20、dAZεSl18词法规则状态图词法分析程序词法分析程序的设计与实现（1）
21、根据词法规则写出正规文法；（2）将正规文法转换成状态图；（3）将状态图转换成流程图；（4）写出词法分析程序。3.1词法分析程序概述19标识符无符号整数运算符：+、*、＝、<、<=分界符：，、；【例】假设某种语言的单词符号的子集有：试构造此语言子集的词法分析程序。3.1词法分析程序概述20（1）根据词法规
