Chapter04LexicalAnalysis词法分析.ppt

,北京化工大学 信息科学与技术学院计算机系 赵瑞莲 ,编译原理,2019/6/6,北京化工大学信息科学与技术学院计算机系,2,3.3.1 文法的定义,3.3 文法和语言的形式定义,定义1. 文法G=（Vn，Vt，P，Z） Vn：非终结符号集 Vt：终结符号集 P：产生式或规则的集合 Z：开始符号（识别符号） ZVn,VVn Vt 称为文法的字母表,Vn Vt,规则的定义 规则是一个有序对(U, x), 通常写为: U : x 或U x | U| = 1 |x| 0 U Vn, xV*。,2019/6/6,北京化工大学信息科学与技术学院计算机系,3,3.3.2 推导的形式定义,定义2：文法G：vx Uy，wxuy, 其中x、y V* ，UVn, u V*, 若U : u （Uu）P，则v w。 若xy，有U : u，则U u.,根据文法和推导定义，可推出终结符号串，所谓文法能推出句子来。,3.3 文法和语言的形式定义,称 v直接产生w; 或w是v直接推导; 或w直接规约到v.,定义符号间的关系。,2019/6/6,北京化工大学信息科学与技术学院计算机系,4,定义4：文法G，v，w V+ if v w , 或v=w，则v w,* = G, = G,直观意义：规范推导最右推导 最右推导：若符号串中有两个以上的非终结符时，先推右边的。 最左推导：若符号串中有两个以上的非终结符时，先推左边的。,称 v推导出（产生）w， 或w规约到v （推导长度为n）.,3.3.2 推导的形式定义,2019/6/6,北京化工大学信息科学与技术学院计算机系,5,文法GZ描述的语言 是该文法所产生的 所有句子的集合.,形式语言理论可以证明以下两点： （1）G L（G）； （2）L(G)G1，G2，Gn； 已知文法，求语言，通过推导； 已知语言，构造文法，无形式化方法，更多是凭经验。,3.3.3 语言的形式定义,3.3 文法和语言的形式定义,2019/6/6,北京化工大学信息科学与技术学院计算机系,6,编译感兴趣的问题是:,给定x, G, 求x L(G) ?,x,算法1,算法2,x L(G) ?,G,y,n,出错处理,停机,3.3 文法和语言的形式定义,2019/6/6,北京化工大学信息科学与技术学院计算机系,7,3.3.4 递归文法,1.递归规则：规则右部有与左部相同的符号 对于 U:= xUy 若x=,即U:= Uy，左递归； 若y=,即U:= xU，右递归。,3.3 文法和语言的形式定义,2019/6/6,北京化工大学信息科学与技术学院计算机系,8,3.3.5 句型的短语、简单短语和句柄,定义8. 给定文法GZ, w=xuyV+，为该文法的句型, 若 Z= xUy, 且U=u, 则u是句型w相对于U的短语； 若 Z= xUy, 且U=u, 则u是句型w相对于U的简单短语。 其中U Vn，u V+，x,y V*,*,*,直观理解：短语是前面句型中的某个非终结符所能推出的符号串。,3.3 文法和语言的形式定义,2019/6/6,北京化工大学信息科学与技术学院计算机系,9,定义9. 任一句型的最左简单短语称为该句型的句柄。,3.3.5 句型的短语、简单短语和句柄,3.3 文法和语言的形式定义,定义12. 对句型中最左简单短语（句柄）进行的规 约称为规范规约。,2019/6/6,北京化工大学信息科学与技术学院计算机系,10,( 3 ) 语法树与推导,句型推导过程句型语法树的生长过程,2.4.1 推导与语法树,2019/6/6,北京化工大学信息科学与技术学院计算机系,11,2.4.1 推导与语法树,2019/6/6,北京化工大学信息科学与技术学院计算机系,12,2型： P： U:= u 其中 UVn， uV*,2型语言：L2. 这种语言可以由下推自动机接受.,称为上下文无关文法。 也即把U改写为u时，不必考虑上下文。,3.8 文法和语言分类,2019/6/6,北京化工大学信息科学与技术学院计算机系,13,P： U:=T 或 U:=Tw 其中 U、wVn TVt,3型语言：L3 又称正则语言、正则集合. 这种语言可以由有穷自动机接受.,3型文法称为正则文法。 它是对2型文法进行进一步限制。,P： U:=T 或 U:=wT 其中 U、wVn TVt,3型文法：,3.8 文法和语言分类,左线性,右线性,2019/6/6,北京化工大学信息科学与技术学院计算机系,14,Chapter 4 Scanning (lexical analysis) 词法分析,4.1 扫描处理 4.2 正则表达式 4.3 有穷自动机 4.4 从正规表达式到DFA 4.4.1 从正则表达式到NFA 4.4.2 从NFA到DFA 4.4.3 DFA的化简 4.5 TINY扫描程序的实现 4.6 利用L e x自动生成扫描程序,2019/6/6,北京化工大学信息科学与技术学院计算机系,15,词 法 分 析,源 程 序,目 标 程 序,语 法 分 析,语 义 分 析,中 间 代 码 优 化,中 间 代 码 生 成, The phase of a compiler 编译程序的结构,目 标 代 码 生 成,2019/6/6,北京化工大学信息科学与技术学院计算机系,16,词 法 分 析,源 程 序,目 标 程 序,语 法 分 析,语 义 分 析,中 间 代 码 优 化,中 间 代 码 生 成,目 标 代 码 生 成, The phase of a compiler 编译程序的结构,2019/6/6,北京化工大学信息科学与技术学院计算机系,17,4.1 扫描处理, 词法分析(扫描)程序的功能 词法分析：根据词法规则识别及组合单词， 进行词法检查。 对数字常数完成数字字符串到（二进制）数值 的转换。 删去空格字符和注解。,2019/6/6,北京化工大学信息科学与技术学院计算机系,18, 词法分析程序实现方案：基本上有两种,1. 词法分析单独作为一遍,4.1 扫描处理,2. 词法分析程序作为单独的子程序,优点: 结构清晰、各遍功能单一 缺点：效率低。,2019/6/6,北京化工大学信息科学与技术学院计算机系,19, 单词的种类 1. 保留字：begin、end、for、do 2. 标识符： 3. 常数：无符号数、布尔常数、字符串常数等 4. 分界符：+、-、*,4.1 扫描处理,单词符号是一个程序设计语言的基本语法符号。,2019/6/6,北京化工大学信息科学与技术学院计算机系,20, 词法分析程序的输出形式-单词的内部形式Token,单词类别 单词自身值,4.1 扫描处理,语法分析 需要的信息,编译其他阶段 需要的信息,记号的属性： 任何与记号相关的值。,Token:,2019/6/6,北京化工大学信息科学与技术学院计算机系,21, 词法分析程序的输出形式-单词的内部形式Token,几种常用的单词内部形式： 1、按单词种类分类 2、保留字和分界符采用一符一类 3、标识符和常数的单词值又为指示字（指针值）,单词类别 单词自身值,4.1 扫描处理,Token:,2019/6/6,北京化工大学信息科学与技术学院计算机系,22,1、按单词种类分类,4.1 扫描处理,2019/6/6,北京化工大学信息科学与技术学院计算机系,23,2、保留字和分界符采用一符一类,2019/6/6,北京化工大学信息科学与技术学院计算机系,24,typedef enum /* book-keeping tokens */ ENDFILE,ERROR, /* reserved words */ IF,THEN,ELSE,END,REPEAT,UNTIL,READ,WRITE, /* multicharacter tokens */ ID,NUM, /* special symbols */ ASSIGN,EQ,LT,PLUS,MINUS,TIMES,OVER,LPAREN,RPAREN,SEMI TokenType;, Tokens(记号)的枚举表示,每一个记号的表示： Typedef struct TokenType tokenval; char *stringval; int numval; TokenRecord,4.1 扫描处理,2019/6/6,北京化工大学信息科学与技术学院计算机系,25,The scanner (Lexical analysis ): TokenType getToken(void),例：C的源代码：aindex = 4 + 2,4.1 扫描处理,2019/6/6,北京化工大学信息科学与技术学院计算机系,26,4. 2 正则表达式, A regular expression r 正则表达式r,is defined by the set of strings that it matches., L(r) 正则表达式生成的语言（正则语言/正则集）,language generated by the regular expression.,2019/6/6,北京化工大学信息科学与技术学院计算机系,27,4.2.1 正则表达式和正则集合的递归定义,有字母表, 定义在上的正则表达式和正则集合递归定义如下: 1和都是上的正则表达式，它们所表示的正则集合分别为：和; 2任何a，a是上的正则表达式，它所表示的正则集合为：a； 3假定U和V是上的正则表达式, 它们所表示的正则集合分别记为L(U)和L(V)，那么U|V，UV和U*也都是 上的正则表达式，它们所表示的正则集合分别为L(U) L(V)、L(U)L(V)和L(U)*； 4任何上的正则表达式和正则集合均由1、2和3产生。,2019/6/6,北京化工大学信息科学与技术学院计算机系,28, The single character from the alphabet, expression a matches the character a. L(a) = a empty string(): the string contains no characters. L() = or : matches no string at all ,whose language is the empty set. L() = , Basic Regular Expression 基本正则表达式,4.2.1 正则表达式和正则集合的递归定义,2019/6/6,北京化工大学信息科学与技术学院计算机系,29, | Choice among alternatives 或(选择), Regular Expression Operation 正则表达式的运算,L(r|s) = L(r ) L(s ) L(a|b|c|d) = a,b,c,d,4.2.1 正则表达式和正则集合的递归定义,2019/6/6,北京化工大学信息科学与技术学院计算机系,30, Names for regular expression 正则表达式的名字, Precedence of Operation and use of parentheses 运算符的优先级和括号的使用,Precedence: * the first the second | the third,(0|1|2|3|9)(0|1|2|3|9)*,例：a|bc* ab|c*d ,(先*，其次 ，最后 |),a|(b(c*),(ab)|(c*)d),正则表达式相等 这两个正则表达式表示的语言相等,2019/6/6,北京化工大学信息科学与技术学院计算机系,31, 用正则表达式的运算符构造正则表达式,ba*,(a|b)* (aa|bb) (a|b)*,上所有以a为首的字的集合,例：令=a,b，上的正则式和相应的正规集如下：,2019/6/6,北京化工大学信息科学与技术学院计算机系,32,设e1, e2和e3均是某字母表上的正则表达式, 则有: 单位正则表达式: e = e = e 交换律: e1 | e2 = e2 | e1 结合律: e1|(e2|e3) = (e1|e2)|e3 e1(e2e3) = (e1e2)e3 分配律: e1(e2|e3) = e1e2|e1e3 (e1|e2)e3 = e1e3|e2e3 此外: r* = (r|)* r* =r* (r|s)* = (r*s*)*, 正则表达式的性质,2019/6/6,北京化工大学信息科学与技术学院计算机系,33,4.2.2 Extensions to Regular Expressions,. * b . *,2019/6/6,北京化工大学信息科学与技术学院计算机系,34,4.2.3 Regular Expressions for Programming Language Tokens 记号的正则表达式,nat = 0-9+ signedNat = (+|-)?nat number = signedNat(“.”nat)? (E signedNat)?,reserved = if | while | do | letter = a-z A-Z digit = 0-9 identifier = letter(letter|digit)*,2019/6/6,北京化工大学信息科学与技术学院计算机系,35,4.2.3 Regular Expressions for Programming Language Tokens,3. Comments 注释,/* this is a C comment */ this is a pascal comment ,4. Ambiguity, White Space, and Lookahead 二义性、空格、回溯,Pascal 注释可写作： ( ) * ,2019/6/6,北京化工大学信息科学与技术学院计算机系,36,3型文法称为正则文法。 3型语言：L3 又称正则语言(正则集合)可以由有穷自动机接受。, 3型文法： (左线性) P：U T 或 U wT, 其中 U、wVN, TVT (右线性) P：U T 或 U Tw, 其中 U、wVN , TVT,4.2.4 正则文法,2019/6/6,北京化工大学信息科学与技术学院计算机系,37, 正则表达式与3型文法等价 例如： 正则表达式： ba* a(a|b)*,3型文法： Z := Za|b Z:=Za|Zb|a,例： 3型文法 S:= aS|aB B:= bC C:= aC|a,a*a,ba*a,aS|aba*a,a*aba*a,正则表达式,2019/6/6,北京化工大学信息科学与技术学院计算机系,38,4.3 有穷自动机,状态转换图 有穷自动机,2019/6/6,北京化工大学信息科学与技术学院计算机系,39,4.3.1 状态转换图, 状态转换图的表示方法,结点代表状态(state)，用圆圈表示。 状态之间用箭弧(transition)连结，箭弧上的标记(字符)代表在射出结点(即箭弧始结点)状态下可能出现的输入字符或字符类。 一个有穷自动机只包含有限个状态(即有限个结点)，其中一个为初态(start state)，至少一个为终态(接受状态accepting state) (双圈表示)。,2019/6/6,北京化工大学信息科学与技术学院计算机系,40,例3：识别整数的转换图,例2：识别标识符的转换图,在状态1下，若输入字符为x，则读进x，并转换到状态2； 若输入字符为y，则读进y，并转换到状态3。,例1：,2019/6/6,北京化工大学信息科学与技术学院计算机系,41,文法： 1. := 字母 | 字母 | 数字 2. :=数字 | 数字 3. := : | + | * | , | ( | ) 4. := = 5. := :,2019/6/6,北京化工大学信息科学与技术学院计算机系,42,标识符,无符号整数,单字符分界符,双字符分界符,S,标,非字母数字,字母,字母、数字,数,非数字,数字,数字,单界,其他字符,+ * ， （ ）,出口,冒号,其他字符,：,双界,=,非 =,出错,其他,读字符,查保留字表,返回S,2019/6/6,北京化工大学信息科学与技术学院计算机系,43,识别算法（自然语言描述）,利用状态图可按如下步骤分析和识别字符串x： 1、置初始状态为当前状态，从x的最左字符开始，重复步骤 2，直到x右端为止。 2、扫描x的下一个字符，在当前状态所射出的弧中找出标记有该字符的弧，并沿此弧过渡到下一个状态； 如果找不到标有该字符的弧，那么x不是句子，过程到此结束； 如果扫描的是x的最右端字符，并从当前状态出发沿着标有该字符的弧过渡到下一个状态为终止状态，则x是句子。,2019/6/6,北京化工大学信息科学与技术学院计算机系,44,4.3.2 Finite Automata有穷自动机,Finite automata( finite-state machines) are a mathematical way of describing particular kinds of algorithms.,Definite of Deterministic finite automation (DFA) 确定有穷自动机 Nondeterministic finite automation (NFA) 非确定有穷自动机,2019/6/6,北京化工大学信息科学与技术学院计算机系,45, DFA (deterministic finite automation) 确定有穷自动机, an alphabet 输入字母表（终结符集合） a set of states S 有穷状态集（非终结符集合） a transition function T : S S (状态转换函数) a start state s0S 唯一的初始状态 a set of accepting states A S 接受状态集,一个确定的有穷自动机（DFA）M是一个五元式: M=(S, ，T,S0, A) ，其中,“确定”即状态转移函数是单值函数。,2019/6/6,北京化工大学信息科学与技术学院计算机系,46, Example： Numbers 数,digit = 0-9 nat = digit + signedNat = (+|-)? Nat Number = singedNat(“.”nat)?(E signedNat)?,2019/6/6,北京化工大学信息科学与技术学院计算机系,47,例：有DFA M=(0,1,2,3,a,b, T, 0, 3) 其中T为: T(0,a)=1 T(0,b)=2 T(1,a)=3 T(1,b)=2 T(2,a)=1 T(2,b)=3 T(3,a)=3 T(3,b)=3,一个DFA可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示T(s,a)的值，这个矩阵称状态表（状态转移矩阵）。,后继状态, 状态表,2019/6/6,北京化工大学信息科学与技术学院计算机系,48, DFA M所接受的符号串 令= ，*，若s1= T(s0,c1), s2= T(s1,c2), , sn = T(sn-1,cn) 且Sn A，则可以写成T(S0, )= Sn, 我们称可为M所接受。,DFA M所接受的语言为： L(M)=|T(S0, )=Sn, Sn A,换言之：若存在一条初始状态到某一终止状态的路径，且这条路径上弧的标记符号连接成符号串，则称为DFA M（接受）识别。,2019/6/6,北京化工大学信息科学与技术学院计算机系,49,4. 3.2.2 Nondeterministic finite automation(NFA) 非确定有穷自动机, NFA M ：, an alphabet 输入字母表（终结符集合） a set of states S 有穷状态集（非终结符集合） a transition function T: S x ( U) 2S (状态转换函数) a set of start states S0 S 初始状态集 a set of accepting states A S 接受状态集,一个非确定的有穷自动机NFA M是一个五元式: NFA M=(S, , T, S0, A)，其中,“非确定” 即状态转移函数是多值函数。,由M接受的语言L(M) L(M) | ciU, s1= T(s0,c1), s2= T(s1,c2), , sn = T(sn-1,cn) , sn A. ,2019/6/6,北京化工大学信息科学与技术学院计算机系,50,2019/6/6,北京化工大学信息科学与技术学院计算机系,51,NFA,2019/6/6,北京化工大学信息科学与技术学院计算机系,52,4.3.3 Implementation of finite automata in Code 用代码实现有穷自动机, 识别标识符的DFA （方法1）, starting in state 1 if the next character is a letter then advance the input; now in state 2 while the next character is a letter or a digit do advance the input; stay in state 2 end while; go to state 3 without advancing the input accept; else error or other cases end if;,2019/6/6,北京化工大学信息科学与技术学院计算机系,53, 识别标识符的DFA （方法2）,state := 1; ch := next input character; while not Acceptstate and not error(state) do newstate := Tstate,ch; if Advancestate,ch then ch := next input character; state := newstate; end while; if Acceptstate then accept;,2019/6/6,北京化工大学信息科学与技术学院计算机系,54,4.4 From Regular Expression To DFA 从正则表达式到DFA,the algorithm : translating a regular expression into a DFA,2019/6/6,北京化工大学信息科学与技术学院计算机系,55,4.4.1 From Regular Expression To NFAs 从正则表达式到NFA,1. (a) 对于正则式,所构造NFA:,x,y,(b) 对于正则式,所构造NFA:,x,y,(c) 对于正则式a, a,则 NFA:,x,y,a,2019/6/6,北京化工大学信息科学与技术学院计算机系,56,2. 若s,t为上的正则式,相应的NFA分别为N(s)和N(t);,(a)对于正则式R=s|t, NFA(R),(b)对正则式R=st,NFA(R),(c)对于正则式R=s*, NFA(R),(d)对R=(s),与R=S的NFA一样.,例:为R=(a|b)*abb构造NFA,使得L(N)=L(R),分解R的方法有很多种！,R=(a|b)*abb,2019/6/6,北京化工大学信息科学与技术学院计算机系,59, 从正则表达式到NFA 方法二:,2019/6/6,北京化工大学信息科学与技术学院计算机系,60,例：令=a,b， 上所有含有两个相继的a或两个相继的b的字的集合用NFA表示如下：,(a|b)* (aa|bb) (a|b)*,NFA M=( 0,1,2,3,4,5,6,7 , a,b , T, 0 , 7 ) 其中T如上（不可省略）。,初态,终态,(a|b)* (aa|bb) (a|b)*,2019/6/6,北京化工大学信息科学与技术学院计算机系,61,4.4.2 从NFA到DFA,2019/6/6,北京化工大学信息科学与技术学院计算机系,62,T（）合并 （如果有S1S2,则把S2状态合并到S1状态） 符号合并,NFA允许边出现, 转换思想,4.4.2 从NFA到DFA,2019/6/6,北京化工大学信息科学与技术学院计算机系,63,为了使得NFA确定化，给出两个定义：,解：根据定义： -closure（I）=1，3,2019/6/6,北京化工大学信息科学与技术学院计算机系,64, J是从状态子集I中的每个状态出发，经过标记为a的弧而达到的状态集合。, Ia是状态子集,其元素为J中的状态，加上从J中每一个状态出发通过弧到达的状态。,定义2: 状态子集的构造：,sI,Ia=-closure(J) =-closure(T(1，a)） =-closure(2，4） =2，4，6,令I是NFA M的状态集的一个子集, a 定义: Ia=-closure(J) 其