CH03--词法分析.

LIWensheng,SCST,BUPT第3章词法分析基础知识：PASCAL、C语言、正规表达式正规文法、有限自动机知识点：词法分析器的作用、地位记号、模式词法分析器的状态转换图WenshengLiBUPT@20082/76词法分析简介3.1词法分析程序与语法分析程序的关系3.2词法分析程序的输入与输出3.3记号的描述和识别3.4词法分析程序的设计与实现3.5软件工具LEX小结WenshengLiBUPT@20083/76简介词法分析任务由词法分析程序完成本章内容安排讨论用手工方式设计并实现词法分析程序的方法和步骤–词法分析程序的作用–词法分析程序的地位–源程序的输入与词法分析程序的输出–单词符号的描述及识别–词法分析程序的设计与实现词法分析程序自动生成工具LEX简介WenshengLiBUPT@20084/76词法分析程序的作用词法分析程序的作用：扫描源程序字符流按照源语言的词法规则识别出各类单词符号产生用于语法分析的记号序列词法检查*创建符号表*把识别出来的标识符插入符号表中与用户接口的一些任务：–跳过源程序中的注释和空白–把错误信息和源程序联系起来WenshengLiBUPT@20085/763.1词法分析程序与语法分析程序的关系词法分析程序与语法分析程序之间的三种关系–词法分析程序作为独立的一遍–词法分析程序作为语法分析程序的子程序–词法分析程序与语法分析程序作为协同程序分离词法分析程序的好处WenshengLiBUPT@20086/76词法分析程序作为独立的一遍输出放入一个中间文件磁盘文件内存文件字符串源程序字符词法分析程序记号记号流源程序WenshengLiBUPT@20087/76词法分析程序作为语法分析程序的子程序避免了中间文件省去了取送符号的工作有利于提高编译程序的效率语法分析程序词法分析程序取下一记号字符串源程序字符记号符号表WenshengLiBUPT@20088/76词法分析程序与语法分析程序作为协同程序协同程序：如果两个或两个以上的程序，它们之间交叉地执行，这些程序称为协同程序。词法分析程序与语法分析程序在同一遍中，以生产者和消费者的关系同步运行。P1P2唤醒P2唤醒P1唤醒P2唤醒P1WenshengLiBUPT@20089/76分离词法分析程序的好处可以简化设计–词法程序很容易识别并去除空格、注释，使语法分析程序致力于语法分析，结构清晰，易于实现。可以改进编译程序的效率–利用专门的读字符和处理记号的技术构造更有效的词法分析程序。可以加强编译程序的可移植性–在词法分析程序中处理特殊的或非标准的符号。WenshengLiBUPT@200810/763.2词法分析程序的输入与输出一、词法分析程序的实现方法二、设置缓冲区的必要性三、配对缓冲区四、词法分析程序的输出WenshengLiBUPT@200811/76一、词法分析程序的实现方法利用词法分析程序自动生成器–从基于正规表达式的规范说明自动生成词法分析程序。–生成器提供用于源程序字符流读入和缓冲的若干子程序利用传统的系统程序设计语言来编写–利用该语言所具有的输入/输出能力来处理读入操作利用汇编语言来编写–直接管理源程序字符流的读入WenshengLiBUPT@200812/76二、设置缓冲区的必要性为了得到某一个单词符号的确切性质，需要超前扫描若干个字符。有合法的FORTRAN语句：DO99K=1,10和DO99K=1.10为了区别这两个语句，必须超前扫描到等号后的第一个分界符处。Pascal语言中：do99、:=、（*C语言中：==、/*、//、++、for_loopWenshengLiBUPT@200813/76三、配对缓冲区把一个缓冲器分为相同的两半，每半各含N个字符，一般N=1KB或4KB。开始指针向前指针……ifx=ythenj:=j+2;eof…WenshengLiBUPT@200814/76测试指针的过程(1)IF(向前指针在左半区的终点){读入字符串，填充右半区;向前指针前移一个位置;}ELSEIF(向前指针在右半区的终点){读入字符串，填充左半区;向前指针移到缓冲区的开始位置;}ELSE向前指针前移一个位置;WenshengLiBUPT@200815/76每半区带有结束标记的缓冲器开始指针向前指针…ifx=ytheofenj:=j+2;eofeofWenshengLiBUPT@200816/76测试指针的过程(2)向前指针前移一个位置；IF(向前指针指向eof){IF(向前指针在左半区的终点){读入字符串，填充右半区;向前指针前移一个位置;};ELSEIF(向前指针在右半区的终点){读入字符串，填充左半区;向前指针指向缓冲区的开始位置;};ELSE终止词法分析;}WenshengLiBUPT@200817/76四、词法分析程序的输出——记号记号、模式和单词–记号：是指某一类单词符号的种别编码，如标识符的记号为id，数的记号为num等。–模式：是指某一类单词符号的构词规则，如标识符的模式是“由字母开头的字母数字串”。–单词：是指某一类单词符号的一个特例，如position是标识符。记号的属性WenshengLiBUPT@200818/76记号的属性词法分析程序在识别出一个记号后，要把与之有关的信息作为它的属性保留下来。记号影响语法分析的决策，属性影响记号的翻译。在词法分析阶段，对记号只能确定一种属性–标识符：单词在符号表中入口的指针–常数：它所表示的值–关键字：（一符一种、或一类一种）–运算符：（一符一种、或一类一种）–分界符：（一符一种、或一类一种）WenshengLiBUPT@200819/76total:=total+rate*4的词法分析结果id，指向标识符total在符号表中的入口的指针assign_op，-id，指向标识符total在符号表中的入口的指针plus_op，-id，指向标识符rate在符号表中的入口的指针mul_op，-num，整数值4WenshengLiBUPT@200820/763.3记号的描述和识别识别单词是按照记号的模式进行的，一种记号的模式匹配一类单词的集合。–为设计词法程序，对模式要给出规范、系统的描述。正规表达式和正规文法是描述模式的重要工具。–二者具有同等表达能力–正规表达式：清晰、简洁–正规文法：便于识别一、词法与正规文法二、记号的文法三、状态转换图与记号的识别WenshengLiBUPT@200821/76一、词法与正规文法把源语言的文法G分解为若干子文法：G0、G1、G2、…、Gn——正规文法——上下文无关文法语法词法词法：描述语言的标识符、常数、运算符和标点符号等记号的文法语法：借助于记号来描述语言的结构的文法文法？WenshengLiBUPT@200822/76二、记号的文法标识符常数–整数–无符号数运算符分界符关键字WenshengLiBUPT@200823/76标识符标识符定义为“由字母打头的、由字母或数字组成的符号串”描述标识符集合的正规表达式：letter(letter|digit)*表示标识符集合的正规定义式：letterA|B|…|Z|a|b|…|zdigit0|1|…|9idletter(letter|digit)*正规表达式？WenshengLiBUPT@200824/76把正规定义式转换为相应的正规文法(letter|digit)*=|(letter|digit)+=|(letter|digit)(letter|digit)*=|letter(letter|digit)*|digit(letter|digit)*=|(A|…|Z|a|…|z)(letter|digit)*|(0|…|9)(letter|digit)*=|A(letter|digit)*|…|Z(letter|digit)*|a(letter|digit)*|…|z(letter|digit)*|0(letter|digit)*|…|9(letter|digit)*WenshengLiBUPT@200825/76标识符的正规文法idArid|…|Zrid|arid|…|zridrid|Arid|Brid|…|Zrid|arid|brid|…|zrid|0rid|1rid|…|9rid一般写作：idletterridrid|letterrid|digitridWenshengLiBUPT@200826/76常数——整数描述整数结构的正规表达式为：(digit)+对此正规表达式进行等价变换：(digit)+=digit(digit)*(digit)*=|digit(digit)*整数的正规文法：digitsdigitremainderremainder|digitremainderWenshengLiBUPT@200827/76常数——无符号数无符号数的正规表达式为：(digit)+(.(digit)+)?(E(+|-)?(digit)+)?正规定义式为digit0|1|…|9digitsdigit+optional_fraction(.digits)?optional_exponent(E(+|-)?digits)?numdigitsoptional_fractionoptional_exponentWenshengLiBUPT@200828/76把正规定义式转换为正规文法(digit)+(.(digit)+)?(E(+|-)?(digit)+)?=(digit)+(.(digit)+|)(E(+|-|)(digit)+|)=digit(digit)*(.digit(digit)*|)(E(+|-|)digit(digit)*|)num1表示无符号数的第一个数字之后的部分num2表示小数点以后的部分num3表示小数点后第一个数字以后的部分num4表示E之后的部分num5表示(digit)*digits表示(digit)+WenshengLiBUPT@200829/76无符号数分析图digit(digit)*(.digit(digit)*|)(E(+|-|)digit(digit)*|)num3num2num1num4numnumdigitnum1num1digitnum1|.num2|Enum4|num2digitnum3num3digitnum3|Enum4|num4+digits|-digits|digitnum5digitsdigitnum5num5digitnum5|WenshengLiBUPT@200830/76无符号数的正规文法numdigitnum1num1digitnum1|.num2|Enum4|num2digitnum3num3digitnum3|Enum4|num4+digits|-digits|digitnum5digitsdigitnum5num5digitnum5|WenshengLiBUPT@200831/76无符号数4.6E-8的分析树numdigitnum1.num2digitnum3Enum4-digitsdigitnum5468WenshengLiBUPT@200832/76运算符关系运算符的正规表达式为：|=|=||=|正规定义式：relop|=|=||=|关系运算符的正规文法：relop|equal|=|greater||equalgreaterequal=WenshengLiBUPT@200833/76三、状态转换图与记号的识别状态转换图利用状态转换图识别记号为线性文法构造相应的状态转换图–状态集合的构成–状态之间边的形成WenshengLiBUPT@200834/76状态转换图状态转换图是一张有限的方向图–图中结点代表状态，用圆圈表示。–状态之间用有向边连接。–边上