《编译原理》第3章 词法分析与有穷自动机.ppt

* “(”和“)”打上引号是为了和正规表达式中的元符号相区别 %% /*辅助过程*/ Upper(char *s,int l) { int i; for(i=0;i l;i++) 　　　s[i]=toupper(s[i]); 　　return 1;} void main(void) { yylex(); } 格式 含义 示例 x 匹配单个字符x ? . 匹配换行符之外的任意字符 ? \ 转义字符，定义同ANSI C 如\n，\t，\r [ ] 字符集合, 匹配括号内的任意字符 [abc]匹配a, b,和c中的任何一个 - 指定范围 [a-z]匹配a和z之间的任何一个 ^ 否定 [^ab]匹配除了a和b之外的任意字符 在LEX源文件识别规则的最后应加一条规则：. {…}; 3.5.2 LEX的正规式 R* 匹配0个或多个R(R是正规式) (ab) *匹配{ε,ab,abab,ababab,…}中任何一个 R＋ 匹配1个或多个R (ab)＋匹配{ab,abab,ababab,…}中的任何一个 R? 匹配0个或1个R (ab)?匹配ε或ab R{m,n} 匹配m到n之间次的R(m,n是整数) a{2,4}匹配{aa,aaa,aaaa}中的任何一个 R{m,} 匹配m次以上的R a{2,}匹配{aa,aaa,aaaa…}中的任何一个 R{m} 匹配m次R a{2}匹配aa (R) 匹配R，且R中运算符优先 (ab)匹配ab R|S 匹配R或S ab|ba匹配ab或ba RS 匹配R和S的连接 abba匹配abba R/S 匹配R，但R之后一定是S，称S为R的尾部条件 ab/ba匹配ab，但ab之后一定是ba ^R 匹配R，但R一定出现在行首 ? R$ 匹配R，但R一定出现在行尾，等价于R/\n ? {name} 匹配名字为name的正规式 ? 运算符 说明 优先级 ( ) 分组括号 1（最高） [ ] 字符类括号 2 * + ? 闭包运算符 3 cc 连接运算符 4 | 或运算符 5 ^ ? 指定行首和行末 6 LEX正规式运算符优先级 正规式 含义 [a-zA-Z0-9_] 表示所有字母、数字及下划线组成的字符集合 [^ \t\n] 表示除空格、tab和换行外的所有字符组成的集合 (\”[^”\n]*) 表示以双引号开头，后跟除双引号和换行外的若干字符组成的字符串，如 “I am a student [A-Za-z][A-Za-z0-9]* 表示以字母开头，后跟若干字母和数字的字符串 ([Ee][-+][0-9]+) 表示科学计数法的指数部分 LEX正规式实例 3.5.3 LEX的实现 LEX的功能是根据LEX源程序构造一个词法分析程序， 该词法分析器实质上是一个有穷自动机。 LEX生成的词法分析程序有两部分组成: 词法分析程序 由正规式构造DFA 识别单词的控制程序 LEX的处理过程： · 扫描每条识别规则Pi构造一相应的非确定有穷自动机Mi ¨将各条规则的有穷自动机Mi合并成一个新的NFA M 即生成该DFA的状态转换矩阵和识别单词的控制程序 0 P1 ε ε ε M1 P2 M2 P3 M3 ·¨确定化并最小化 ，NFA?DFA LEX处理二义性规则的原则： 1.最长匹配原则 在识别单词过程中，有一字符串 x x x x x 根据最长匹配原则，应识别为这是 一个符合Pk规则单词，而不是Pj和Pi规则的单词。 Pj Pi Pk 2.优先匹配原则 如有一字符串，有两条规则可以同时匹配时，那么用规则 序列中位于前面的规则相匹配，所以排列在前面的规则优先权 最高 如,main 如,mains 在写LEX源程序时应注意规则的排列顺序。另要注意，优先匹配原则是在符合最长匹配的前提下执行的。 例： LEX源程序， a { } abb { } a bb { } 一.读LEX源程序，分别生成NFA，用状态图表示为： 二.合并成一个NFA： 0 3 1 7 4 5 2 6 8 start b b b b a a ε ε ε a 1 2 3 4 5 6 7 8 start start start a a a b b b b 三.确定化 给出状态转换的矩阵 状态