编译原理课件第3章.ppt-淘文阁

资源描述

《编译原理课件第3章.ppt》由会员分享，可在线阅读，更多相关《编译原理课件第3章.ppt（85页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第3章词法分析3.1词法分析器的功能3.2单词的描述3.3单词的识别3.4词法分析程序的自动生成3.5本章小结5/23/2023 13.1词法分析器的功能功能：输入源程序，输出单词符号(token)。即：把构成源程序的字符串转换成“等价的”单词(记号)序列根据词法规则识别及组合单词，进行词法检查对数字常数完成数字字符串到二进制数值的转换删去空格字符和注释5/23/2023 2 3.1.1 单词的分类与表示&3.1.2 词法分析器的输出一、单词的种类1.关键字:也称基本字，begin、end、for、do.2.标识符:由用户定义，表示各种名字3.常数:整常数、实常数、布尔常数、字符串常数等4

2、.运算符:算术运算符+、-、*、/等；逻辑运算符not、or与and等；关系运算符=、和等5.分界符:，、；、（、）.5/23/2023 3二、单词的内部形式几种常用的单词内部形式：1、按单词种类分类2、保留字和分界符采用一符一类3、标识符和常数的单词值又为指示字（指针值）种别属性值表示单词的种类，可用整数编码或记忆符表示不同的单词不同的值5/23/2023 4单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数保留字分界符类别编码1234567单词值内部字符串整数值数值0 或 1内部字符串保留字或内部编码分界符或内部编码1、按单词种类分类5/23/2023 52、保留字和分界符采用

