编译原理教学课件：Chapter 3 - Lexical Analysis

1、Where we are ?2022/7/181Lexical AnalysisSyntax AnalysisSemantic AnalysisIR GenerationIR OptimizationCode GenerationOptimizationSourceCodeMachineCodewhile (ip z)+ip;w h i l ewhile (ip z)+ip;( i pz ) nt + + i p ;w h i l ewhile (ip z)+ip;( i pz ) nt + + i p ;T_While(T_IdentT_Ident)+T_Identipzipw h i l

2、ewhile (ip z)+ip;( i pz ) nt + + i p ;T_While(T_IdentT_Ident)+T_IdentipzipWhile+IdentipIdentzIdentipScanning a Source Filew h i l e( 1 3 7 i ) nt + + i ;w h i l e( 1 3 7 i ) nt + + i ;Scanning a Source Filew h i l e( 1 3 7 i ) nt + + i ;Scanning a Source Filew h i l e( 1 3 7 i ) nt + + i ;Scanning a

3、 Source Filew h i l e( 1 3 7 i ) nt + + i ;Scanning a Source Filew h i l e( 1 3 7 i ) nt + + i ;Scanning a Source Filew h i l e( 1 3 7 i ) nt + + i ;Scanning a Source Filew h i l ei ) nt + + i ;T_While( 1 3 7Scanning a Source Filew h i l ei ) nt + + i ;( 1 3 7.T_WhileThe piece of the original progra

4、mfrom which we made the token iscalled a lexemeThis is called a token. You can think of it as an enumerated type representing what logical entity we read out of the source code.Scanning a Source FileScanning a Source Filew h i l ei ) nt + + i ;T_While( 1 3 7w h i l ei ) nt + + i ;T_While( 1 3 7Scann

5、ing a Source Filew h i l ei ) nt + + i ;T_While( 1 3 7Scanning a Source Filew h i l ei ) nt + + i ;T_While( 1 3 7Sometimes we will discard alexemerather than storing it for later use.Here, we ignore whitespace, since it has no bearing on the meaning Of the program.Scanning a Source Filew h i l ei )

