《打印词法分析和语法分析》由会员分享，可在线阅读，更多相关《打印词法分析和语法分析（224页珍藏版）》请在金锄头文库上搜索。
1、2018/8/22,北京化工大学信息科学与技术学院计算机系,1,Chapter 3 Scanning(lexical analysis) 词法分析,3.1 词法分析器的作用 3.2 记号的描述 3.3 记号的识别 3.4 从正规表达式到DFA 3.5 TINY扫描程序的实现 3.6 LEX,2018/8/22,北京化工大学信息科学与技术学院计算机系,2,3.1 词法分析器的作用,词 法 分 析,源 程 序,目 标 程 序,语 法 分 析,语 义 分 析,中 间 代 码 优 化,中 间 代 码 生 成, The phase of a compiler 编译程序的结构,目 标 代 码 生 成,20
2、18/8/22,北京化工大学信息科学与技术学院计算机系,3,3.1 词法分析器的作用,读入输入字符，产生记号序列，供语法分析使用3.1.1 词法分析中的问题 3.1.2 记号 3.1.3 记号的属性,2018/8/22,北京化工大学信息科学与技术学院计算机系,4,3.1 词法分析器的作用,3.1.1 词法分析中的问题,把编译过程的分析阶段划分为词法分析和语法分析的原因如下： 1. 简化编译器的设计可能是最重要的考虑。 2. 提高编译器的效率。 3. 增强编译器的可移植性。,2018/8/22,北京化工大学信息科学与技术学院计算机系,5,3.1 词法分析器的作用,3.1.2 记号: 扫描程序生成
3、的逻辑单元,以字母开头：保留字：IF,THEN,ELSE,END,REPEAT,UNTIL,READ,WRITE标识符：字母/数字串 以数字开头：整常数：数字开头的数字串实常数：整数.整数 符号词：+，-，*，/，(，)，:，:=，;，. 控制词：enter,Reserved Words 保留字,2018/8/22,北京化工大学信息科学与技术学院计算机系,6,typedef enum /* book-keeping tokens */ENDFILE,ERROR,/* reserved words */IF,THEN,ELSE,END,REPEAT,UNTIL,READ,WRITE,/* mul
4、ticharacter tokens */ID,NUM,/* special symbols */ASSIGN,EQ,LT,PLUS,MINUS,TIMES,OVER,LPAREN,RPAREN,SEMI TokenType;, Tokens(记号)的枚举表示,每一个记号的表示：Typedef struct TokenType tokenval;char *stringval;int numval; TokenRecord,2018/8/22,北京化工大学信息科学与技术学院计算机系,7,3.1.3 记号的属性任何与记号相关的值 E = M * C,3.1 词法分析器的作用,2018/8/22,
5、北京化工大学信息科学与技术学院计算机系,8,3.2 记号的描述,be set of the ASCII characters or some subset of it,3.2.1 串和语言 3.2.2 语言上的运算,2018/8/22,北京化工大学信息科学与技术学院计算机系,9, The single character from the alphabet, expression a matches the character a. L(a) = a empty string(): the string contains no characters. L() = or : matches no
6、 string at all ,whose language is the empty set.L() = ,3.2.3 Definition of Regular Expression,1. Basic Regular Expression 基本正则表达式,2018/8/22,北京化工大学信息科学与技术学院计算机系,10, | Choice among alternatives 或(选择),2. Regular Expression Operation 正则表达式的运算,L(r|s) = L(r ) L(s ) L(a|b|c|d) = a,b,c,d,例：若S= a|bb， (a|bb)*
7、 =？L(a|bb)*)=？,(a|bb)* =,a,bb,aa,abb,bba,bbbb,aaa,aabb, L(a|bb)*)=L(a|bb)*=a|bb*=,a,bb,aa,abb,bba,bbbb,aaa,aabb,abba,abbbb,bbaa,2018/8/22,北京化工大学信息科学与技术学院计算机系,11, Names for regular expression 正则表达式的名字, Precedence of Operation and use of parentheses运算符的优先级和括号的使用,Precedence of Operation运算符的优先级,Preceden
8、ce: * the first the second| the third,(0|1|2|3|9)(0|1|2|3|9)*,例：a|bc* a|(b(c*)ab|c*d (ab)|(c*)d),(先*，其次 ，最后 |),digit = 0|1|2|3|4|9 digit digit*,2018/8/22,北京化工大学信息科学与技术学院计算机系,12,3. Example,1)= a,b,c the set of all strings over this alphabet that contain exactly one b. (上只包括一个b的所有串的集合),(a|c)*b(a|c)*,2
9、) = a,b,c the set of all strings that contain at most one b. (上最多包括一个b的所有串的集合),(a|c)*|(a|c)*b(a|c)* (a|c)*(b|)(a|c)*,3) = a,b the set of strings S consists of a single b surrounded by the same number of as.(上由一个b及在其前后有相同数目的a组成的串S的集合),S = b,aba,aabaa,aaabaaa,“regular expression cant count ”,2018/8/22
10、,北京化工大学信息科学与技术学院计算机系,13,3. Example,4) = a,b,cthe strings contain no two consecutive bs (上任意两个b都不相连的所有串的集合),( not b | b not b )* ( b |) not b = a|c (a | c | ba | bc)* (b |) (b |) (a | c | ab| cb )*,5) = a,b,c, Regular Expression :(b|c)* a(b|c)*a)* (b|c)*, determine a concise English description of th
11、e language (正则表达式描述语言),the strings contain an even number of as 偶数个a的串的语言,(b|c)* a(b|c)*a)* (b|c)* ( not a* a not a* a)* not a*,2018/8/22,北京化工大学信息科学与技术学院计算机系,14,3.2.4 Extensions to Regular Expressions,r? the strings matched by r are optional,1. one or more repetitions 一个或多个重复(正闭包),r+,2. any characte
12、r 任意字符,period “”,3. a range of characters 字符范围,0-9, a-zA-Z,4. any character not in a given set 不在给定集合中的任意字符,(a|b|c) a character that is not either a or b or c abc in Lex,5. optional subexpressions 可选的表达式,2018/8/22,北京化工大学信息科学与技术学院计算机系,15,Regular Expressions for Programming Language Tokens,1. Numbers
13、数,nat = 0-9+ signedNat = (+|-)?nat number = signedNat(“”nat)? (E signedNat)?,2. Reserved Words and Identifiers 保留字和标识符,reserved = if | while | do | letter = a-z A-Z digit = 0-9 identifier = letter(letter|digit)*,3. Comments 注释,/* this is a C comment */ this is a pascal comment ,4.Ambiguity, White Sp
14、ace, and Lookahead 二义性、空格、回溯,2018/8/22,北京化工大学信息科学与技术学院计算机系,16,3.2.5 正则文法,2018/8/22,北京化工大学信息科学与技术学院计算机系,17,3.3 记号的识别,状态转换图 有穷自动机,2018/8/22,北京化工大学信息科学与技术学院计算机系,18,3.3.1 状态转换图,状态转换图的表示方法,结点代表状态(state)，用圆圈表示。 状态之间用箭弧(transition)连结，箭弧上的标记(字符)代表在射出结点(即箭弧始结点)状态下可能出现的输入字符或字符类。 一个有穷自动机只包含有限个状态(即有限个结点)，其中一个为初
15、态(start state)，至少一个为终态(接受状态accepting state) (双圈表示)。,2018/8/22,北京化工大学信息科学与技术学院计算机系,19,3.3.2 Finite Automata有穷自动机,Finite automata( finite-state machines) are a mathematical way of describing particular kinds of algorithms.,Definite of Deterministic finite automation(DFA) 确定有穷自动机Nondeterministic finite automation(NFA) 非确定有穷自动机,2018/8/22,北京化工大学信息科学与技术学院计算机系,20,3.3.2.1 Definite of Deterministic finite automation(DFA) 确定有穷自动机,由M接受的语言L(M) L(M) | ci , s1= T(s0,c1), s2= T(s1,c2), , sn = T(sn-1,cn) , sn A. ,
