《《词法分析部分总结》ppt课件》由会员分享，可在线阅读，更多相关《《词法分析部分总结》ppt课件（80页珍藏版）》请在金锄头文库上搜索。
1、1,词法分析部分总结,田 聪,2,描述：用正规式对模式进行描述； 构造NFA：为每个正规式构造一个NFA； 确定化：将NFA转换成等价的DFA； 最小化：优化DFA，使其状态数最少； 构造词法分析器：由DFA构造词法分析器（表驱动，直接编码，LEX）。,构造词法分析器的一般方法和步骤,3,涉及到的形式化概念,正则表达式（正规式） NFA DFA,正则表达式 例如：Char(char|digit)*，,字符串，abb A111, .,NFA,DFA,正则语言（正规集）,4,正则语言,正则语言,上下文无关语言,上下文有关语言,递归可枚举语言,5,正则语言,正则语言 正则表达式 有限状态自动机 上下
2、文无关语言 上下文无关文法 非确定的下推自动机 上下文有关语言 上下文有关文法 线性有界自动机（特殊的图灵机） 递归可枚举语言 短语结构 图灵机,6,Algebraic Laws for REs,Union and concatenation behave like addition and multiplication. + is commutative (可交换的) and associative (可结合的) a+b=b+a, a+b+c= a+(b+c) concatenation is associative (可结合的) a.b.c=a.(b.c) Concatenation di
3、stributes over +(可分配的) a.(b+c)=a.b+a.c Exception: Concatenation is not commutative (可交换的) a.b b.a,7,Identities and Annihilators, is the identity (单位元) for +. R + = R. is the identity (单位元) for concatenation. R = R = R. is the annihilator (零元) for concatenation. R = R = .,8,正则语言相关内容,如何证明正则表达式和NFA的等价性
4、？ （1）We need to show that for every RE, there is an automaton that accepts the same language. （2）And for every automaton, there is a RE defining its language.,9,RE to -NFA: Basis,Symbol a: :,10,RE to -NFA: Induction 1 Union,11,RE to -NFA: Induction 2 Concatenation,12,RE to -NFA: Induction 3 Closure,
5、13,正则语言相关内容,如何证明正则表达式和NFA的等价性？ （1）We need to show that for every RE, there is an automaton that accepts the same language. （2）And for every automaton, there is a RE defining its language.,14,From Automata to RE,Ardens rule For any sets of strings S and T, the equation X=SX+T has X=S*T as a solution.
6、 Moreover, this solution is unique if not in S.,15,From Automata to RE,Given an automaton A A has states q0, , qn with q0 being the start state Let Xi denote the set of strings accepted by A starting in state qi Thus, L(A)=X0 We can write an equation for each Xi, defining it in terms of the sets cor
7、responding to its successor states.,16,From Automata to RE,17,From Automata to RE,q2,q0,q3,q1,b, c,a,c,c,a,a,b,c,a,b,b,A0,(0) X0=aX1+bX3+cX3 (1) X1=aX3+bX2+cX0+ (2) X2=aX3+bX3+cX0 (3) X3=aX3+bX3+cX3,X3=(a+b+c)X3+, by Ardens rule: X3=(a+b+c)*= ,(0) X0=aX1 (1) X1=bX2+cX0+ (2) X2=cX0,Substituing (0) an
8、d (2) in (1): X1=(bc+c)aX1+ =(bc+c)a)* (by Ardens rule),X0=a(bc+c)a)*,18,DFA-to-RE,Another approach Page 93, theorem 3.4. （形式语言与自动机） Induction on k-path.,19,Decision Properties of Regular Languages,20,Properties of Language Classes,A language class is a set of languages. We have one example for lang
9、uage class: the regular languages. 任何一个正则表达式都表达了一个语言，所有的正则表达式构成了语言类：正则语言 Language classes have two important kinds of properties: Decision properties. Closure properties.,21,Decision Properties,A decision property for a class of languages is an algorithm that takes a formal description of a language
10、 (e.g., a DFA) and tells whether or not some property holds. Example: Is language L empty? Suppose the representation is a DFA. Can you tell if L(A) = for DFA A?,22,Why Decision Properties?,When we talked about protocols represented as DFAs, we noted that important properties of a good protocol were
11、 related to the language of the DFA. Example: “Does the protocol terminate?” = “Is the language finite?” Example: “Can the protocol fail?” = “Is the language nonempty?”,23,Why Decision Properties (2),We might want a “smallest” representation for a language, e.g., a minimum-state DFA or a shortest RE
12、. If you cant decide “Are these two languages the same?” I.e., do two DFAs define the same language? You cant find the “smallest.”,24,Closure Properties,A closure property (封闭性) of a language class says that given languages in the class, an operator (e.g., union) produces another language in the sam
13、e class. Example: the regular languages are obviously closed under union, concatenation, and (Kleene) closure. (求补？求交？) 是正规式 若a是上的字符，则a是正规式 若r和s分别是上的正规式，那么 （a） r|s是正规式 （b） rs是正规式 （c） r*是正规式,25,The Membership Question,Our first decision property is the question: “is string w in regular language L?（成员
14、问题）” Assume L is represented by a DFA A. Simulate the action of A on the sequence of input symbols forming w.,26,Example: Testing Membership,0 1 0 1 1,27,Example: Testing Membership,0 1 0 1 1,28,Example: Testing Membership,0 1 0 1 1,29,Example: Testing Membership,0 1 0 1 1,30,Example: Testing Member
15、ship,0 1 0 1 1,31,Example: Testing Membership,0 1 0 1 1,32,The Emptiness Problem,Given a regular language, does the language contain no string at all（判空问题）. Assume representation is DFA. Construct the transition graph. Compute the set of states reachable from the start state. If any final state is r
16、eachable, then yes, else no.,33,The Infiniteness Problem,Is a given regular language infinite? Start with a DFA for the language. Key idea: if the DFA has n states, and the language contains any string of length n or more, then the language is infinite. Otherwise, the language is surely finite. Limited to strings of length n or less.,34,Proof of Key Idea,If an n-state DFA accepts a string w of length n or more, then there
