K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

States3 indicates that the input was new while s5 indicates that it was not. Therecognizer takes one transition per input character.We can combine the recognizer for new or not with the one for while bymerging their initial states and relabeling all the states.w ss2 3e 3n s- s0 1QoQsJwt ss4 5JJJ^Jh si sl se ss6 78910State s0 has transitions for n and w. The recognizer has three accepting states,s3 , s5 , and s10 . If any state encounters an input character that does not matchone of its transitions, the recognizer moves to an error state.2.2.1 A Formalism for RecognizersTransition diagrams serve as abstractions of the code that would be requiredto implement them. They can also be viewed as formal mathematical objects, called finite automata, that specify recognizers.

Formally, a finiteautomaton (fa) is a five-tuple (S, 6, δ, s0 , S A ), wherennS is the finite set of states in the recognizer, along with an error state se .6 is the finite alphabet used by the recognizer. Typically, 6 is the unionof the edge labels in the transition diagram.Finite automatona formalism for recognizers that has a finite set ofstates, an alphabet, a transition function, a startstate, and one or more accepting states30 CHAPTER 2 Scannersnnnδ(s, c) is the recognizer’s transition function. It maps each state s ∈ Sand each character c ∈ 6 into some next state.

In state si with inputccharacter c, the fa takes the transition si → δ(si , c).s0 ∈ S is the designated start state.S A is the set of accepting states, S A ⊆ S. Each state in S A appears as adouble circle in the transition diagram.As an example, we can cast the fa for new or not or while in the formalismas follows:S = {s0 , s1 , s2 , s3 , s4 , s5 , s6 , s7 , s8 , s9 , s10 , se }6 = {e, h, i, l, n, o, t, w}( nwes0 → s1 , s0 → s6 , s1 → s2 ,δ=this4 → s5 , s6 → s7 , s7 → s8 ,ows1 → s4 ,s2 → s3 ,s8 → s9 ,s9 → s10l)es0 = s0S A = {s3 , s5 , s10 }For all other combinations of state si and input character c, we defineδ(si , c) = se , where se is the designated error state.

This quintuple is equivalent to the transition diagram; given one, we can easily re-create the other.The transition diagram is a picture of the corresponding fa.An fa accepts a string x if and only if, starting in s0 , the sequence of characters in the string takes the fa through a series of transitions that leavesit in an accepting state when the entire string has been consumed. Thiscorresponds to our intuition for the transition diagram.

For the string new,neour example recognizer runs through the transitions s0 → s1 , s1 → s2 , andws2 → s3 . Since s3 ∈ S A , and no input remains, the fa accepts new. For theninput string nut, the behavior is different. On n, the fa takes s0 → s1 . On u,uit takes s1 → se . Once the fa enters se , it stays in se until it exhausts the inputstream.More formally, if the string x is composed of characters x1 x2 x3 .

. . xn , thenthe fa (S, 6, δ, s0 , S A ) accepts x if and only ifδ(δ(. . . δ(δ(δ(s0 , x1 ), x2 ), x3 ) . . . , xn−1 ), xn ) ∈ S A.Intuitively, this definition corresponds to a repeated application of δ to apair composed of some state s ∈ S and an input symbol xi . The base case,δ(s0 , x1 ), represents the fa’s initial transition, out of the start state, s0 , onthe character x1 . The state produced by δ(s0 , x1 ) is then used as input, alongwith x2 , to δ to produce the next state, and so on, until all the input has been2.2 Recognizing Words 31consumed.

The result of the final application of δ is, again, a state. If thatstate is an accepting state, then the fa accepts x1 x2 x3 . . . xn .Two other cases are possible. The fa might encounter an error whileprocessing the string—that is, some character x j might take it into the errorstate se . This condition indicates a lexical error; the string x1 x2 x3 . . . x j isnot a valid prefix for any word in the language accepted by the fa. Thefa can also discover an error by exhausting its input and terminating in anonaccepting state other than se . In this case, the input string is a proper prefix of some word accepted by the fa. Again, this indicates an error. Eitherkind of error should be reported to the end user.In any case, notice that the fa takes one transition for each input character.Assuming that we can implement the fa efficiently, we should expect therecognizer to run in time proportional to the length of the input string.2.2.2 Recognizing More Complex WordsThe character-by-character model shown in the original recognizer for notextends easily to handle arbitrary collections of fully specified words.

