编译原理精品教学课件（华南理工大学）第三章词法分析.pptxVIP

;;3.1 词法分析程序的设计 3.3 单词的形式化描述工具 3.4 有穷自动机 3.5 正则式和有穷自动机的等价性 3.6 由DFA构造词法分析程序;3.1 词法分析程序的设计;回顾: 词法分析的主要任务是：从左到右逐个字符地扫描源程序，产生一个个单词(Token)，同时检查源程序中的词法错误。执行词法分析的程序称为词法分析程序或扫描程序(Scanner)。 单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。 ;1 确定词法分析器的接口;;2 确定单词分类和Token结构;单词的机内表示 二元式（单词种别，单词自身的值） 种别是语法分析需要的信息 自身值是编译其他阶段需要的信息 种别编码(常用整数编码) 方法一：按单词的5大种类每种一个码，例如标识符为l，常数为2，基本字为3，运算符为4，界符为5。 方法二：每个基本字一个编码；所有标识符为一个编码；常数按类型分类，每类一个编码；每个运算符一个编码；每个界符一个编码。;;例如 源程序if i=5 then x:=y; 种别编码：标识符为l，常数为2，基本字为3，运算符为4，界符为5 词法分析后输出的单词序列是: (3,‘if’) (1,指向i的符号表入口) (4,‘=’) (2,‘5’) (3,‘then’) (1,指向x的符号表入口) (4,‘:=’) (1,指向y的符号表入口) (5,‘;’);3.3 单词的形式化描述工具;3.3.1 正规文法;;3.3.2 正规式(正则表达式)Regular Expression;假定ｅ1和ｅ2都是∑上的正规式，他们所表示的正规集分别为Ｌ(ｅ1)和Ｌ(ｅ2)，那么，以下也都是正规式和它们所表示的正规集：;;正规式 正规集 a|bc* L(a|bc*)={a} ∪({b}{? ,c,cc,…}) ={a} ∪{b,bc,bcc…}={a,b,bc,bcc…} 正规式的等价性 若两个正规式e1和e2所表示的正规集相同，则说e1和e2等价;程序中的单词都能用正则式来定义 令l为a~z的字母，d为0~9的数字 e1= l ( l | d)* e1表示标识符集合 e2= dd* e2表示无符号整数 注： 标识符→l｜l字母数字 字母数字→l｜d｜l字母数字｜d字母数字 正规式比正规文法更简洁，容易理解单词的构成规律，且可以从正规式自动地构造识别程序，所以通常用正规式作为单词的描述工具;提问;正规表??式的应用;正规表达式的应用;3.3.3 正规文法和正规式间的转换;将∑上的一个正则式r转换成文法G=(VN,VT,S,P) VT= ∑,首先形成产生式S-r,S为G的开始符 不断利用下面的规则做变换,直到每个产生式最多含有一个终结符为止;例:将R=a(a|d)*转换成相应的正规文法 令转换成文法G=(VN,VT,S,P) 其中VT={a,d}， 文法开始符为S 首先形成S-a(a|d)*,然后变换 S-aA A-(a|d)*;将正规文法转换成正规式 将每条产生式改写为正规式 用代入法解正规式方程组 最后只剩下一个开始符号定义的正则式,其中不含非终结符 正则文法到正则式的转换规则:;例：将文法G[S]转换成正规式 G：S→a A|a A→dA|d 先由产生式得: S=aA|a A=d*d 将A代入S中得: S=ad*d|a 利用正则式变换得 S=a(d*d|ε)=ad* 说明:d*d|ε =(ε|d|dd|…)d|ε =d|dd|…|ε= d* 所求正规式为ad*;3.4 有穷自动机(也称有限自动机)Finite Automata;金银岛游戏;金银岛游戏;有穷自动机和正规表达式的关系 例： 描述标识符的正规表达式是： 令letter=a|b|…|z，digit=0|1|…|9 标识符为：letter(letter|digit)* 识别这样的标识符的过程可以用有穷自动机描述如下：;状态：是识别过程中的一些位置，表示有多少模式已经被识别 转换：记录从一个状态到另一个状态的转换 开始状态：识别过程的开始位置 终止状态：表示识别过程的结束 一个字符串被识别的过程可以用识别过程中用到的状态和转换序列来表示 例如：字符串“xtemp=5”中标识符“xtemp”的识别过程为：;定义: 一个DFA M是一个五元组:M=（K，Σ，f，S，Z） K是一个有穷集，它的每个元素称为一个状态 Σ是一个有穷字母表，它的每个元素称为一个输入字符 f是转换函数，是在K X ∑-K上的映射，f(ki,a)=kj意味着当前状态为ki、输入字符为a时，将转换到下一状态kj S∈K，是唯一的初态 Z ? K,是一个终态集，终态也称