编译原理-词法分析

1程序设计语言编译原理——第三章词法分析任务：从左至右逐个字符地扫描源程序，产生单词符号把作为字符串的源程序改造为单词符号串的中间程序。李伟生信科大厦19楼Tel：[e-mail]2第3章词法分析内容提要:3.1词法分析的基本概念3.2词法分析器的设计3.3正规表达式与有限自动机3.4词法分析器的自动产生3本章重点单词的描述工具单词的识别系统设计和实现词法分析程序–首先需要描述和刻画程序设计语言中的原子单位——单词，其次需要识别单词和执行某些相关的动作。–描述程序设计语言的词法的机制是正规表达式，识别机制是有穷状态自动机。本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。43.1词法分析器的基本概念词法分析器又称扫描器，是执行词法分析的程序。任务有二：(1)识别单词——从用户的源程序中把单词分离出来;(2)翻译单词——把单词转换成机内表示，便于后续处理。词法分析程序：词法分析是编译过程中的一个阶段，在语法分析前进行，也可以和语法分析结合在一起作为一遍。输入：源程序字符串输出：等价的属性字序列（内部表示形式）词法分析程序的功能：读入源程序字符串，识别开具有独立含义的最小语法单位——单词（符号）；把单词变换成长度统一的且为定长的属性字。其他功能：滤掉空格，跳过注释、换行符；某些预加工处理。5词法分析器词法分析程序和语法分析程序的关系常遇到的术语：Token单词，词标，符号；lexeme词素，词位；pattern模式，式样帮助理解术语：Ingeneral，thereisasetofstringsintheinputforwhichthesametokenisproducedasoutput.Thissetofstringsisdescribedbyarulecalledapatternassociatedwiththetoken.Thepatternissaidtomatcheachstringintheset.Alexemeisasequenceofcharactersinthesourceprogramthatismatchedbythepatternforatoken.例如：constpi=3.14159；中的pi是token“identifier”的lexeme，其pattern为letterfollowedbylettersand/ordigit.源程序词法分析程序语法分析程序Tokengettoken….6词法分析器词法分析程序的实现方式相对独立方式：把词法分析程序作为语法分析程序的一个独立子程序。语法分析程序需要新符号时调用这个子程序。完全独立方式：词法分析程序作为单独一趟来实现。词法分析程序读入整个源程序，它的输出作为语法分析程序的输入。词法分析程序输出单词的形式词法分析程序输出的单词符号通常用二元式表示：（单词种别，单词符号的属性值）单词种别：表示单词种类，常用整数编码，它是语法分析需要的单词符号的属性值：是编译中其他阶段所需要的信息如果一个种别只含一个单词符号，那么该单词符号的种别编码就完全代表它自身的值。如果一个种别含有多个单词符号，那么还应给出该单词符号的属性值：标识符属性值是标识符自身的字符串；常数属性值是常数的二进制数值。7词法分析器语言的单词符号单词符号是程序语言中具有独立意义的基本语法单位，一般分为下面5种。关键字(基本字)：系统内部定义，具有固定的意义，通常用来区分语法单元(个数确定，可全体编为一类，也可一字一类)标识符：用户给一些变量起的名字(个数不确定，作为一类)常数：各种类型的常数。(个数不确定，按类型分类)运算符：单字符界符如+、-、*、/、等，双字符界符如:=====/**/等。(个数确定，一符一类)界符：如，、；、（、）、:等。(个数确定,一符一类)注意：一种语言的单词如何分类、怎样编码，主要取决于技术上的方便。8词法分析器单词的识别问题字母开头——关键字或标识符；数字开头——数值型常量；‘或“开头——字符型常量或字符串常量；其它——多数以自身形态识别之，如+，:=，…如何区分关键字和标识符？现在，大多数编译程序使用“保留字”，即标识符不能用作关键字。系统预先造好关键字表，拼好的字符串，先查“关键字”表，查到了，视为关键字，否则，视为标识符。9词法分析器举例：例如：程序段if(a1)b=10;假定基本字、运算符、界符都是一符一种。它所输出的单词符号是：(2,)基本字if(29,)左括号((10,’a’)标识符a(23,)大于号(11,’1’的二进制)常数1(30,)右括号)(10,’b’)标识符b(17,)赋值号=(11,’10’的二进制)常数10(26,)分号；103.2词法分析器的设计构造词法分析程序的方法词法分析程序的编写1.构造词法分析程序的方法用手工方式，即根据识别语言单词的状态转换图，使用某种高级语言，例如，C语言直接编写词法分析程序。利用自动生成工具LEX自动生成词法分析程序。11词法分析器的设计2.词法分析程序实现中需要考虑的问题：(1)确定实现词法分析程序的执行方式。(2)确定属性字的结构。(3)缓冲区预处理，超前搜索。(4)关键字的处理，符号表的实现。(5)查找效率，算法的优化实现。(6)词法错误处理。12词法分析器的设计属性字词法分析程序对说明部分不做语义处理。词法分析程序输出属性字一般采用下面的形式：（符号类，符号值）属性字是符号的机内表示，有统一固定的长度源程序的输入在内存开辟缓冲区，将程序文本放进该缓冲区预处理：删除无用字符等词法分析程序对缓冲区扫描时，设置两个指示器，一个指向当前正在识别的单词的开始位置，称为起始指针；另一个用于向前搜索，以寻找单词的终点，称为扫描指针。起始指针搜索指针13词法分析器的设计超前搜索词法分析程序在读取单词时，为了判断是否已读入整个单词的全部字符，常采取向前多读取字符并通过读取的字符来判别，即所谓超前搜索技术。关键字的识别与查表算法对于关键字，先把它们当成标识符，然后去查关键字表。若在表中查到，则为关键字，获取相应的类别码；否则，认为是标识符。查找算法：线性查找折半查找Hash函数14词法分析器的设计出错处理对定义外的（如，对首字符不是字母的，不是数字的，不是运算符和分界符的）单词进行出错处理。使用状态图设计词法分析程序多数语言的词法规则可用正规文法和正规表达式来描述。正规文法或正规表达式定义的语言都可以被状态图识别。使用状态图设计词法分析程序的步骤如下：(1)对程序设计语言的单词按类构造相应的状态图。（这里把关键字与标识符作为一类）(2)合并各类单词的状态图，增加一个出错处理终态，构成一个识别该语言所有单词的状态转换图(3)对状态图的每一个终点编一段相应的子程序。15词法分析器的设计3.状态转换图什么是状态转换图？为了识别正规文法的句子而专门设计的有向图。如：C语言中关于标识符定义的规则（词法规则）如下：标识符→字母|标识符字母|标识符数字则识别标识符的状态（转换）图：状态都是非终结符号S：开始状态E：终止状态，用双圈表示I：标识符状态SIE字母其它字母或数字16词法分析器的设计如何为正规文法构造状态转换图？什么是正规文法？（A→Bα或A→α）步骤如下：(1)以S为开始状态作结点；(2)把文法中的每一个非终结符号作为状态结点；(3)对于形如A→α的每个规则，引一条开始状态S到状态A的弧，弧上标记为α；对于形如A→Bα的规则引一条从状态B到A的弧，弧上标记为α，其中B为非终结符号，α为终结符号。(4)以识别符号为终止状态。17词法分析器的设计构造状态转换图举例例如：对于正规文法G[Z]：Z→Za|Aa|BbA→Ba|aB→Ab|bSABZaba(1)SABaZaaab(2)abSABabZbaa(3)18词法分析器的设计如何应用状态转换图识别句子？如果x是相应文法的句子便必须能从开始状态出发，顺着弧的方向行进到终止状态。其步骤如下:(1)从开始状态开始，以它作为当前状态，并从x的最左字符开始重复步骤2，直到到达x的右端为止；(2)扫描x的下一字符，在当前状态射出的各个弧中找出标记有该字符的弧，并沿此弧前进，以达到的状态作为下一当前状态。步骤2存在的两种可能：可能找不到一条弧的标记与当前字符相同；总能找到一个弧，其标记与当前字符相同。19词法分析器的设计应用状态转换图识别句子举例例如：对于正规文法G[Z]：Z→Za|Aa|BbA→Ba|aB→Ab|babSABabZbaa(1)识别字符串ababaaaabSABabZbaaFba,b(2)识别字符串bababbb20词法分析器的设计a状态转换图识别句子的实质是一个规约过程，运用自底向上的识别算法：如：SA与AZ表示：a直接规约为A，Aa直接规约为Z。从开始状态S出发逐步到达终止状态Z的过程，也是从终结符号串出发，规约到非终结符号的过程。a21词法分析器的设计对句子ababaaa的分析步骤当前状态输入的其余部分1Sababaaa2Ababaaa3Babaaa4Abaaa5Baaa6Aaa7Za8ZababaaaABABAZZ语法树22词法分析器的设计状态转换图的实现一个程序语言的所有单词符号的识别可以用若干个状态转换图予以描述。状态转换图可以用程序实现，最简单的方法是让每个状态结点对应于一段程序。为了更好地使用状态转换图构造词法分析程序，为了讨论词法分析程序的自动生成，引入了正规表达式和有限自动机的概念。233.3正规表达式与有限自动机正规式与正规集确定有限自动机(DFA)非确定有限自动机(NFA)1.正规表达式与正规集（正规语言）程序设计语言中的单词是基本语法成分.单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造。首先回顾上一章的一些基本术语和概念.符号一个抽象实体,我们不再形式地定义它(就象几何中的”点”一样).例如字母是符号,数字也是符号。24正规表达式与有限自动机字母表：字母表是元素的非空有穷集合，我们把字母表中的元素称为符号，因此字母表也称为符号集。符号串：由字母表中的符号组成的任何有穷序列称为符号串，例如001110是字母表=｛0，1｝上的符号串.符号串的长度：如果某符号串x中有m个符号，则称其长度为m，表示为｜x｜=m，如001110的长度是6。空符号串：即不包含任何符号的符号串，用ε表示，其长度为0，即｜ε｜=0。25正规表达式与有限自动机符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串.符号串的方幂：符号串自身连接n次得到的符号串an定义为aa…aan个a的连接符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积定义为AB=xy|xA且yB使用*表示上的一切符号串（包括ε）组成的集合。Σ*称为Σ的闭包。上的除ε外的所有符号串组成的集合记为+。Σ+称为Σ的正闭包。26正规表达式与有限自动机正规式对于字母表，我们感兴趣的是它的一些特殊子集，即所谓正规集。我们使用正规式来表示正规集。正规式也称正则表达式,正规表达式（regularexpression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。我们用以描述单词符号。下面是正规式和它所表示的正规集的递归定义。27正规表达式与有限自动机定义（正规式和它所表示的正规集）设字母表为，辅助字母表`={，，，，，，}。1.和都是上的正规式，它们所表示的正规集分别为{}和{}；2.任何a，a是上的一个正规式，它所表示的正规集为{a}；3.假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1也都是正规式,它们所表示的正规集分别为L(e