编译原理ch3 词法分析。.ppt

《编译原理ch3 词法分析。.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章词法分析1学习内容3.1词法分析的任务3.2词法分析程序的设计与实现3.3正规式与有穷自动机3.4词法分析程序的自动构造工具2学习目标掌握：词法分析程序的构造，正规式和正规文法到有穷自动机的转换，NFA到DFA的转换、DFA的化简理解：正规文法、正规式、DFA的概念、NFA的概念了解：词法分析程序的自动构造工具33.1词法分析的任务词法分析是编译过程中的第一个阶段，它的主要任务是扫描源程序，按构词规则识别单词，并报告发现的词法错误。输入：源程序字符串输出：单词符号（最基本的语法单位）4词法分析程序的功能词法分析程序主要执行以下功能：读入源程序字符串，识别开具有独

2、立含义的最小语法单位——单词（符号）；把单词变换成长度统一的且为定长的属性字；其他功能：滤掉空格，跳过注释、换行符某些预加工处理5词法分析程序的实现方式1.词法分析单独作为一遍优点:结构清晰、各遍功能单一，有利于集中考虑词法分析一些枝节问题。S.P.(字符串)词法分析S.P.(符号串)语法分析第一遍第二遍单词串6词法分析程序的实现方式2.词法分析程序作为单独的子程序更通常情况，常将词法分析程序设计成一个子程序，每当语法分析程序需要一个单词时，则调用该子程序。S.P.(字符串)词法分析程序语法分析程序取单词单词7词法分析程序的输出1.单词的种类单词符号一般可分为下列五种

3、：基本字（关键字）：begin、end、if、while、var标识符：常量名、变量名、过程名常数（量）：25、3.1415、true、“ABC”运算符：＋、－、*、＜=界符：逗点、分号、括号8词法分析程序的输出单词类别：表示单词种类，常用整数编码，它是语法分析需要的几种常用的单词内部形式：1）一类一种：按单词种类分类。2）一字一种：保留字、运算符和分界符采用一符一类，所有标识符为一个编码，所有常数为一个编码。9词法分析程序的输出2.单词的输出形式：（单词种别，单词符号的属性值）单词的属性值：指单词符号的特征，通过属性值把同一种类的单词区别开来。关键字、常数、运算符和

4、分界符的属性值即为自身值，标识符的的属性值为为存放该标识符的符号表入口的指针。10例1（一类一种）单词的种别可以用整数编码表示，假如标识符编码为1，常数为2，关键字为3，运算符为4，界符为5。ifi=5thenx:=y关键字if(3,‘if’)标识符i（1，指向i的符号表入口）等号　＝　　（4,‘=’）常数5（2,‘5’）关键字then（3,‘then’）标识符x（4,指向x的符号表入口）…11例2（一字一种）C程序while(i>=j)i--;输出单词符号：<(,-><>=,-><),

5、-><--,-><;,->若一个种别只有一个单词符号，则种别编码就代表该单词符号。123.2词法分析程序的设计与实现状态图状态转换图是为了识别正规文法所表示的单词而设计的一种有限方向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连接，箭弧上的标记（符号）代表在射出结点状态下可能出现的输入符号或符号类。133.2词法分析程序的设计与实现一张状态转换图只包含有限个状态，即有限个结点，其中有一个初态，并由若干终态（用双圆圈表示）。0123abba图3.114复习——正规文法3型文法(正规文法)：它是2型文法的特例,任一产生式α→

6、β的形式都为A→aB或A→a，其中A，B∈VN，a∈VT。在程序设计语言中，3型文法通常用来描述单词的结构。正规文法又成为右线性文法。左线性文法：产生式为A→Ba或A→a15由正规文法构造状态图1.对于右线性文法，状态图的构造步骤如下：步骤1：增加节点Z为终态（假定文法的字母表中不包括符号Z）；步骤2：将每一个非终结符号设置为一个对应的状态；步骤3：对于形如A→a的每一个规则，引一条从状态A到Z的弧，弧上标记为a；而对于形如A→aB的每个规则，引一条从状态A到B的弧，标记为a（其中B∈VN，a∈VT）。16由正规文法构造状态图2.对于左线性文法，状态图的构造步骤如下：

7、步骤1：增加节点S为初态（假定文法的字母表中不包括符号S）；步骤2：将每一个非终结符号设置为一个对应的状态；步骤3：对于形如A→a的每一个规则，引一条从状态S到A的弧，弧上标记为a；而对于形如A→Ba的每个规则，引一条从状态B到A的弧，标记为a（其中B∈VN，a∈VT）。17例子假设某语言的标识符用一下正规文法来定义：G[S]:S→lAA→︳lA︳dA这里l，d∈VT，l∈｛a…z},d∈｛0…9},构造该文法的状态图。18状态转换图识别的串在状态转换图中，从某一初态结点到某一终态结点序列称为路。对于某一符号串β，若存在一条路产生β，则称符号串β能