编译原理第3章.词法分析

《编译原理第3章.词法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章词法分析回忆：词法分析程序的功能：对构成源程序的字符串从左到右进行扫描和分解，并根据语言的词法规则识别出一个个具有独立意义的单词符号。具体：①设计成单独一遍扫描。②设计成子程序，当语法分析器需要新单词时调用它。第三章.词法分析§3.0词法分析程序的功能源程序词法分析单词符号序列语法分析源程序词法分析子程序语法分析取单词8/29/20212§3.1词法分析程序的输入输出一.输入：字符串表示的源程序二.输出：单词符号或单词符号表示的源程序1.语言的单词符号：是指语言中具有独立意义的最小语法单位。共分

2、五类：保留字、标识符、常数、运算符、和界符2.单词符号的内部表示：二元组（单词种别码，单词自身值）继续8/29/20213单词种别码保留字：①一字一种：1－begin2－end3－if4－then②全体为一种：0或者k标识符：全体为一种常数：①数据类型：整型、实型、字符型、布尔型②全体为一种运算符：①一符一种②全体为一种界符：①一符一种②全体为一种返回8/29/20214单词自身值①如果一个种别码对应一个单词符号，则种别码可以代表单词自身。②如果一个种别码对应多个单词符号，则单词自身值是单词符号的机内

3、码。机内码：标识符：自身串（ASCII码）常数：二进制值、逻辑值Ifa>1thenb=100词法分析器（3，）（6，a）（12，）（7，1的二进制）（4，）（6，b）（10，）（7，100的二进制）8/29/20215③用相应符号表项的指针值来区分同类中不同的单词符号。K表：I表：C表：beginendifthen…ab…1100…ifa>1thenb=100词法分析器（k，3）（I，1）（P，18）（C，1）（K，4）（I，2）（P，10）（C，2）返回8/29/20216§3.2词法分析程序的设计

4、一.输入、预处理输入缓冲区预处理子程序扫描缓冲区源程序词法分析的预处理程序：从源程序中处理出一串确定长度的输入字符，并将其装进词法分析程序的扫描缓冲区。处理：①删除注解、空格、回车符、换行符之类非必要信息。②把标识符登录入符号表以及某些预加工处理等。扫描缓冲区的设计：两个指针：起点指针,搜索指针两个半区：左右半区互补使用↑↑起点指针搜索指针8/29/20217二.单词符号的识别以及超前搜索词法分析程序在识别单词时,对有些单词需要向源程序中多看若干个字符才能被识别,称为超前搜索。1.关键字的识别:有些语

5、言中关键字的识别需要超前搜索。例如:FORTRAN语言中:1DO99K=1,102DO99K=1.102.标识符的识别:以运算符、界符、空格等结束。3.常数的识别:需要超前搜索。例如:5.EQ.M和5.E08。4.运算符和界符的识别:需要超前搜索。例如:<=8/29/20218状态转换图:是由一组矢线连接的有限个结点所组成的有向图。其作用是识别相应的字符串。例如:标识符:I→l

6、Il

7、Id初态=>①②③终态例如:<整数>→数字

8、<整数>数字=>①④⑤三.状态转换图l非l非dl/dd非dd8/29/20

9、219利用状态转换图识别(或接受)字符串的过程:从初态出发,按照与符号串余留部分中最左字符相匹配的原则,游历状态图,直至符号串的末端为止。如果这时恰好到达终态,则符号串为该文法的句子；否则不是。例如：识别num1、1001初态=>①②③终态④⑤l非l非dl/dd非dd8/29/202110大多数程序设计语言的单词符号都可以用状态转换图来识别。可以用一张状态转换图或若干张状态转换图来描述一个语言的所有单词。例如：图3.3是简单语言词法分析的状态转换图。8/29/2021112.由正规文法构造状态转换图(

10、1).右线性文法=>状态转换图已知:G=(VN,VT,P,S)P:A→aB

11、aA,B∈VN,a∈VT*求:状态转换图M设:

12、VN

13、=k,则状态转换图M共有k+1个结点方法:①初态=S,增设终态结点F②对G中形如A→aB的产生式,从结点A引一条矢线到结点B,并用a标记。③对G中形如A→a的产生式,从结点A引一条矢线到终态结点F,并用a标记。④对G中形如A→ε的产生式,从结点A引一条矢线到终态结点F,并标记为ε,或令A为接受状态。8/29/202112例如:文法G[Z]:Z→0AA→0A

14、0BB→1A

15、ε

16、语言为:L(G)=0(0

17、01)*0求:状态转换图。ZFBA=>1000εZ0=>BZA00108/29/202113(2).左线性文法=>状态转换图已知:G=(VN,VT,P,S)P:A→Ba

18、aA,B∈VN,a∈VT*求:状态转换图M设:

19、VN

20、=k,则状态转换图M共有k+1个结点方法:①新增初态=R,S=终态结点②对G中形如A→Ba的产生式,从结点B引一条矢线到结点A,并标记为a。③对G中形如A→B的产生式,从结点B引一条矢线到结点A,并标记为ε。