Cooper_Engineering_a_Compiler(Second Edition) (Rice), страница 22

In most languages, the scanner’s overshoot will be limited. Pathological behavior, however, can cause the scannerto examine individual characters many times, significantly increasing theoverall cost of scanning. In most programming languages, the amount ofroll back is small relative to the word lengths. In languages where significant amounts of roll back can occur, a more sophisticated approach to thisproblem is warranted.2.5 Implementing Scanners 63Avoiding Excess Roll BackSome regular expressions can produce quadratic calls to roll back in thescanner shown in Figure 2.14. The problem arises from our desire to havethe scanner return the longest word that is a prefix of the input stream.Consider the re ab | (ab)∗ c. The corresponding dfa, shown in the margin,recognizes either ab or any number of occurrences of ab followed by afinal c.

On the input string ababababc, a scanner built from the dfa will readall the characters and return the entire string as a single word. If, however, theinput is abababab, it must scan all of the characters before it can determinethat the longest prefix is ab. On the next invocation, it will scan abababto return ab. The third call will scan abab to return ab, and the final callwill simply return ab without any roll back. In the worst, case, it can spendquadratic time reading the input stream.Figure 2.15 shows a modification to the scanner in Figure 2.14 that avoidsthis problem.

It differs from the earlier scanner in three important ways.First, it has a global counter, InputPos, to record position in the inputstream. Second, it has a bit-array, Failed, to record dead-end transitionsas the scanner finds them. Failed has a row for each state and a column foreach position in the input stream. Third, it has an initialization routine thatNextWord()state ← s0 ;lexeme ← ‘‘ ’’;clear stack;push(hbad, badi);while (state 6= se ) doNextChar(char);InputPos ← InputPos + 1;lexeme ← lexeme + char;hstate,InputPosi ← pop();truncate lexeme;RollBack();end;if state ∈ SAthen return TokenType[state];else return bad;then break;push(hstate,InputPosi);cat ← CharCat[char];state ← δ[state,cat];end;n FIGURE 2.15 The Maximal Munch Scanner.s0a?InitializeScanner()InputPos = 0;for each state s in the DFA dofor i = 0 to |input stream| doFailed[s,i] ← false;end;end;s1b?as3 s2ab c6??cs4s5while(state ∈/ SA and state 6= bad ) doFailed[state,InputPos] ← true;if Failed[state,InputPos]if state ∈ SAthen clear stack;?64 CHAPTER 2 Scannersmust be called before NextWord() is invoked.

That routine sets InputPosto zero and sets Failed uniformly to false.This scanner, called the maximal munch scanner, avoids the pathologicalbehavior by marking dead-end transitions as they are popped from the stack.Thus, over time, it records specific hstate,input positioni pairs that cannotlead to an accepting state. Inside the scanning loop, the first while loop, thecode tests each hstate,input positioni pair and breaks out of the scanning loopwhenever a failed transition is attempted.Optimizations can drastically reduce the space requirements of this scheme.(See, for example, Exercise 16 on page 82.) Most programming languageshave simple enough microsyntax that this kind of quadratic roll back cannotoccur.

If, however, you are building a scanner for a language that can exhibitthis behavior, the scanner can avoid it for a small additional overhead percharacter.Generating the Transition and Classifier TablesGiven a dfa, the scanner generator can generate the tables in a straightforward fashion. The initial table has one column for every character in theinput alphabet and one row for each state in the dfa. For each state, in order,the generator examines the outbound transitions and fills the row with theappropriate states. The generator can collapse identical columns into a singleinstance; as it does so, it can construct the character classifier.

(Two characters belong in the same class if and only if they have identical columnsin δ.) If the dfa has been minimized, no two rows can be identical, so rowcompression is not an issue.Changing LanguagesTo model another dfa, the compiler writer can simply supply new tables.Earlier in the chapter, we worked with a second, more constrained specification for iloc register names, given by the re: r( [0. . . 2] ([0. . . 9] | ) |[4. . .

9] | (3 (0 | 1 | )) ). That re gave rise to the following dfa:s20…2s0rs14…93s50…90,1s3s6s4Because it has more states and transitions than the re for r [0. . . 9]+ , weshould expect a larger transition table.2.5 Implementing Scanners 65s0s1s2s3s4s5s6ser0,1234 ... 9Others1seseseseseseseses2s3seses6seseses2s3seseseseseses5s3seseseseseses4s3seseseseseseseseseseseseseAs a final example, the minimal dfa for the re a (b|c)∗ has the followingtable:b,cs0as1s0s1Minimal DFAab,cOthers1seses1seseTransition TableThe character classifier has three classes: a, b or c, and all other characters.2.5.2 Direct-Coded ScannersTo improve the performance of a table-driven scanner, we must reduce thecost of one or both of its basic actions: read a character and compute thenext dfa transition. Direct-coded scanners reduce the cost of computingdfa transitions by replacing the explicit representation of the dfa’s stateand transition graph with an implicit one. The implicit representation simplifies the two-step, table-lookup computation.

It eliminates the memoryreferences entailed in that computation and allows other specializations. Theresulting scanner has the same functionality as the table-driven scanner, butwith a lower overhead per character. A direct-coded scanner is no harder togenerate than the equivalent table-driven scanner.The table-driven scanner spends most of its time inside the central whileloop; thus, the heart of a direct-coded scanner is an alternate implementation of that while loop. With some detail abstracted, that loop performs thefollowing actions:while (state 6= se ) doNextChar(char);cat ← CharCat[char];state ← δ [state,cat];end;66 CHAPTER 2 ScannersREPRESENTING STRINGSThe scanner classifies words in the input program into a small set ofcategories. From a functional perspective, each word in the input streambecomes a pair hword,typei, where word is the actual text that forms theword and type represents its syntactic category.For many categories, having both word and type is redundant.

Thewords +, ×, and for have only one spelling. For identifiers, numbers,and character strings, however, the compiler will repeatedly use theword. Unfortunately, many compilers are written in languages that lackan appropriate representation for the word part of the pair. We needa representation that is compact and offers a fast equality test for twowords.A common practice to address this problem has the scanner create a single hash table (see Appendix B.4) to hold all the distinct strings used inthe input program.

The compiler then uses either the string’s index in this"string table" or a pointer to its stored image in the string table as a proxyfor the string. Information derived from the string, such as the length ofa character constant or the value and type of a numerical constant, canbe computed once and referenced quickly through the table. Since mostcomputers have storage-efficient representations for integers and pointers, this reduces the amount of memory used internally in the compiler.By using the hardware comparison mechanisms on the integer or pointerproxies, it also simplifies the code used to compare them.Notice the variable state that explicitly represents the dfa’s current stateand the tables CharCat and δ that represent the dfa’s transition diagram.Overhead of Table LookupFor each character, the table-driven scanner performs two table lookups,one in CharCat and another in δ.

While both lookups take O(1) time, thetable abstraction imposes constant-cost overheads that a direct-coded scanner can avoid. To access the ith element of CharCat, the code must computeits address, given by@CharCat0 + i × wDetailed discussion of code for array addressingstarts on page 359 in Section 7.5.where @CharCat0 is a constant related to the starting address of CharCatin memory and w is the number of bytes in each element of CharCat. Aftercomputing the address, the code must load the data found at that address inmemory.2.5 Implementing Scanners 67Because δ has two dimensions, the address calculation is more complex.