6、nt + + i ;T_While( 1 3 7Scanning a Source Filew h i l ei ) nt + + i ;T_While( 1 3 7Scanning a Source Filew h i l ei ) nt + + i ;T_While( 1 3 7Scanning a Source Filei ) nt + + i ;( 1 3 7w h i l eT_While(Scanning a Source Filei ) nt + + i ;( 1 3 7w h i l eT_While(Scanning a Source Filei ) nt + + i ;(

7、1 3 7w h i l eT_While(Scanning a Source Filei ) nt + + i ;( 1 3 7w h i l eT_While(Scanning a Source Filei ) nt + + i ;( 1 3 7w h i l eT_While(Scanning a Source Filei ) nt + + i ;( 1 3 7w h i l eT_While (Scanning a Source Filei ) nt + + i ;w h i l eT_While( 1 3 7T_IntConst137(Scanning a Source Filew

8、h i l ei ) nt + + i ;T_While( 1 3 7(T_IntConst137Some tokens can haveattributes that store Extra information about the token. Here we store which integer is represented.Scanning a Source File C+: Nested template declarationsvectorvector myVectorScanning is Hard C+: Nested template declarationsvector

9、 vector myVectorScanning is Hard C+: Nested template declarations(vector (vector myVector)Scanning is HardScanning is Hard C+: Nested template declarations(vector (vector myVector) Again, can be difficult to determine where to split. PL/1: Keywords can be used as identifiers.Scanning is Hard PL/1: K

10、eywords can be used as identifiers.IF THEN THEN THEN = ELSE; ELSE ELSE = IFScanning is Hard PL/1: Keywords can be used as identifiers.IF THEN THEN THEN = ELSE; ELSE ELSE = IFScanning is HardScanning is Hard PL/1: Keywords can be used as identifiers.IF THEN THEN THEN = ELSE; ELSE ELSE = IF Can be dif

11、ficult to determine how to label lexemes.Challenges in ScanningHow do we determine which lexemes are associated with each token?When there are multiple ways we could scan the input, how do we know which one to pick?How do we address these concerns efficiently?#include using namespace std;int main()f

12、or(int i=32;i=127;i+)coutASCII码是i的字符是(char)i . ExampleL(a|bc*)=a (b ,c, cc,)=a b, bc, bcc, =a, b, bc, bcc, Simple Regular ExpressionsSuppose the only characters are 0 and 1.Here is a regular expression for strings containing 00 as a substring: (0 | 1)*00(0 | 1)*Simple Regular ExpressionsSuppose the

13、only characters are 0 and 1.Here is a regular expression for strings containing 00 as a substring: (0 | 1)*00(0 | 1)*Simple Regular ExpressionsSuppose the only characters are 0 and 1.Here is a regular expression for strings containing 00 as a substring: (0 | 1)*00(0 | 1)*1101110010100001111101111001

14、1111Simple Regular ExpressionsSuppose the only characters are 0 and 1.Here is a regular expression for strings of length exactly four:(0|1)(0|1)(0|1)(0|1)Simple Regular ExpressionsSuppose the only characters are 0 and 1.Here is a regular expression for strings of length exactly four:(0|1)(0|1)(0|1)(

15、0|1)Simple Regular ExpressionsSuppose the only characters are 0 and 1.Here is a regular expression for strings of length exactly four:(0|1)(0|1)(0|1)(0|1)0000101011111000Simple Regular ExpressionsSuppose the only characters are 0 and 1.Here is a regular expression for strings of length exactly four:

16、(0|1)40000101011111000Simple Regular ExpressionsSuppose the only characters are 0 and 1.Here is a regular expression for strings that contain at most one zero:Simple Regular ExpressionsSuppose the only characters are 0 and 1.Here is a regular expression for strings that contain at most one zero:1*(0

17、 | )1*Simple Regular ExpressionsSuppose the only characters are 0 and 1.Here is a regular expression for strings that contain at most one zero:1*(0 | )1*1111011111111101110Simple Regular ExpressionsSuppose the only characters are 0 and 1.Here is a regular expression for strings that contain at most

18、one zero:1*0?1*11110111111111011102022/7/1862ExampleGiven the description of the strings to be matched and translate the description into a regular expression=a,b,c, regular expression of strings that contain exactly one b is _?Regular expression of strings that contain at most one b is _?Email addr

19、ess?(a|c)*b(a|c)*(a|c)*|(a|c)*b(a|c)* or (a|c)*(b| )(a|c)*a-z(a-z0-9*-_?a-z0-9+)*(a-z0-9*-_?a-z0-9+)+.a-z2,3(.a-z2)?2022/7/1863LanguageDefinitionAny set of strings over some fixed alphabetExample is a language, the empty set is also a language2022/7/1864Operations on language ConcatenationConcatenat

20、ion of L and M is written as LMLM =st|sL,tMExample:L=ab,cde M = 0,1LM =ab0,ab1,cde0,cde1A=A=AExponentiationThe exponentiation of L is defined as:L0 = L1 = L , L2 = LLLK = LL.L(LK is L concatenated with itself k-1 times)2022/7/1865ClosureClosure of L ( written as L*) denotes zero or more concatenatio

21、ns of L L* = L 0 L1 L 2 L 3Example：L=0，1L*=L0L1L2=,0,1,00,01,10,11,000,Positive closure of L (written as L+) denotes one or more concatenation of LL += L 1 L 2 L 3L *= L 0 L +L += LL*= L* L2022/7/18662.2.2 Definition of Regular ExpressionsThe set of basic regular expressionEssential set of operation

22、s that generate new regular expression from existing onesA regular expression is one of the following: and are regular expressions ,L()=, L()= Any is a regular expression of ,L()=2022/7/1867if1 and2 are regular expressions of , then the following are all regular expressions of :(1)1 (1)(2)12(1)(2)12

23、(1)(1)language generated by the regular expressionregular expression2022/7/1868Example=a，b, the following are regular expressions and the language they generatedregular expression raa|bab(a|b)(a|b)a(ab)L(r)aa, babaa, ab, ba, bb ,a, aa, ,a, b, aa, ab, 2022/7/1869ExplanationThe same language may be ge

24、nerated by many different regular expressionse1= (ab), e2 = bae1= b(ab) , e2 =(ba)bNot all sets of strings that we can describe in simple terms can be generated by regular expressionsExample:The set of strings S=b,aba,aabaa, = anban|n0 cannot be generated by regular expressions2022/7/18702.2.3 Regul

25、ar Expression for Programming Language TokensTypical regular expression for tokens, let l=a|b|zd=0|1|9Identifier:Unsigned integer:Number with an exponent (e.g: 2.71E-2)Reserved word:l ( l | d)*dd*dd*(.dd*| )(e(+|-| )dd*| )if|while|do|2022/7/1871AmbiguitySome strings can be matched by several differe

26、nt regular expressionsLanguage definition must give disambiguating rulesWhen a string can be either an identifier or a keyword, keyword interpretation is preferredWhen a string can be a single token or a sequence of several tokens, the single-token interpretation is preferred (principle of longest s

27、ubstring)2022/7/1872Token delimitersCharacters that are unambiguously part of other tokens are delimitersExample: in string “xtemp=ytemp” = is a delimiter Blanks, newlines, tab characters, comment are all token delimitersExample: in string “while x” two tokens “while” and “x” are separated by a blan

28、kScanner discard them after checking for any token delimiting effects2022/7/1873LookaheadScanner must deal with the problem of lookahead one or more charactersFor example: recognizing the special symbol “:=”,when encounter “:” , scanner must lookahead to determine whether the token is “:” or “:=” Lo

29、okahead tokens should not be consumed from the input string 2022/7/1874The process of constructing a scanner :regular expressionprogram for scannerDFANFAstartA Simple AutomatonA,B,C,.,ZEach circle is a state of the automaton. The automatons configuration is determined by what state(s) it is in.start

30、A Simple AutomatonA,B,C,.,ZstartA Simple AutomatonA,B,C,.,ZThese arrows are called transitions . The automaton changes which state(s) it is in by following transitions.startA Simple AutomatonA,B,C,.,Z H E Y A The automaton takes a String as input and decides whether to accept or reject the string.st

31、artA Simple AutomatonA,B,C,.,Z H E Y A startA Simple AutomatonA,B,C,.,Z H E Y A startA Simple AutomatonA,B,C,.,Z H E Y A startA Simple AutomatonA,B,C,.,Z H E Y A startA Simple AutomatonA,B,C,.,Z H E Y A startA Simple AutomatonA,B,C,.,Z H E Y A startA Simple AutomatonA,B,C,.,Z H E Y A startA Simple A

32、utomatonA,B,C,.,Z H E Y A startA Simple AutomatonA,B,C,.,Z H E Y A startA Simple AutomatonA,B,C,.,Z H E Y A startA Simple AutomatonA,B,C,.,Z H E Y A The double circle indicates that this state is an accepting state. Theautomaton accepts the string if it ends in an accepting state. startA Simple Auto

33、matonA,B,C,.,Z startA Simple AutomatonA,B,C,.,Z startA Simple AutomatonA,B,C,.,Z startA Simple AutomatonA,B,C,.,Z startA Simple AutomatonA,B,C,.,Z startA Simple AutomatonA,B,C,.,Z startA Simple AutomatonA,B,C,.,ZThere is no transition on “here, so the automaton dies and rejects. startA Simple Automa

34、tonA,B,C,.,ZThere is no transition on “here, so the automaton dies and rejects.startA Simple AutomatonA,B,C,.,Z A B C A B CstartA Simple AutomatonA,B,C,.,ZstartA Simple AutomatonA,B,C,.,Z A B CstartA Simple AutomatonA,B,C,.,Z A B CstartA Simple AutomatonA,B,C,.,Z A B CstartA Simple AutomatonA,B,C,.,

35、Z A B CstartA Simple AutomatonA,B,C,.,ZThis is not an accepting state, so the automaton rejects. A B C2022/7/181052.3 Finite AutomataFunction :Finite automata are mathematical ways of describing particular kinds of algorithms.Here they are used to describe the process of recognizing patterns written

36、 in regular expressions and so can be used to construct scannersCategory:Deterministic Finite Automata (DFA)Nondeterministic Finite Automata (NFA)Relationship between finite automata and regular expressions2022/7/18106ExampleRegular expression for identifierlet letter=a|b|zdigit=0|1|9The process of

37、recognizing such an identifier can be described as finite automataidentifier=letter(letter|digit)*13letterletterdigit2other2022/7/18107States: are locations in the process of recognition recording how much of the pattern has already been seenTransitions: record a change from one state to anotherStar

38、t state: at which the recognition process beginsAccepting states: represent the end of the recognition process13letterletterdigit2other2022/7/18108The process of recognizing an actual string can be indicated by listing the sequence of states and transitions in the diagram used in the recognition pro

39、cess. 13letterletterdigit2otherExample: recognizing process of “xtemp=.”:122222xtemp3=2022/7/181092.3.1 Definition of DFAA DFA M=（S，T，S0，A）S is a set of states is an alphabetT is a transition function T:SS, T(Si,a)=Sj represents when the current state is Si and the current input character is a，DFA w

40、ill transit to state SjS0S is a start stateA S is a set of accepting states2022/7/18110ExampleDFA M=(S，U，V，Q, a，b, f, S, Q). f is defined as following：f（S，a）=Uf（S，b）=V f（V，a）=Uf（V，b）=Qf（U，a）=Qf（U，b）=Vf（Q，a）=Qf（Q，b）=QThe meaning of deterministic:The next state is uniquely given by the current state a

41、nd the current input character.2022/7/18111Transition Diagram of DFAEach state is a node of the diagramThe start state is indicated by drawing an unlabeled arrowed line to itAccepting states are indicated by drawing a double-line border around the stateIf T(Si,a)=Sj, then drawing an arrowed line fro

42、m the node Si to node Sj labeled by a2022/7/18112ExampleDFA M=（S，U，V，Q,a，b,f,S,Q）f（S,a）=Uf（S,b）=V f（V,a）=Uf（V,b）=Qf（U,a）=Qf（U,b）=Vf（Q,a）=Qf（Q,b）=QThe diagram of it is:bSUVQaaaba，b2022/7/18113Notes about the DiagramExtension to the definition:The transitions can also be labeled with names representin

43、g a set of characters13letterletterdigit2other2022/7/18114A ConventionError transitions are not drawn in the diagramerrorotherany13letterletterdigit2other2022/7/18115Transition table of DFATransition table is indexed by states and input characters Its values express the values of the transition func

44、tion TThe first state listed is the start stateUsing a separate column to indicate accepting stateCharacterStatebSUVQaaaba，b2022/7/18116AcceptingL(M): the language accepted by DFA ML(M) is the set of strings of characters c1c2cn with each ci such that there exist states s1=T(s0,c1),s2=T(s1,c2),Sn=T(

45、sn-1,cn) with sn is an accepting state String “baab” is accepted by DFA MbSUVQaaaba，bb2022/7/18117Example“01101” is accepted by the following DFA ?“1001” is accepted by the following DFA ?SUVZ1110002022/7/18118Example of DFA=a,b,c ,The set of strings that contain exactly one b is accepted by the fol

46、lowing DFA:The set of strings that contain at most one b is accepted by the following DFA:12ba,ca,c2ba,ca,c1Whats the difference?2022/7/181192.3.2 Definition of NFAThe need of NFAProblem of DFA when recognizing all tokens of a programIn a programming language there are many tokens, each token will b

47、e recognized by its own DFAWe should combine all the tokens into one giant DFA.2022/7/18120This is not a DFA. If there is not a systematic way it will be complex to arrange the diagram to be a DFA13letterletter,digit2other5digitdigit4other76=910subset of SS0S is a start stateA S is a set of acceptin

48、g states2022/7/181231. NFA is similar to DFA except thatExpand to include NFA may have -transition-a transition that may occur without consulting the input string-transition is used as following:12R1R2startstartConstruction for R1R2R1R2Construction for R1R2startR1R2Construction for R1R2startR1R2Cons

49、truction for R1R2startR2startR1startConstruction for R1 | R2R1R2startstartstartConstruction for R1 | R2R1R2startConstruction for R1 | R2R1R2startConstruction for R1 | R2R1R2startConstruction for R1 | R2R1R2startConstruction for R1 | R2RstartConstruction for R*RstartstartConstruction for R*Rstartstar

50、tConstruction for R*RstartConstruction for R*RstartConstruction for R*RstartConstruction for R*2022/7/181402. NFA is similar to DFA except thatExpand the definition of TMore than one transition from a state may exist for a particular character. So the value of T is a set of states rather than a sing

51、le state2022/7/18141ExampleNFA M=(S，P，Z, 0,1, f, S, Z)f (S,0) = Pf (S,1) = S，Z f (Z,0) = Pf (Z,1) = Pf (P,1) = ZDiagram of NFA SPZ00,1111The meaning of nondeterministic: The sequence of transition that accepts a particular string is not determined at each step by the state and the next input charact

52、er.2022/7/18142ExampleThe string “abb” can be accept by either of the following sequence of transitions:1234aab12424abb134242ab4b2022/7/181432.3.3 Implementation of Finite Automata in CodeRegular expressions represent a pattern, used as token descriptions DFAs represent algorithms that accept string

53、s according to a pattern described in regular expressionThe process of constructing a scanner :regular expressionprogram for scannerDFANFA?2022/7/18144Translate a Diagram of DFA into codeGeneric algorithm that will translate DFA to codeWrite the transition as a doubly nested case statement inside a

54、loopThe first case statement tests the current state The nested second level tests the input character, given the state2022/7/18145Example: DFA that accepts identifiers state:=1;startwhile state=1 or 2 docase state of1:case input character of letter: advance the input; state:=2;else state:=error or

55、other; end case2:case input character of letter, digit: advance the input; state:=2;else state:=3; end case;end case;end while;if state=3 then accept else error;13letterletterdigit2other2022/7/18146Translate a Transition Table of DFA into codeUsing transition table ,we can write code in a form that

56、will implement any DFAVariables used in code schemeTransitions are kept in a transition array “T” indexed by states and input characters;Transitions that advance the input are given by the Boolean array “Advance”, indexed also by states and input characters;Accepting states are given by the Boolean

57、array “Accept”, indexed by states2022/7/18147Code Scheme state:=1;ch:=next input character;while not Acceptstate and not error(state) donewstate:=Tstate,ch;if Advancestate,ch then ch:=next input char;state:=newstate;end while;if Acceptstate then accept;S I/*OtherAccept12No23Yes2022/7/18148The advant

58、ages of table-driven methodsThe size of code is reducedThe same code will work for many different problemsThe code is easier to change (maintain)The disadvantageThe tables can become very large, causing a significant increase in the space2022/7/181492.4 From Regular Expression to DFAsRegular express

59、ion is equivalent to DFAFrom regular expression to DFATranslate a regular expression into an NFA(2.4.1)Translate an NFA into a DFA(2.4.2)Minimizing a DFA(2.4.3)The process of constructing a scanner :regular expressionprogram for scannerDFANFA?2022/7/181502.4.1 From a Regular Expression to an NFA“Ind

60、uctive” methodIt follows the structure of the definition of a regular expression2022/7/18151Construct NFA for each basic regular expression2. NFA that is equivalent to regular expression 3. NFA that is equivalent to regular expression a,a 1. NFA that is equivalent to regular expression yxyxyxa2022/7