编译技术课件-词法分析概述及其手工实现.pptxVIP

第三章:词法分析;第三章:词法分析;八月十五日夜湓亭望月 ? 白居易 昔年八月十五夜曲江池畔杏园边今年八月十五夜湓浦沙头水馆前西北望乡何处是东南见月几回圆昨风一吹无人会今夜清光似往年;八月十五日夜湓亭望月 ? 白居易 昔年八月十五夜，曲江池畔杏园边。今年八月十五夜，湓浦沙头水馆前。西北望乡何处是，东南见月几回圆。昨风一吹无人会，今夜清光似往年。 ;八月十五日夜湓亭望月 ? 白居易 昔年八月十五夜，曲江池畔杏园边。今年八月十五夜，湓浦沙头水馆前。西北望乡何处是，东南见月几回圆。昨风一吹无人会，今夜清光似往年。 ;程序;程序;内 容;;实现方案：基本上有两种;;词法分析程序的输出形式-----单词的内部形式;单词名称 标识符 无符号常数(整) 无符号浮点数 布尔常数 字符串常数 保留字 分界符;2、保留字和分界符采用一符一类;内 容;;左线性文法的状态图的画法：;例如：正则文法 Z::= U0 |V1 U ::=Z1 |1 V ::=Z0 | 0 其状态图为：; 识别算法;问题：;;;文法：1. <标识符>::= 字母 | <标识符>字母 | <标识符>数字 2. <无符号整数>::=数字 | <无符号整数>数字 3. <单字符分界符>::= : | + | * | , | ( | ) 4. <双字符分界符>::= <冒号>= 5. <冒号>::= :;;3.4.2 状态图的实现——构造词法分析程序;1.单词及内部表示: 保留字和分界符采用一符一类;2.词法分析程序需要引用的公共（全局）变量和过程;3、词法分析程序算法; ‘*’ : RETURN(‘STARSY’,-) ; ‘,’ : RETURN(‘COMMASY’,-) ; ‘(’ : RETURN(‘LPARSY’,-) ; ‘)’ : RETURN(‘RPARSY’,-) ; ‘:’ : BEGIN GETCHAR; if CHAR=‘=‘ THEN RETURN(‘ASSIGNSY’,-) ; UNGETCH; RETURN(‘COLONSY’,-) ; END END OF CASE; ERROR; GOTO START; 练习：用C语言实现上述算法。;内 容;;正则表达式中的运算符： | -----或（选择） ? ----连接 * 或 { } ---重复 （） ----括号;例：设 ? = { a,b },下面是定义在?上的正则表达式和正则集合;正则表达式的性质： 设e1, e2和e3均是某字母表上的正则表达式, 则有: 单位正则表达式: ? ?e = e? = e 交换律: e1 | e2 = e2 | e1 结合律: e1|(e2|e3) = (e1|e2)|e3 e1(e2e3) = (e1e2)e3 分配律: e1(e2|e3) = e1e2|e1e3 (e1|e2)e3 = e1e3|e2e3 此外: r* = (r|?)* r** =r* (r|s)* = (r*s*)*;例： 3型文法 正则表达式 S::= aS|aB aS|aba*a a*aba*a B::= bC ba*a C::= aC|a a*a;3.5.2 确定的有穷自动机（DFA）— 状态图的形式化;状态转换函数δ可用一矩阵来表示： 输入 字符 状态 a b 0 1 2 1 3 2 2 1 3 3 3 3;DFA也可以用一状态转换图表示：;换言之：若存在一条初始状态到某一终止状态的路径，且这条路径上能有弧的标记符号连接成符号串α，则称α为DFA M（接受）识别。;3.5.3 不确定的有穷自动机(NFA)第三章: