编译原理词法分析

《编译原理词法分析》由会员分享，可在线阅读，更多相关《编译原理词法分析（164页珍藏版）》请在金锄头文库上搜索。

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

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

3、( (字符串字符串) )词法分词法分 析程序析程序语法分语法分 析程序析程序取单词单词单词7词法分析程序的输出1.单词的种类单词符号一般可分为下列五种：v基本字（关键字）：begin、end、if、while、 varv标识符：常量名、变量名、过程名v常数（量）：25、3.1415、true、“ABC”v运算符：、*、=v界符：逗点、分号、括号8词法分析程序的输出v单词类别：表示单词种类，常用整数编码 ，它是语法分析需要的n几种常用的单词内部形式： 1）一类一种：按单词种类分类。 2）一字一种：保留字、运算符和分界 符采用一符一类，所有标识符为一个编 码，所有常数为 一个编码。9词法分析程序的

4、输出2.单词的输出形式：v（单词种别，单词符号的属性值）n单词的属性值：指单词符号的特征，通过 属性值把同一种类的单词区别开来。关键 字、常数、运算符和分界符的属性值即为 自身值，标识符的的属性值为为存放该标 识符的符号表入口的指针。10例1（一类一种） 单词的种别可以用整数编码表示，假如标识符编码为1，常数为2 ，关键字为3，运算符为4，界符为5。 if i=5 then x:=y 关键字 if (3, if) 标识符 i （1，指向i的符号表入口） 等号 （4, = ） 常数 5 （ 2, 5 ） 关键字 then （ 3, then ） 标识符 x （ 4,指向x的符号表入口） 11例2

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

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

7、线性文法，状态图的构造步骤如下：n步骤1：增加节点S为初态（假定文法的字母表 中不包括符号S）；n步骤2：将每一个非终结符号设置为一个对应的 状态；n步骤3：对于形如Aa的每一个规则，引一条从 状态S到A的弧，弧上标记为a；而对于形如 ABa的每个规则，引一条从状态B到A的弧，标 记为a（其中BVN ，aVT ）。17例子n假设某语言的标识符用一下正规文法来定义 ：nGS: SlA A lA dA这里l，d VT ，l az, d 09,构造该文法的状态图。18状态转换图识别的串n在状态转换图中，从某一初态结点到某一终 态结点序列称为路。对于某一符号串，若 存在一条路产生，则称符号串能被该状

8、态转换图识别，否则符号串不能被该状态 转换图识别。19例子识别标识符的状态转换图123字母其他字母或数字*识别整常数的状态转换图123数字其他数字*20词法分析程序的构造n程序设计语言各类单词的词法都能用相应的正规文 法来描述，由正规文法可以构造出相应的状态图， 进而识别一个单词。 状态转换图非常容易用程序来 实现，最简单的办法是让每一个状态结对应一小段 程序n一个词法分析程序可以通过一下步骤得到：1.根据语言的词法规则写出描述单词的正规文法；2.将正规文法转换成相应的状态图；3.将状态图转换成算法的流程图，进而实现词法分 析程序。21例子：状态转换图的实现构造一个识别某种简单语言所有单词符号

9、的转换图，下表列 出了这个语言的所有单词符号。22123456789101112130空白字母字母或数字非字母与数字数字非数字数字=+*非*,()其它*23n几点重要限制不必使用超前搜索q所有基本字都是保留字;用户不能用它们作 自己的标识符q基本字作为特殊的标识符来处理;不用特殊 的状态图来识别，只要查保留字表。q如果基本字、标识符和常数(或标号)之间 没有确定的运算符或界符作间隔，则必须使 用一个空白符作间隔。 DO99K=1，10 要写成 DO 99 K=1，1024n思想：每个状态结点对应一小段程序。n做法: 1)对不含回路的分叉结，可用一个CASE语句或 一组IF-THEN-ELSE语