Howcould we recognize a number with such a recognizer? A specific number,such as 113.4, is easy.s01s11s234s3 ‘.’ s4s5To be useful, however, we need a transition diagram (and the corresponding code fragment) that can recognize any number. For simplicity’s sake,let’s limit the discussion to unsigned integers. In general, an integer is eitherzero, or it is a series of one or more digits where the first digit is from oneto nine, and the subsequent digits are from zero to nine. (This definitionrules out leading zeros.) How would we draw a transition diagram for thisdefinition?s21…9s00…9s30…9s40…9s50…9…0s10The transition s0 → s1 handles the case for zero.

The other path, from s0 tos2 , to s3 , and so on, handles the case for an integer greater than zero. Thispath, however, presents several problems. First, it does not end, violating thestipulation that S is finite. Second, all of the states on the path beginning withs2 are equivalent, that is, they have the same labels on their output transitionsand they are all accepting states.32 CHAPTER 2 Scannerschar ← NextChar( );state ← s0 ;S = {s0 , s1 , s2 , se }while (char 6= eof and state 6= se ) do6 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}state ← δ(state,char);char ← NextChar( );0 s0 →s1 ,end;δ=if (state ∈ SA )then report acceptance;else report failure;SA = {s1 , s2 }s 0-92 → s2 ,1-9 s0 → s2 0-9 s1 → se n FIGURE 2.2 A Recognizer for Unsigned Integers.Lexemethe actual text for a word recognized by an FAThis fa recognizes a class of strings with a common property: they are allunsigned integers.

It raises the distinction between the class of strings andthe text of any particular string. The class “unsigned integer” is a syntacticcategory, or part of speech. The text of a specific unsigned integer, such as113, is its lexeme.We can simplify the fa significantly if we allow the transition diagram tohave cycles. We can replace the entire chain of states beginning at s2 with asingle transition from s2 back to itself:1…9s0s20…90s1This cyclic transition diagram makes sense as an fa. From an implementation perspective, however, it is more complex than the acyclic transitiondiagrams shown earlier. We cannot translate this directly into a set of nestedif-then-else constructs. The introduction of a cycle in the transition graphcreates the need for cyclic control flow. We can implement this with a whileloop, as shown in Figure 2.2.

We can specify δ efficiently using a table:δ0123456789Others0s1s2ses1ses2ses2ses2ses2ses2ses2ses2ses2ses2ses2ses2ses2ses2ses2ses2ses2ses2ses2ses2seseseseseChanging the table allows the same basic code skeleton to implement otherrecognizers. Notice that this table has ample opportunity for compression.2.2 Recognizing Words 33The columns for the digits 1 through 9 are identical, so they could berepresented once. This leaves a table with three columns: 0, 1 .

. . 9, and other.Close examination of the code skeleton shows that it reports failure as soonas it enters se , so it never references that row of the table. The implementation can elide the entire row, leaving a table with just three rows and threecolumns.We can develop similar fas for signed integers, real numbers, and complexnumbers. A simplified version of the rule that governs identifier names inAlgol-like languages, such as C or Java, might be: an identifier consists ofan alphabetic character followed by zero or more alphanumeric characters.This definition allows an infinite set of identifiers, but can be specified withthe simple two-state fa shown to the left.

Many programming languagesextend the notion of “alphabetic character” to include designated specialcharacters, such as the underscore.fas can be viewed as specifications for a recognizer. However, they are notparticularly concise specifications. To simplify scanner implementation, weneed a concise notation for specifying the lexical structure of words, anda way of turning those specifications into an fa and into code that implements the fa. The remaining sections of this chapter develop precisely thoseideas.SECTION REVIEWA character-by-character approach to scanning leads to algorithmic clarity. We can represent character-by-character scanners with a transitiondiagram; that diagram, in turn, corresponds to a finite automaton. Smallsets of words are easily encoded in acyclic transition diagrams. Infinitesets, such as the set of integers or the set of identifiers in an Algol-likelanguage, require cyclic transition diagrams.Review QuestionsConstruct an FA to accept each of the following languages:1.

Характеристики

Список файлов книги