《第3章-词法分析》由会员分享，可在线阅读，更多相关《第3章-词法分析（40页珍藏版）》请在金锄头文库上搜索。
1、编译原理 第三章 词法分析第三章 词法分析知识结构： 功能 词法分析器的要求 单词符号分类 词法分析 单词内部形式器的设计 设计方发 词法分析器的设计 状态图 词法分析器组成 正规表达式 单词描述工具 正规集词法分析器 正规文法 确定有限自动机（DFA）单词识别工具 非确定有限自动机（NFA） DFA的最小化 正规式与FA的等价转换等价转换 正规文法与FA的等价转换 第一节 对词法分析器的要求一、词法分析器的功能输入源程序，输出单词符号（二元式表示）。二元式（单词流）源程序（字符流）词法分析器 输入 输出二、单词符号的分类关键字：是由程序语言定义的具有固定意义的标识符。标识符：用来表示各种名字
2、，如变量等。常数：常数的类型有整型，实型等。运算符：算术运算符，关系运算符，逻辑运算符。界限符：逗号，分号等。三、单词符号内部的表示形式内部的单词符号TOKEN字（二元式），TOKEN字占用机器字的长度，依据信息量的多少而定。1、TOKEN字结构CLASS（单词种别码）VALUE（单词符号得属性）CLASS：用整数表示。VALUE：表示单词符号的属性（符号表指针）。 2、TOKEN的作用 CLASS：用于语法分析器对源程序结构的分析。 VALUE：用于语义分析器对源程序具体操作的分析。3、单词种别码划分原则 CLASS：关键字，运算符，界限符（编译程序定义的符号）使用一字一种编码。VALUE值
3、省略。 VALUE：标识符，常数（用户定义的符号），存放符号表常数表的指针。标识符，常数每一类为一种编码。例：BEGIN A：= B END； 词法分析结果： 符号表名字 属性A B （BEGIN，- ） （A ，K1 ） K1 （：= ，- ）（B ，K3 ） K3（END ，- ）（ ； ，- ）四、词法分析器的结构1、一遍扫描（交互式结构）。2、多遍扫描（独立式结构）。 第二节 词法分析器的设计一、设计步骤1、确定词法分析器的接口关系；2、确定单词分类和TOKEN字的结构；3、对每一类单词构造状态转换图；4、根据状态转换图设计算法。二、功能描述1、组织源程序输入；2、按词法规则拼读单词符
4、号，并转换成二元式；3、删除注解行，空格和无用符号；4、检查词法错误。三、设计方法1、输入(读取原文件) 原文件存储方式：一种方式将原文件一次读入内存，另一种方式利用缓冲区技术将原文件分批读入内存。缓冲区的设置：输入（扫描）缓冲区，存放输入的原文件（双缓冲区）。 起点指针 扫描指针2、预处理功能描述：删除无用符号，出错信息的列表打印。单词符号的识别：语句格式标识符不能被无效字符隔开。标识符与关键字，关键字与关键字之间用空格符隔开。标识符的个数不能超过限定的个数。单词符号的格式标识符，关键字的首字符必须是字母。常数的首字符必须是数字。3、识别算法(P39)标识符的识别；常数的识别；算符的识别；界
5、符的识别。四、状态转换图1、状态转换图的表示形式是一张有向图,结点代表状态（用表示），结点间用箭弧线连接（），箭弧线上的符号，表示射出结点到达射入结点可能识别的输入符号，终态结点代表分析结束。21 初态 a331 b c d 初始状态,表示识别符号串的开始。双圈终态，表示识别符号串的结束。*表示多读入一个字符。 例1：标识符的状态转换图 状态转换矩阵状态字母数字其它0 1 1 1 1 2 2 0121 字母 其它 * 字母，数字 例2：标识符“AB1”的识别21011 A B 1 其它 *例4：无符号数状态转换图1210 数字 其它 * 状态转换矩阵状态数字其它011122 数字 2、识别过程
6、从初态开始，逐步读入字符，转到下一个状态（或出错），直至终态（或不能到达终态出错）。例3：字符串“AB+12”的识别23101 A B + *10识别出单词AB,多读入一个字符 +。由另一张状态转换图识别单词符号 +。 + 继续识别剩余字符12(数字)：2101 1 2 其它 *上述识别过程把AB12字符串分解为三个单词符号“AB”、“ + ” 、“12”。 3、状态转换图的实现状态转换图非常容易用程序实现，每一个状态对应一段程序。不含回路的分叉状态结点的程序设计J 字母IK 数字L 其它符号利用多分支语句CASE或选择语句IF.THEN.ELSE.。含回路状态结点的程序设计JI 其它 数字，
7、字母 利用循环语句WHILE.DO。词法分析程序的组成状态转换图是一种特殊的流程，它可直观清晰地描述单词符号的识别过程，只要把每一个结点加入语义动作，就构成了词法分析程序。4、词法分析程序的组成（八个模块）主控模块；初始化模块；判定源程序文件是否存在模块；从源程序文件中读一个字模快；拼读一个单词模块；查关键字模块；输出单词模块；错误处理模块。第三节 正规式、正规集、正规文法一、正规式的定义S中的符号为正规式的基本符号，单个符号或由符号与运算符组成的表达式称正规式。运算符优先级：重复 用“ * ”表示；连接 用“ ”表示或省略；选择 用“ ”表示。例：a，ab*，ab ，（ab）c都是正规式。二
8、、正规集由正规表达式所表示的字符串的集合称为正规集。如正规式用V表示，正规集L（V）表示。三、正规文法正规文法是上下文无关文法的一种特殊情况，所有产生式的右部至多含有一个非终结符号，左线性文法，右线性文法都属于正规文法。左线性文法：A Ba A a 右线性文法：A aB A a 其中：A，BVN ，aV* T四、正规式与正规集的递归定义1、正规式与正规集的递归定义P46和都是上的正规式，正规集为和。任何a，a是S上的正规式，正规集为a。假定U和V是S上的正规式，正规集为L(U)，L(V)UV是正规式，正规集为L(U)L(V)。UV是正规式，正规集为L(U)L(V)。 (U)*是正规式，正规集为
9、 (L(U)*。例1：令= a, b，则正规式a | b的正规集是 a, b 。正规式（a | b）（a | b）的正规集是aa, ab, ba, bb。正规式a* 的正规集是，a, aa, aaa。正规式（a | b）* 的正规集是,a, b, aa, ab, ba, bb, aaa。（a | b）*（a*b*）*，即所有a和b的符号串集合。（a | b）*(aa| bb)（a | b）* 的正规集是所有含有两个相继a或两个相继b的字符串集合。例2：S =a, b, cz，0, 1,9正规式（a | b|z）（a | b|z|0|1|9）* 代表标识符。 2、正规式与正规集的等价性若两个正规
10、式代表的正规集相同，则认为正规式等价。U=V，表示L（U）=L（V）例3：U=10*0* ， L(U)=10* V=10* ， L(V)=10* 则10*0*=10*例4：b(ab)*= (ba)*b （ab）*a*b*(a|b)*= (a*b*)* (a|b)*(a*|b*)3、正规式的代数定律（1）UV=VU 交换律（2）UVW=（UV）W 结合律（3）U（VW）=（UV）W 结合律（4）U（VW）=UVUW 分配律（5）U = U= U（6）U*=U+e（7）U*=U*（8）U+=U*U=UU*例1：选择规则UV，则描述的正规集L(UV)=L(U)L(V)。 令 U=a,V=b： 则 L(UV)= L(U)L(V)=L(a)L(b) =ab=a，b 例2：连接规则UV，则描述的正规集L(UV)=L(U)L(V)。 令 U=ab，V=c： 则 L(UV)= L(U)L(V)=L(ab )L(c) = a，bc=ac,bc 例3：重复规则U*，则描述的正规集L(U*)=(L(U)
