第三章词法分析§3.1词法分析程序的功能§3.2单词符号及输出单词的形式§3.6词法分析程序的编写方法§3.3语言单词符号的两种定义方式§3.4正规式与有穷自动机§3.5正规文法与有穷自动机本章小结§3.1词法分析程序的功能§3.2单词符号及输出单词的形式关键字：是由程序语言定义的具有固定意义的标识符，也称保留字或基本字。如Pascal中的begin、end、if、integer等，C中的if、else、do、while，C++中的class、int、switch、break等都是保留字，它们一般不用作一般标识符。标识符：用来表示各种名字，如变量名、常量名、数组名、函数名、子程序名等。常数：程序中出现的各种类型的常量。常量的类型一般有整型、实型、布尔型、字符型等。如125、0.718、TRUE、“Hello”等。运算符：表达式中连接运算对象的符号。如+、-、*、/、<等。界符：程序中的定界符。如逗号、分号、括号、/*、*/等。§3.2.2词法分析程序输出单词的形式种别通常定义为枚举类型的逻辑项。例如：typedefenum{IF,ELSE,PLUS,NUM,ID,……}TokenType;单词自身的值（单词符号的属性值，它是编译其它阶段需要的信息）属性值是指单词符号的特性或特征，可以是标识符在符号表的入口地址、数值的二进制值等。扫描器必须计算每一个记号的若干属性，所以将所有的属性收集到一个单独构造的数据类型中是很有用的，这种数据类型称作记号记录(tokenrecord)。例如：typedefstruct{TokenTypetokenval;char*stringval;intnumval;}TokenRecord;或作为一个联合typedefstruct{TokenTypetokenval;unon{char*stringval;intnumval;}attribute;}TokenRecord;【例】试给出程序段if(a>1)b=100;输出的单词符号串。经词法分析器处理后，它将被转换为如下的单词符号序列：(while,-)((,-)(id,指向i的符号表表项的指针)(>=,-)(id,指向j的符号表表项的指针)(),-)(id,指向i的符号表表项的指针)(--,-)(；,-)词法分析器作为一个独立子程序词法分析器的设计单词符号的识别：超前搜索§3.6词法分析程序的编写方法一个状态转换图可用于识别（或接受）一定的字符串。大多数程序语言的单词符号都可以用转换图予以识别。作为一个综合例子，我们来构造一个识别某个简单语言的所有单词符号的转换图。下表列出了这个小语言的所有单词以及它们的种别和内部值。单词符号0本例规则，对所有关键字用户不得使用它们作为自己定义的标识符，关键字作为一类特殊的标识符来处理，不再专设对应的转换图。但需要把关键字预先安排在一个表格专，此表叫关键字表。当识别出一个标识符时，就去查关键字表，以确定它是否为一关键字。其次，规定若关键字、标识符和常数之间没有确定的运算符或界限府作间隔，则必须至少用一个空白符作间隔，即此时的空白符是有意义的。状态转换图的实现(5)程序§3.3语言单词符号的两种定义方式§3.3.1正规式与正规集正规式表示字符串的格式，正规式r完全由它所匹配的串集来定义。这个集合为由正规式生成的语言(languagegeneratedbytheregularexpression)，写作L(r)每个正规式可以看作是一个匹配模式。【例3.1】令∑={a,b}，下面给出∑上的正规式和相应的正规集：【例3.2】设∑={a,b,c},则aa*bb*cc*是∑上的一个正规式若两个正规式所表示的正规集相同，则认为二者等价。两个等价的正规式R1和R2记为R1=R2。正规式具有如下性质：*****正规式的扩展*****不在给定集合中的任意字符用“非”运算或解集合的互补运算。用波浪符“~”。【例如】正规式~a表示字母表中非a字符可选的子表达式r？表示由r匹配的串是可选的（0个或1个）。例如：natural=[0-9]+nsignedNatural=(+|-)?Natural§3.3.2正规文法与正规式1、正规文法到正规式的转换【例3.4】设有正规文法Ｇ：【例3.5】设有正规文法Ｇ：【例3.6】设有正规文法Ｇ：【例3.7】已知描述“标识符”单词符号的正规文法文法G1:SScBcBBbAbAAaa建立方程组：S=Sc+Bc………(1)B=Bb+Ab………(2)A=Aa+a………(3)由（3）得：A=aa*………(4)依次代入(3)(2)(1)得：S=aa*bb*cc*即语言{aibjck|i,j,k