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

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. A six-character identifier consisting of an alphabetic character followed by zero to five alphanumeric characters2. A string of one or more pairs, where each pair consists of an openparenthesis followed by a close parenthesis3. A Pascal comment, which consists of an open brace, {, followed byzero or more characters drawn from an alphabet, 6, followed by aclose brace, }s0a…z,A…Zs1a…z,A…Z,0…934 CHAPTER 2 Scanners2.3 REGULAR EXPRESSIONSThe set of words accepted by a finite automaton, F , forms a language,denoted L(F ).

The transition diagram of the fa specifies, in precise detail,that language. It is not, however, a specification that humans find intuitive.For any fa, we can also describe its language using a notation called a regular expression (re). The language described by an re is called a regularlanguage.Regular expressions are equivalent to the fas described in the previoussection.

(We will prove this with a construction in Section 2.4.) Simplerecognizers have simple re specifications.nnnThe language consisting of the single word new can be described by anre written as new. Writing two characters next to each other implies thatthey are expected to appear in that order.The language consisting of the two words new or while can be writtenas new or while. To avoid possible misinterpretation of or, we writethis using the symbol | to mean or. Thus, we write the re asnew | while.The language consisting of new or not can be written as new | not.Other res are possible, such as n(ew | ot).

Both res specify the samepair of words. The re n(ew | ot) suggests the structure of the fa that wedrew earlier for these two words.w ss2 3e3n s- s0 1QoQst ss4 5To make this discussion concrete, consider some examples that occur in mostprogramming languages. Punctuation marks, such as colons, semicolons,commas, and various brackets, can be represented by their character representations. Their res have the same “spelling” as the punctuation marksthemselves. Thus, the following res might occur in the lexical specificationfor a programming language:: ; ? => ( ) { } [ ]Similarly, keywords have simple res.if while this integer instanceofTo model more complex constructs, such as integers or identifiers, we needa notation that can capture the essence of the cyclic edge in an fa.2.3 Regular Expressions 35The fa for an unsigned integer, shown at the left, has three states: an initialstate s0 , an accepting state s1 for the unique integer zero, and another accepting state s2 for all other integers.

The key to this fa’s power is the transitionfrom s2 back to itself that occurs on each additional digit. State s2 folds thespecification back on itself, creating a rule to derive a new unsigned integerfrom an existing one: add another digit to the right end of the existing number. Another way of stating this rule is: an unsigned integer is either a zero,or a nonzero digit followed by zero or more digits.

To capture the essenceof this fa, we need a notation for this notion of “zero or more occurrences”of an re. For the re x, we write this as x∗ , with the meaning “zero or moreoccurrences of x.” We call the * operator Kleene closure, or closure for short.Using the closure operator, we can write an re for this fa:0…91…9s0s20s10 | (1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9) (0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)∗ .2.3.1 Formalizing the NotationTo work with regular expressions in a rigorous way, we must define themmore formally.