《词法分析部分总结》由会员分享，可在线阅读，更多相关《词法分析部分总结（80页珍藏版）》请在金锄头文库上搜索。
1、词法分析部分总结田 聪1F描述：用正规式对模式进行 描述； F构造NFA：为每个正规式构 造一个NFA； F确定化：将NFA转换成等价 的DFA； F最小化：优化DFA，使其状 态数最少； F构造词法分析器：由DFA构 造词法分析器（表驱动，直 接编码，LEX）。构造词法分析器的一般方法和步骤2涉及到的形式化概念F正则表达式（正规式） FNFA FDFA正则表达式例如：Char(char|digit)*， 字符串，abbA111, .NFADFA正则语言（正规集）3正则语言正则语言上下文无关语言上下文有关语言递归可枚举语言4正则语言F正则语言 正则表达式 有限状态自动机 F上下文无关语言 上下
2、文无关文法 非确定的下推自动机 F上下文有关语言 上下文有关文法 线性有界自动机（特殊的图灵机） F递归可枚举语言 短语结构 图灵机5Algebraic Laws for REsFUnion 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 distributes
3、over +(可分配的)a.(b+c)=a.b+a.c Exception: Concatenation is not commutative (可交换的)a.b b.a6Identities and AnnihilatorsF is the identity (单位元) for +.R + = R. F is the identity (单位元) for concatenation.R = R = R. F is the annihilator (零元) for concatenation.R = R = .7正则语言相关内容F如何证明正则表达式和NFA的等价性？（1）We need to
4、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.8RE to -NFA: BasisFSymbol a:F:a9RE to -NFA: Induction 1 UnionFor E1For E2For E1 E210RE to -NFA: Induction 2 ConcatenationFor E1For E2For E1E211RE to -NFA: Indu
5、ction 3 ClosureFor EFor E*12正则语言相关内容F如何证明正则表达式和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.13From Automata to REF Ardens ruleFor any sets of strings S and T, the equation X=SX+T has
6、 X=S*T as a solution. Moreover, this solution is unique if not in S.14From Automata to REF Given an automaton A F A has states q0, , qn with q0 being the start state FLet Xi denote the set of strings accepted by A starting in state qi FThus, L(A)=X0 F We can write an equation for each Xi, defining i
7、t in terms of the sets corresponding to its successor states.15From Automata to REq2q0q3q1b, caccaa,b,ca,bbA016From Automata to REq2q0q3q1b, caccaa,b,ca,bbA0(0) X0=aX1+bX3+cX3 (1) X1=aX3+bX2+cX0+ (2) X2=aX3+bX3+cX0 (3) X3=aX3+bX3+cX3X3=(a+b+c)X3+, by Ardens rule: X3=(a+b+c)*= (0) X0=aX1 (1) X1=bX2+c
8、X0+ (2) X2=cX0Substituing (0) and (2) in (1): X1=(bc+c)aX1+ =(bc+c)a)* (by Ardens rule)X0=a(bc+c)a)*17DFA-to-REFAnother approach FPage 93, theorem 3.4. （形式语言与自动机） FInduction on k-path.18Decision Properties of Regular Languages19Properties of Language ClassesFA language class is a set of languages.We
9、 have one example for language class: the regular languages. 任何一个正则表达式都表达了一个语言，所有的 正则表达式构成了语言类：正则语言 FLanguage classes have two important kinds of properties:uDecision properties.uClosure properties.20Decision PropertiesFA decision property for a class of languages is an algorithm that takes a formal
10、 description of a language (e.g., a DFA) and tells whether or not some property holds. FExample: Is language L empty?Suppose the representation is a DFA. Can you tell if L(A) = for DFA A?21Why Decision Properties?FWhen we talked about protocols represented as DFAs, we noted that important properties
11、 of a good protocol were related to the language of the DFA. FExample: “Does the protocol terminate?” = “Is the language finite?” FExample: “Can the protocol fail?” = “Is the language nonempty?”22Why Decision Properties (2)FWe might want a “smallest” representation for a language, e.g., a minimum-st
12、ate DFA or a shortest RE. FIf you cant decide “Are these two languages the same?”I.e., do two DFAs define the same language? You cant find the “smallest.”23Closure PropertiesFA closure property (封闭性) of a language class says that given languages in the class, an operator (e.g., union) produces anoth
13、er language in the same class. FExample: the regular languages are obviously closed under union, concatenation, and (Kleene) closure. (求补？求交？) 是正规规式 若a是上的字符，则a是正规式 若r和s分别是上的正规式，那么 （a） r|s是正规式 （b） rs是正规式 （c） r*是正规式24The Membership QuestionFOur first decision property is the question: “is string w in
14、regular language L?（成员问题）” FAssume L is represented by a DFA A. FSimulate the action of A on the sequence of input symbols forming w.25Example: Testing MembershipStart10ACB100,10 1 0 1 1Next symbolCurrentstate26Example: Testing MembershipStart10ACB100,10 1 0 1 1Next symbolCurrentstate27Example: Test
15、ing MembershipStart10ACB100,10 1 0 1 1Next symbolCurrentstate28Example: Testing MembershipStart10ACB100,10 1 0 1 1Next symbolCurrentstate29Example: Testing MembershipStart10ACB100,10 1 0 1 1Next symbolCurrentstate30Example: Testing MembershipStart10ACB100,10 1 0 1 1Next symbolCurrentstate31The Empti
16、ness ProblemFGiven a regular language, does the language contain no string at all（判空问题）. FAssume representation is DFA. FConstruct the transition graph. FCompute the set of states reachable from the start state. FIf any final state is reachable, then yes, else no.32The Infiniteness ProblemFIs a given regular language infinite? FStart wit
