资源描述：
《第2章词法分析Tsu版电子教案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第2章词法分析词法分析任务2.1词法分析器的设计考虑及手工构造2.1.1单词类型及二元式编码㈠单词类型基本字、标识符、常数、运算符、界符㈡单词的性质•个数确定和不确定•单字符或多字符构成㈢单词二元式编码经词法分析后，单词用二元式(code,val)表示。•code表示单词的种别，用整数码表示，在语法分析时使用。•val表示单词的值，在本书中用字符串表示，在语义分析时使用。㈣编码原则通常将标识符归为一种，常数按类型分种，基本字、运算符及界符采用一符-•种。㈤实例设有某一程序设计语言，其部分单词二元式编码如下所示：单词单词种别(字符形式)
2、单词值(字符串形式)integeraNULrealCNULbeginNULend}NUL标识符•1字符串形式符号名无符号整常数X字符串形式数字无符号实常数y字符串形式数字=—NUL**NUL++NUL((NUL))NUL99NUL■■NUL•••••••••用该程序设计语言编制的计算园柱体表面积的源程序(输入输出略)如下所示:Begin/*S=2*3.14*R*R+2*3.14*R*H*/Realr,h,s;s=2*3.14*r*(r+h)End根据单词二元式编码，上述程序的单词二元式序列应为：C｛「NUL“)(C,”NUL“)('i
3、y'r")CJNUL”)(,,'；,NULn)(Y,”s”)C',”NUL”)Ci「s”)C=7*NULH)(乂,”2”)(*,”NUL”)('/,”3.14”)C*7，NULn)(Y,“r”)C*；”NUL”)(f,“NUL”)(T,V)(屮,“NUL”)(Y,“h”)(')T'NUL”)('｝；”NUL”)2.1.2源程序的输入及预处理㈠源程序的输入•分段读入处理(早期)•全部读入后处理设源程序如下所示，其中丫为续行符。Source,txt-记事本文件（E）编辑（町搜索（S）帮助（H）Begin/xS=2x3.14mRxR+2x3
4、.1HmRxHx/▲Realr,h,s；s=2m3.14xrx(r+h)EndL源程序读入后，输入缓冲区的内容如下所示:㈡预处理词法分析器通常由二个部分构成:预处理程序扫描器（单词识别程序）①分成二部分的理rh②预处理主要工作上述源程序经预处理后，扫描缓冲区中的内容如下所示:beg■1nrea1rhs■s=2*3■14*r*(r+h)end ••• O预处理程序例2.1.3基本字的识别和超前搜索程序设计语言单词以基本字识别最为困难，原因如下：①有些语言对基本字不加保护，用户可用作普通标识符。②基本字、用户定义的标识符和常数之间没
5、有分隔符。解决办法：①所有基本字均为保留字（Reservedword）,用户不得使用它们作为标识符。②将空格、TAB和换行符视为界符。在基本字、用户定义的标识符和常数Z间，若没有运算符或界符，则至少用一个空格（或TAB、换行符）加以分隔。2.1.4遍㈠遍的基本概念㈡遍引入的历史背景（三）遍和编译程序的结构2.1.5状态转换图和词法分析器的手工构造㈠引入状态转换图的必要性㈡状态转换图基本概念及应用例1,识别标识符的状态转换图如下所示：了母数字空格字母—①一非字母数字T*例2,识别实常数和整常数的状态转换图如下所示:空格例3,识别和”++
6、啲状态转换图。空格㈢利用状态转换图识别单词状态转换图每次只能识别一个单词，若源程序中有N个单词，则需使用状态转换图N次。设源程序为”x+++y#”（#是预处理程序添加的），单词识别程序（扫描器）共使用状态转换图5次。1）从初态0出发，读入乂进入状态1,在状态1读入屮，进入终态2,识别出标识符”x”,退回屮；2）从初态0出发，读入屮进入状态10,在状态10读入屮，进入终态11,识别出运算符”卄”；3）从初态0出发，读入屮进入状态10,在状态10读入y,进入终态12,识别出运算符”+”，退回y；4）从初态o出发，读入y进入状态1,在状态1
7、读入#,进入终态2,识别出标识符”y”，退回#;5）从初态0出发，读入#进入状态13,识别出单词”#”，识别出单词”#”意味着整个源程序中字符处理完毕。㈣根据状态转换图编制程序2.2正规式、自动机及词法分析器的自动生成2.2.1基本概念㈠有穷字母表工符号有限集，它的每个元素称为字符。㈡字(字符串)工上字符所构成的有限序列。①空字②L③(集合的)积运算④(集合的)闭包⑤(集合的)正则闭包2.2.2正规式与正规集㈠正规式和正规集的定义：•£和①是工上的正规式，相应的正规集为｛£｝、｛｝。•若aeE,则a是正规式，相应正规集为｛a｝。•若(
8、X、卩为正规式，相应正规集分别记为L(a)和L(p),则a
9、卩是正规式，其相应正规集记为L(a
10、p),且令L(a
11、p)=L(a)UL(p)o•若a、(3为正规式，相应正规集分别记为L((x)和L(p),则邓(或a•卩)是
