北京工业大学编译原理课件第三章 词法分析.ppt

第3章 词法分析 词法分析(Lexical Analysis) 词法的表示 词法分析器的设计与实现 主要内容 词法分析器(Lexical Analyzer, Scanner)的功能 正规表达式 有穷状态自动机FA——状态图 词法分析器的设计与实现 3.1 词法分析（扫描）器的功能 功能：输入源程序，输出(单词)符号(token)。即：把构成源程序的字符串转换成单词符号的序列 单词符号的形式 按照最小的语义单位设计 通常表示为二元组： （单词符号种别，属性值 ） 关键——找出符号的分割符 例如：axx=70.35+12+exp(2.7) 1) 单词符号的表示 常用单词符号种别——分类（P42） 各关键字（保留字、基本字），各种运算符，各种分界符——各用一个种别码标识 其它标识符——用一个种别码标识 常数——用一个种别码标识 属性（值）——单词符号的值 常数的值，标识符的名字等 保留字、运算符、分界符的属性值可以省略 单词符号编码举例 例 3-1: 单词符号序列while(pointer!=N){S=S++;pointer++;} while (WHILE, _ ) ( (SLP, _ ) pointer (IDN,符号表项指针) != (NE, _ ) N (IDN,符号表项指针) ) (SRP, _ ) { (LP, _ ) S (IDN,符号表项指针) = (EQ, _) S (IDN,符号表项指针) ++ (INC, _ ) ; (SEMI, _ ) 2）相关问题 词法分析器可以作为一个独立的子程序，也可以作为一遍独立的扫描来安排。 输入缓冲区 2）相关问题 3.2 符号的描述——正规(表达)式 例：标识符的文法描述 约定：用d表示数字：0,1,2,…,9; 用l表示字母：A,B,…,Z,a,b,…,z G =({d,l}, {S,T}, P, S) 1) 正规式：正规语言的另一种描述方法 例3-2：标识符的另一种表示 l (l|d)* | 表示或 * 表示Kleene闭包 符号的并列表示符号连接关系 正规式 r 表示正规集,相应的正规集记为 L(r) 正规(表达)式(Regular Expression——RE) 设∑是一个字母表， ⑴ Φ是∑上的RE，L(Φ)=Φ； ⑵ ε是∑上的RE，L(ε)={ε}； ⑶ 对于?a∈∑，a是RE，L(a)={a}； ⑷如果r和s是RE，L(r)=R,L(s)=S，则： r与s的“和” (r|s)是RE，L(r|s)=R∪S； r与s的“乘积” (rs)是RE，L(rs)=RS； r的克林闭包(r*)是RE，L(r*)=R*。 ⑸ 只有满足⑴、⑵、⑶、⑷的才是RE。 运算的优先级 运算优先级和结合性: *高于“连接” 和| ， “连接” 高于 | | 具有交换律、结合律 “连接” 具有结合律、和对|的分配律 ( ) 指定优先关系 意义清楚时，括号可以省略 例：L(a(a|b)*(ε|((.|_)(a|b)(a|b)*))) {a}{a,b}*({ε}∪{.,_}{a,b}{a,b}* ) 2) 正规文法与正规式 正规文法与正规式等价 对任何正规文法，存在定义同一语言的正规式 对任何正规式，存在生成同一语言的正规文法 例 3-3 标识符定义的转换 引入 S S→l (l|d)* 引入A消除闭包 S→l A A→(l|d)A|ε 执行连接对|的分配律 S→lA A→lA|dA|ε 例3-4正规式到正规文法的转换 a(a|b)*(ε|((.|_)(a|b)(a|b)*)) = a(a|b)* |a(a|b)*.(a(a|b)*|b(a|b)*) |a(a|b)*_(a(a|b)*|b(a|b)*) =aA|aC A→aA|bA|ε C→aC|bC|.B|_B B→aA|bA 正规式到正规文法的转换 按如下方法构造正规定义式，并逐步将其转换成正则文法 引入开始符号S，从如下正规定义式开始 S→r 对r中的形如r1|r2|…|rn的子串 用产生式组 A→ r1|r2|…|rn 表示 正规式到正规文法的转换 对r中的形如r1*的子串 用产生式组 A→ε|r1A 表示 对r中的形如r1+的子式子， 用产生式组 A→ r1| r1A 表示 执行连接对|的分配律 对连接运算，要作特殊处理：按出现顺序定义 正规式到正规文法的转换用到了正规定义式的概念 例 3-5：一个简单词法的正规定义式 词法规则 单词种别 属性 标识符→字母(字母