A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition), страница 9

The symbol | indicates theinput position at each successive call to the lexical analyzer, the symbol ⊥ indicates thecurrent position of the automaton, and ⊺ indicates the most recent position in which therecognizer was in a final state.2.4 NONDETERMINISTIC FINITE AUTOMATAA nondeterministic finite automaton (NFA) is one that has a choice of edges - labeled with thesame symbol - to follow out of a state. Or it may have special edges labeled with ∊ (the Greekletter epsilon) that can be followed without eating any symbol from the input.Here is an example of an NFA:30In the start state, on input character a, the automaton can move either right or left.

If left ischosen, then strings of a's whose length is a multiple of three will be accepted. If right ischosen, then even-length strings will be accepted. Thus, the language recognized by this NFAis the set of all strings of a's whose length is a multiple of two or three.On the first transition, this machine must choose which way to go.

It is required to accept thestring if there is any choice of paths that will lead to acceptance. Thus, it must "guess", andmust always guess correctly.Edges labeled with ∊ may be taken without using up a symbol from the input. Here is anotherNFA that accepts the same language:Again, the machine must choose which ∊-edge to take. If there is a state with some ∊-edgesand some edges labeled by symbols, the machine can choose to eat an input symbol (andfollow the corresponding symbol-labeled edge), or to follow an ∊-edge instead.CONVERTING A REGULAR EXPRESSION TO AN NFANondeterministic automata are a useful notion because it is easy to convert a (static,declarative) regular expression to a (simulatable, quasi-executable) NFA.The conversion algorithm turns each regular expression into an NFA with a tail (start edge)and a head (ending state).

For example, the single-symbol regular expression a converts to theNFAThe regular expression ab, made by combining a with b using concatenation, is made bycombining the two NFAs, hooking the head of a to the tail of b. The resulting machine has atail labeled by a and a head into which the b edge flows.31In general, any regular expression M will have some NFA with a tail and head:We can define the translation of regular expressions to NFAs by induction. Either anexpression is primitive (a single symbol or ∊) or it is made from smaller expressions.Similarly, the NFA will be primitive or made from smaller NFAs.Figure 2.6 shows the rules for translating regular expressions to nondeterministic automata.We illustrate the algorithm on some of the expressions in Figure 2.2 - for the tokens IF, ID,NUM, and error.

Each expression is translated to an NFA, the "head" state of each NFA ismarked final with a different token type, and the tails of all the expressions are joined to anew start node. The result - after some merging of equivalent NFA states - is shown in Figure2.7.Figure 2.6: Translation of regular expressions to NFAs.32Figure 2.7: Four regular expressions translated to an NFA.CONVERTING AN NFA TO A DFAAs we saw in Section 2.3, implementing deterministic finite automata (DFAs) as computerprograms is easy. But implementing NFAs is a bit harder, since most computers don't havegood "guessing" hardware.We can avoid the need to guess by trying every possibility at once.

Let us simulate the NFAof Figure 2.7 on the string in. We start in state 1. Now, instead of guessing which ∊-transitionto take, we just say that at this point the NFA might take any of them, so it is in one of thestates {1, 4, 9, 14}; that is, we compute the ∊-closure of {1}. Clearly, there are no other statesreachable without eating the first character of the input.Now, we make the transition on the character i. From state 1 we can reach 2, from 4 we reach5, from 9 we go nowhere, and from 14 we reach 15. So we have the set f2, 5, 15g.

But againwe must compute the ∊-closure: From 5 there is an ∊-transition to 8, and from 8 to 6. So theNFA must be in one of the states {2, 5, 6, 8, 15}.On the character n, we get from state 6 to 7, from 2 to nowhere, from 5 to nowhere, from 8 tonowhere, and from 15 to nowhere. So we have the set {7}; its ∊-closure is {6, 7, 8}.Now we are at the end of the string in; is the NFA in a final state? One of the states in ourpossible-states set is 8, which is final. Thus, in is an ID token.We formally define ∊-closure as follows.

Let edge(s, c) be the set of all NFA states reachableby following a single edge with label c from state s.For a set of states S, closure(S) is the set of states that can be reached from a state in S withoutconsuming any of the input, that is, by going only through ∊-edges. Mathematically, we canexpress the idea of going through ∊-edges by saying that closure(S) is the smallest set T suchthatWe can calculate T by iteration:33Why does this algorithm work? T can only grow in each iteration, so the final T must includeS. If T = T′ after an iteration step, then T must also include. Finally, thealgorithm must terminate, because there are only a finite number of distinct states in the NFA.Now, when simulating an NFA as described above, suppose we are in a set d = {si; sk; sl} ofNFA states si ; sk; sl. By starting in d and eating the input symbol c, we reach a new set ofNFA states; we'll call this set DFAedge(d; c):Using DFAedge, we can write the NFA simulation algorithm more formally.