10、句实现ijkl字母数字/GetChar( ); if (IsLetter( ) 状态j的对应程 序段; else if (IsDigit( ) 状态k的 对应程序段; else if (ch=/) 状态l的对应程 序段; else 错误处理;25n2)对含回路的状态结，可对应一段由WHILE结构 和IF语句构成的程序.i字母或数字其它jGetChar( ); while (IsLetter( ) or IsDigit( ) GetChar( ); 状态j的对应程序段263)终态结点表示识别出某种单词符号，因 此，对应语句为RETURN (C，VAL)其中，C为单词种别，VAL为单词自身值.27

11、全局变量与过程 1)ch 字符变量、存放最新读入的源程序字符 2)strToken 字符数组，存放构成单词符号的字符 串 3)GetChar 子程序过程，把下一个字符读入到 ch 中 4)GetBC 子程序过程，跳过空白符，直至 ch 中 读入一非空白符 5)Concat 子程序，把ch中的字符连接到 strToken 286)IsLetter和 IsDisgital 布尔函数，判断ch中字符是 否为字母和数字 7)Reserve 整型函数，对于 strToken 中的字符串查 找保留字表，若它是保留字则给出它的编码，否 则回送0 8)Retract 子程序，把搜索指针回调一个字符位置 9)I

12、nsertId 整型函数，将strToken中的标识符插入 符号表，返回符号表指针 10)InsertConst 整型函数过程，将strToken中的常 数插入常数表，返回常数表指针。 29int code, value; strToken := “ ”;/*置strToken为空串*/ GetChar(); GetBC(); if (IsLetter() begin while (IsLetter() or IsDigit() begin Concat(); GetChar(); end Retract(); code := Reserve(); if (code = 0) begin va

13、lue := InsertId(strToken); return ($ID, value); end else return (code, -); end30else if (IsDigit() begin while (IsDigit() begin Concat( ); GetChar( ); end Retract(); value := InsertConst(strToken); retrnr($INT, value); end else if (ch =) return ($ASSIGN, -); else if (ch =+) return ($PLUS, -);31else

14、if (ch =*) begin GetChar(); if (ch =*) return ($POWER, -); Retract(); return ($STAR, -); end else if (ch =;) return ($SEMICOLON, -); else if (ch =() return ($LPAR, -); else if (ch =) return ($RPAR, -); else ProcError( );/* 错误处理*/323.3 正规式与有穷自动机n用正规表达式描述词法规则n构造正规表达式等价的NFAn构造NFA等价的DFAn化简DFAn根据DFA编写程序，

15、实现词法分析器n正规式NFA DFA DFA最小化词法 分析器33单词的描述工具n作用: 描述单词的构成规则,基于这类描述工 具建立词法分析技术,进而实现词法分析程序 的自动构造.n工具有: 正规文法 正规式(Regular Expression)34为什么要引进正则表达式？n对于字母表，我们感兴趣的是它的一些 特殊字集正规集。n正规集是字母表上的符合一定规则的符 号串构成的集合n正则表达式是一种适合描述符号的表示法 ，可由它定义正规集。35正规式(regular expression)n定义（正规式和它所表示的正规集）： 设字母标为v1 和都是上的正规式，它们所表示的 正规集分别为和；v2

16、任何a ，a是上的一个正规式，它 所表示的正规集为a；36正规式(regular expression)v3 假定e1和e2都是上的正规式，它们所 表示的正规集分别为L(e1)和L(e2)，那么， (e1), e1e2, e1e2, e1也都是正规式,它们所 表示的正规集分别为L(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1)。（递归）v4 仅由有限次使用上述三步骤而定义的 表达式才是上的正规式，仅由这些正规式 所表示的字集才是上的正规集。37n其中的“”读为“或”（也有使用“+”代替 “” 的 ）；“ ”读为“连接”；“”读为“闭包”（即，任 意有限次的自重复连接）。在不致混淆时，括 号可省去，但规定