3、一符一类单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数BEGINENDFORDO:+*,(类别编码12345678920212223单词值内部字符串整数值数值0 或 1内部字符串-5/23/2023 6例3.1 语句if count7 then result:=3.14的单词符号序列(IF，0)(ID，指向count 的符号表入口)(GT，0)(INT，7)(THEN，0)(ID，指向result的符号表入口)(ASSIGN，0)(REAL，3.14)(SEMIC，0)跟实现有关5/23/2023 73.1.3源程序的输入缓冲与预处理超前搜索和回退双字符运算符（*,/*,:=,

4、）DO 90 k=1,10DO 90 k=1.10 缓冲区假定源程序存储在磁盘上，这样每读一个字符就需要访问一次磁盘，效率显然是很低的。空白字符的剔除剔除源程序中的无用符号、空格、换行、注释等5/23/2023 83.1.4词法分析阶段的错误处理 1非法字符检查2关键字拼写错误检查3不封闭错误检查4重复说明检查5错误恢复与续编译紧急方式恢复(panic-mode recovery)反复删掉剩余输入最前面的字符，直到词法分析器能发现一个正确的单词为止。5/23/2023 93.1.5词法分析器的位置目标程序词法分析器语法分析器语义分析与代码生成目标代码整理图3.4以语法分析器为中心源程序符

5、号表以语法分析器为中心的优点：比较简单以词法分析作为独立的一个阶段：简化编译器的设计。提高编译器的效率。增强编译器的可移植性。5/23/2023 103.2单词的描述3.2.1正则文法正则文法G=(V，T，P，S)中，对P，均具有形式Aw或AwB(Aw或ABw)，其中A，BV，wT+。例3.2 标识符的文法 A|B|X|a|b|z A|B|Z a|b|z 0|1|2|95/23/2023 1 1 例3.2 标识符的文法或者定义为约定：用digit表示数字：0,1,2,9;用letter表示字母：A,B,Z,a,b,z|A|B|Z|a|b|z 0|1|2|9 例3.3 无符号数的文法5

6、/23/2023 123.2.2正则表达式例3.2：标识符的另一种表示letter(letter|digit)*|表示或*表示Kleene闭包+表示正闭包？表示“0或1个”Letter和(letter|digit)*的并列表示两者的连接正则式r表示正则集,相应的正则集记为 L(r)5/23/2023 133.2.2正则表达式(续)RE定义3.1 设是一个字母表，则上的正则表达式及其所表示的正则语言可递归地定义如下：是上的一个正则表达式，它表示空集；是上的一个正则表达式，它表示语言；对于a(a)，a是上的一个正则表达式，它表示的正则语言是a；假设r和s都是上的正则表达式，它们表示的语言分别为

7、L(r)和L(s)，则：(r)也是上的正则表达式，它表示的语言为L(r)；(r|s)也是上的正则表达式，它表示的语言为L(r)L(s)；(rs)也是上的正则表达式，它表示的语言为L(r)L(s)；(r*)也是上的正则表达式，它表示的语言为(L(r)*；只有经有限次使用上述规则构造的表达式才是上的正则表达式。5/23/2023 14正则表达式中的运算优先级运算优先级和结合性:*高于“连接”和|，“连接”高于|具有交换律、结合律“连接”具有结合律、和对|的分配律()指定优先关系意义清楚时，括号可以省略5/23/2023 15例子令=a，b，上的正规式和相应的正规集的例子有：正规式正规集a aab

8、 a,bab ab(ab)(ab)aa,ab,ba,bba,a,a,任意个a的串(ab),a,b,aa,ab 所有由a和b组成的串(ab)(aabb)(ab)上所有含有两个相继的a或两个相继的b组成的串5/23/2023 16 设r,s,t为正规式，正规式服从的代数规律有：1.rs=sr“或”服从交换律2.r(st)=(rs)t“或”的可结合律3.(rs)t=r(st)“连接”的可结合律4.r(st)=rsrt(st)r=srtr“连接对”满足分配律 5.r=r,r=r 是“连接”的单位元6.r*=(r|)*和之间的关系7.r*=r*是幂等的5/23/2023 17正规式举例程序设计语言中的

9、单词基本上都能用正则表达式来定义。用letter和digit分别表示字母和数字，标识符的正规集为Letter(letter|digit)*表示无符号数集的正则表达式为：digit digit*(.digit digit*|)(E(+-)digit digit)5/23/2023 18正则表达式的缩写形式正闭包：如果r表示语言L(r)的正则表达式，r+表示r的正闭包，它是语言(L(r)+的正则表达式a+表示由一个或多个a构成的所有串的集合 0或1个：?是一元操作符，表示“0或1个”r?=r|如果r是正则表达式，则(r)?是表示语言L(r)的正则表达式例：digit+(.digit+)?(E(+

10、-)?digit+)?字符类：abc表示正则表达式a|b|c.例：标识符A-Za_zA-Za_z0_9*5/23/2023 193.2.3正则表达式与正则文法的等价性正则表达式与正则文法等价对任意一个正则表达式，存在一个定义同一语言的正则文法对任意一个正则文法，存在一个定义同一语言的正则表达式5/23/2023 20根据正则文法构造等价的正则表达式问题：给定正则文法G，构造一个正则表达式r，使得L(r)=L(G)基本思路为正则文法的每个产生式构造一个正则表达式方程式，这些方程式中的变量是文法G中的语法变量，各变量的系数是正则表达式，简称为方程式。从而得到一个联立方程组。用代入消元法消去联立方

11、程组中除开始符号外的其他变量，最后得到关于开始符号S的解：S=r，r即为所求的正则表达式。5/23/2023 21根据正则文法构造等价的正则表达式具体步骤(1)根据正则文法G构造正则表达式联立方程组。假设正则文法G是右线性的，其每个产生式的右部只含有一个终结符，则有如下方程式构造规则：对形如A a1|a2|am的产生式，构造方程式A=a1|a2|am。其中可以有形如A的产生式；对形如Aa1A|a2A|amA的产生式，构造方程式A=(a1|a2|am)*A；对形如Aa1B|a2B|amB的产生式，构造方程式A=(a1|a2|am)B，其中BA。5/23/2023 22根据正则文法构造等价的正则

12、表达式(2)解联立方程组，求等价的正则表达式r用代入消元法逐个消去方程组中除开始符号S外的其他变量，最后即可得到关于开始符号S的解。代入消元规则如下：如果有A=r1B|r2B|rnB，则用A=(r1|r2|rn)B进行替换，其中BA；如果有A=t1A|t2A|tmA，则用A=(t1|t2|tm)*A进行替换；5/23/2023 23根据正则文法构造等价的正则表达式如果有A=(r1|r2|rn)B，B=(t1|t2|tm)C，则用A=(r1|r2|rn)(t1|t2|tm)C进行替换，其中BA；如果有A=(r1|r2|rn)B，B=(t1|t2|tm)，则用A=(r1|r2|rn)(t1|t2

13、|tm)进行替换，其中BA；对A=(t1|t2|tm)*A且A=(r1|r2|rn)B，其中BA，则用A=(t1|t2|tm)*(r1|r2|rn)B进行替换；对A=(t1|t2|tm)*A且A=r1|r2|rn则用A=(t1|t2|tm)*(r1|r2|rn)进行替换；5/23/2023 24根据正则文法构造等价的正则表达式如果有A=1、A=2、A=h，则用A=1|2|h代替之。如果最后得到的关于S的方程式为如下形式，S=1|2|h 则将方程式右边所有其中仍然含有语法变量的i(1in)删除，得到的结果就是与G等价的正则表达式；如果任意的i(1in)均含有语法变量，则就是与G等价的正则表达式

15、正则表达式转换成等价的正则文法问题：给定上的一个正则表达式r，根据r构造正则文法G，使得L(G)=L(r)定义3.3 设字母表为，A、B、C为语法变量集合，对于上的任意正则表达式r，形如Ar的式子称为正则定义式；如果r是中的字母和用正则定义式定义的变量组成的正则表达式，则形如Ar的式子称为正则定义式。5/23/2023 27将正则表达式转换成等价的正则文法按如下方法构造正则定义式，并逐步将其转换成正则文法引入开始符号S，从如下正则定义式开始Sr 按如下规则将Sr分解为新的正则定义式，在分解过程中根据需要引入新的语法变量 5/23/2023 28将正则表达式转换成等价的正则文法 Ar是正则

17、023 30例3.9正则表达式到正则文法的转换 a(a|b)*(|(.|_)(a|b)(a|b)*)=a(a|b)*|a(a|b)*.(a(a|b)*|b(a|b)*)|a(a|b)*_(a(a|b)*|b(a|b)*)=aA|aBA=aA|bA|B=aB|bB|.C|_CC=aA|bASaA|aB AaA|bA|SaA|aB AaA|bA|BaB|bB|.C|_C BaB|bB|.C|_CCaA|bA CaA|bA5/23/2023 31例3.10标识符定义的转换引入 S Sletter(letter|digit)*分解为 Sletter A A(letter|digit)A|执行连接对|

18、的分配律 Sletter A Aletter A|digit A|5/23/2023 32高级语言词法的简单描述词法单词符号的文法，用来描述高级语言中的：标识符、常数、运算符、分界符、关键字参考教材P73-77，了解如何定义高级语言中的整数、实数等的相应正则文法。5/23/2023 33例3.7某简易语言的词法正则定义式词法规则单词种别属性(|)*IDN 符号表入口()*NUM 数值:=ASG 无其它单词字符本身单词名称无 5/23/2023 34变换为正规文法letter|letter|digitdigit|digit:=+=(其它：实数、算术运算符、关系运算符、分号、括号等

19、）问题：如何识别记号？5/23/2023 353.2.4有穷状态自动机具有离散输入输出的系统的数学模型具有有穷个内部状态系统只需根据当前所处的状态和面临的输入就能确定后继的行为，处理完当前输入后系统的状态将发生变化具有初始状态和终止状态例：电梯、文本编辑程序、词法分析程序5/23/2023 36有穷自动机的物理模型有穷状态控制器输入带读头设想有个按钮，自动机启动后一个动作一个动作地做下去，直到没有输入。如果停在终态，接收；如果停在非终态，不接收一个动作：p，aq，读头前进一格FA接收的符号行的集合即为其接收的语言5/23/2023 37确定的有穷自动机的形式定义定义3.4 一个确定的有穷自动

20、机 M（记作DFA M）是一个五元组（，0，），其中是一个有穷状态集合。是一个字母表，它的每个元素称输入符号。0，0 称为初始状态。，称为终止状态集合。是一个从到的单值映射(p，)（p,，）表示当前状态为p,输入符号为a时，自动机将转换到下一个状态，称为p的一个后继。5/23/2023 38DFA的表示例设（，）其中：（，），（，）3（，），（，）（，），（，）（，），（，）一个有三种表示：（1）转换函数；（2）转移矩阵；（3）状态转换图。5/23/2023 39转移矩阵0132aaaabbbb3状态转换图易存储5/23/2023 40从状态转换图看，从初态出发，沿任一条路径到达接受状态，

21、这条路径上的弧上的标记符号连接起来构成的符号串被接受。如：abab0123aa a abbbbDFA M 接受的语言问题：如何形式描述DFA接收的语言？5/23/2023 41DFAM接受的语言如果对所有*，a，以下述方式递归地扩展的定义（，），(，）(，w），），则M所接收的语言为：()*，且(，)对于上页例中的DFA M和w=baa，(0，ba）=(2,a）=(1,）=35/23/2023 42非确定的有穷自动机NFAM定义3.6 非确定的有穷自动机是一个五元组 M（，q，）其中，q，的意义和的定义一样，而是一个从到的子集的映射，即：，其中S=。类似于FA，NFA M亦可用状态转换图表示，

22、同样也可以定义NFA M接受的语言。5/23/2023 43DFAM的模拟算法输入：以eof结尾的串x，DFA M=(Q，q0，F)；输出：如果M接受x则输出“yes”，如果M不接受x则输出“no”步骤：1 s=q0;2 c=getchar(x);3 while(c!=eof)4 s=move(s,c);5 c=getchar(x);6 7 if sF return“yes”8 else return“no”;5/23/2023 44例3.11 令=0,1，L=x|x*，x中的0的个数和1的个数都是偶数。构造自动机M，使L(M)=L 引入四个状态：q00:M读入了偶数个0和偶数个1，既是初态，

23、又是终态。q01:M读入了偶数个0和奇数个1。q10:M读入了奇数个0和偶数个1。q11:M读入了奇数个0和奇数个1。5/23/2023 45例3.11 令=0,1，L=x|x*，x中的0的个数和1的个数都是偶数。构造自动机M，使L(M)=L 状态转换图：0 1q00q10q01q01q1 1q00q10q00q1 1q1 1q01q105/23/2023 463.2.5状态转换图定义3.7 设M=(Q，q0，F)为一个有穷状态自动机，满足如下条件的有向图被称为M的状态转换图(transition diagram)：qQ q是该有向图中的一个顶点；(q，a)=p 图中有一条从顶点q到顶点p的

24、标记为a的弧；qF 标记为q的顶点被用双层圈标出；用标有start的箭头指出M的开始状态。5/23/2023 47例3.11对应的状态转换图5/23/2023 483.2.6正则表达式转换为状态转换图s sr ra(a)对应的状态转换图(b)对应的状态转换图rr rs rr rr r(c)a对应的状态转换图(d)r|s对应的状态转换图(e)rs对应的状态转换图(h)rs*对应的状态转换图(g)r+对应的状态转换图(f)r*对应的状态转换图图3.8典型正则表达式对应的状态转换图s5/23/2023 493.2.6正则表达式转换为状态转换图转换过程如下：设置一个开始状态和一个终止状态，从开始状态

25、到终止状态引一条标记为待转换表达式的边；检查图中边的标记，如果相应的标记不是字符、或用“|”连接的字符和，则根据规则(1)-(8)进行替换，直到图中不再存在不满足要求的边。按照习惯，如果一条边上标记的是，这个边就不用画出来。5/23/2023 50|(0|1)01*|0+的状态转换图5/23/2023 515/23/2023 52有穷状态自动机与单词识别的关系有穷状态自动机和正则文法等价，考虑到状态转换图的直观性，我们从状态转换图出发来考虑词法分析器的设计。允许在状态转换图的边上标记像digit、letter这样意义明确的符号，other表示例外情况5/23/2023 535/23/2023

26、 54有穷状态自动机与单词识别的关系考虑到在识别单词的过程中需要执行一些动作，所以将这些动作标记标在基本的状态转换图上。如果到达终止状态，则意味着读入了一个与当前单词无关的字符，由于这个无关字符是下一个单词的开始符号，所以必须回退一个字符。状态上的*表示向前指针必须回退一个字符。5/23/2023 55 Install_id()首先检查符号表，如果在符号表中找到了当前识别出的单词，当它被标记为关键字时，install_id()返回0，当它被标记为程序变量时，返回指向相应符号表表项的指针。如果在符号表中没有找到当前标识出的单词，则将该单词作为程序变量填入符号表中，并返回指向新建表项的指针。Ge

27、ttoken()以同样的方式在符号表中查找该单词，如果该单词是一个关键字，则返回该关键字的种别码，否则返回id。5/23/2023 56例3.14不同进制无符号整数的识别八进制数:(OCT，值)oct0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*十进制数:(DEC，值)dec(1|.|9)(0|.|9)*|0十六进制数:(HEX，值)hex0 x(0|1|.|9|a|.|f|A|F)(0|.|9|a|.|f|A|F)*5/23/2023 57识别不同进制数的状态图图3.11 识别八进制无符号整数的状态转换图5/23/2023 58识别不同进制数的状态图图3.12 识别

28、十进制无符号整数的状态转换图5/23/2023 59识别不同进制数的状态图图3.13 识别十六进制无符号整数的状态转换图5/23/2023 60识别不同进制数的状态图图3.14 识别C语言不同进制无符号整数的状态转换图5/23/2023 613.3.2单词识别的状态转换图表示 letter|letter|digit digit|digit:=|=|=|=+|-|*|/|*:|,|;5/23/2023 625/23/2023 63利用状态转换图识别单词从初始状态出发；读入一个字符；按当前字符转入下一状态；重复-直到无法继续转移为止。在遇到读入的字符是单词的分界符时，若当前状态是终止状态，说明读

29、入的字符组成了一个单词；否则，说明输入字符串w不符合词法规则。如果从状态转换图的初始状态出发，分别沿着所有可能的路径到达终止状态，并将每条路径上的标记依次连接成字符串，则可以得到状态转换图能够识别的所有单词，这些单词组成的集合也就是状态转换图识别的语言。读入字符a时从状态A转换到状态B正好对应着一步推导过程，即AaB，边正好与产生式(AaB)相对应 5/23/2023 64由正则文法构造状态转换图以每个语法变量(或其编号)为状态结点，开始符号对应初始状态S；增设一个终止状态 T；对G中每个形如AaB的产生式，从状态A到状态B画一条有向弧，并标记为a；对G中每个形如Aa的产生式，从状态A到终止

30、状态T画一条标记为a的有向弧；对G中每个形如A的产生式，从状态A到终止状态T画一条标记为any的有向弧，any表示T中的任何符号。5/23/2023 655/23/2023 665/23/2023 675/23/2023 683.3.3几种典型的单词识别问题标识符的识别关键字的识别常数的识别算符和分界符的识别回退5/23/2023 693.3.4状态转换图的实现如果将状态转换图看成是单词的识别规则库的话，则单词识别程序从当前状态(最初为初始状态)出发，读入一个输入字符后，将首先查询该规则库。重复以下过程，直至到达某个终止状态。如果从当前状态出发有一条边上标记了刚刚读入的输入字符，则

31、单词识别程序将转入这条边所指向的那个状态，并再读入一个输入字符；否则调用出错处理程序；将从初始状态到该终止状态所经历的路径上的字符所组成的字符串作为一个单词输出；并将当前状态重新置为开始状态，以便进行下一个单词的识别；如果读完输入字符流后仍未进入某个终止状态则调用出错处理程序。5/23/2023 703.3.5词法分析程序的编写状态转移图教材P93图3.15 状态转移图的实现教材P105图3.22 词法分析程序token_scan()输入：字符流输出：symbol:单词种别attr:属性（全局变量）5/23/2023 71数据结构与子例程数据结构ch 字符变量，存放当前读入的输入字符tok

32、en 字符串变量，存放构成单词的字符串 symbol 单词种别（词法分析子程序的返回值）attr 属性（全局变量）子例程install_id(token):将token存入符号表，返回入口指针getchar():从输入缓冲区中读入一个字符放入chretract():将向前指针回退一个字符，将ch置为空白符 copytoken():返回输入缓冲区中从开始指针lexeme_beginning到向前指针forward之间的字符串 isLetter()isalpha()isalnum()5/23/2023 72图3.15的状态转换图的实现算法 tokentoken_scan()charch;char*

33、token;ch=getchar();while(ch=blank|ch=tab|ch=newline)ch=getchar();lexeme_beginning+;if(isalpha(ch)ch=getchar();while(isalnum(ch)ch=getchar();retract(1);token=copytoken();return(gettoken(token),install_id(token);5/23/2023 73 else if(isdigit(ch)ch=getchar();while(isdigit(ch)ch=getchar();retract(1);toke

34、n=copytoken();return(INT,install_num(token);else switch(ch)case*:ch=getchar();if(ch=*)return(EXP,0);else retract(1);return(MULTI,0);break;5/23/2023 74 case:ch=getchar();if(ch=)return(ASSIGN,0);elseretract(1);return(COLON,0);break;case)return(NE,0);elseretract(1);return(LT,0);break;case=:return(EQ,0)

35、;break;case:ch=getchar();if(ch=)return(GE,0);elseretract(1);return(GT,0);break;case+:return(PLUS,0);break;case-:return(MINUS,0);break;case/:return(RDIV,0);break;case,:return(COMMA,0);break;case;:return(SEMIC,0);break;default:error_handle();break;return;5/23/2023 753.4词法分析程序的自动生成图3.23利用Lex建立词法分析程序的过程5/23/2023 763.4.1Lex源程序声明部分(正规定义式)%识别规则部分(识别规则)%辅助过程部分%常量定义%正规定义5/23/2023 773.4.1Lex源程序1、正规定义式letterA|B|C|Z|a|b|c|zdigit0|1|2|9identifierletter(letter|digit)*integerdigit(digit)*2、识别规则正规式动作描述token1action1token2action2tokennactionn5/23/2023 78

展开阅读全文