If the start stateof the NFA is s1, and the input string is c1,…, ck, then the algorithm isManipulating sets of states is expensive - too costly to want to do on every character in thesource program that is being lexically analyzed. But it is possible to do all the sets-of-statescalculations in advance. We make a DFA from the NFA, such that each set of NFA statescorresponds to one DFA state.

Since the NFA has a finite number n of states, the DFA willalso have a finite number (at most 2n) of states.DFA construction is easy once we have closure and DFAedge algorithms. The DFA startstate d1 is just closure(s1), as in the NFA simulation algorithm. Abstractly, there is an edgefrom di to dj labeled with c if dj = DFAedge(di, c). We let Σ be the alphabet.The algorithm does not visit unreachable states of the DFA. This is extremely important,because in principle the DFA has 2n states, but in practice we usually find that only about n ofthem are reachable from the start state.

It is important to avoid an exponential blowup in thesize of the DFA interpreter's transition tables, which will form part of the working compiler.A state d is final in the DFA if any NFA state in states[d] is final in the NFA. Labeling a statefinal is not enough; we must also say what token is recognized; and perhaps several membersof states[d] are final in the NFA. In this case we label d with the token-type that occurred firstin the list of regular expressions that constitute the lexical specification. This is how rulepriority is implemented.34After the DFA is constructed, the "states" array may be discarded, and the "trans" array isused for lexical analysis.Applying the DFA construction algorithm to the NFA of Figure 2.7 gives the automaton inFigure 2.8.Figure 2.8: NFA converted to DFA.This automaton is suboptimal.

That is, it is not the smallest one that recognizes the samelanguage. In general, we say that two states s1 and s2 are equivalent when the machine startingin s1 accepts a string σ if and only if starting in s2 it accepts σ. This is certainly true of thestates labeled 5, 6, 8, 15 and 6, 7, 8 in Figure 2.8, and of the states labeled 10, 11, 13, 15 and11, 12, 13.

In an automaton with two equivalent states s1 and s2, we can make all of s2'sincoming edges point to s1 instead and delete s2.How can we find equivalent states? Certainly, s1 and s2 are equivalent if they are both final orboth nonfinal and, for any symbol c, trans[s1, c] = trans[s2, c]; 10, 11, 13, 15 and 11, 12, 13satisfy this criterion. But this condition is not sufficiently general; consider the automatonHere, states 2 and 4 are equivalent, but trans[2, a] ≠ trans[4, a].After constructing a DFA it is useful to apply an algorithm to minimize it by findingequivalent states; see Exercise 2.6.2.5 LEXICAL-ANALYZER GENERATORSDFA construction is a mechanical task easily performed by computer, so it makes sense tohave an automatic lexical-analyzer generator to translate regular expressions into a DFA.35JavaCC and SableCC generate lexical analyzers and parsers written in Java.

The lexicalanalyzers are generated from lexical specifications; and, as explained in the next chapter, theparsers are generated from grammars.For both JavaCC and SableCC, the lexical specification and the grammar are contained in thesame file.JAVACCThe tokens described in Figure 2.2 are specified in JavaCC as shown in Program 2.9.

AJavaCC specification starts with an optional list of options followed by a Java compilationunit enclosed between PARSER_BEGIN(name) and PARSER_END(name). The same name mustfollow PARSER_BEGIN and PARSER_END; it will be the name of the generated parser (MyParserin Program 2.9). The enclosed compilation unit must contain a class declaration of the samename as the generated parser.PROGRAM 2.9: JavaCC specification of the tokens from Figure 2.2.PARSER_BEGIN(MyParser)class MyParser {}PARSER_END(MyParser)/* For the regular expressions on the right, the token on the left will bereturned:/*TOKEN : {< IF: "if" >| < #DIGIT: ["0"-"9"] >| < ID: ["a"-"z"] (["a"-"z"]|<DIGIT>) >| < NUM: (<DIGIT>)+ >| < REAL: ( (<DIGIT>)+ "." (<DIGIT>)* ) |( (<DIGIT>)* "." (<DIGIT>)+ )>}/* The regular expressions here will be skipped during lexical analysis: */SKIP : {<"--" (["a"-"z"])* ("\n" | "\r" | "\r\n")>|""| "\t"| "\n"}/* If we have a substring that does not match any of the regularexpressions in TOKEN or SKIP,JavaCC will automatically throw an error.

*/void Start() :{}{ ( <IF> | <ID> | <NUM> | <REAL> )* }Next is a list of grammar productions of the following kinds: a regular-expression productiondefines a token, a token-manager declaration can be used by the generated lexical analyzer,and two other kinds are used to define the grammar from which the parser is generated.A lexical specification uses regular-expression productions; there are four kinds: TOKEN, SKIP,MORE, and SPECIAL_TOKEN. We will only need TOKEN and SKIP for the compiler project in thisbook.

The kind TOKEN is used to specify that the matched string should be transformed into atoken that should be communicated to the parser. The kind SKIP is used to specify that thematched string should be thrown away.36In Program 2.9, the specifications of ID, NUM, and REAL use the abbreviation DIGIT.