【正文】 elements of K’, Qi∈ K。Z is leaving state which belongs to nonempty set, Z K。 VT is a set of input symbols。 M is a transition function that is statesymbol pairs K VT, M (W , a)=U. While W is the present state, when W accepts an input symbol “a”, W will move to next state U . . ? If it has a unique and definite next state when it moves form one state to others, the FA is called definite finite automata—DFA. 204。 S is start state, S∈ K。 15 ? Example Grammar G［ Z］： Z::=Za|Aa|Bb A::=Ba|a B::=Ab|b What we want to do is that to construct a state diagram from this grammar and judge if string “ababaaa” belongs to the language. are the procedure of generating the state diagram of example from begin to end. . 16 ? From the start state of S, we input the charaters “ababaaa” one by one, at last reach the end state Z. So string “ababaaa” is the sentence of the grammar . 17 Finite Automata ? The aim we study the language and grammar is to create a lexical analyzer. Actually, we first know a language, grammar, and then we can construct transition diagram from it. This section we go on forming automata from the transition diagram, and then design a program to realize the automata, namely, lexical analyzer. . 18 ? Deterministic Finite Automata— DFA ? The finite automata is a mathematical model of state transition, it can be described by five elements. (K , VT , M , S , Z) ? While K is a set of states。 ? After the process of lexical analyzer, the tokens of it are shown by Table . 7 Role of buffer in lexical analyzing ? Lexical analyzer needs buffer all the times when source program is piled, because lexical analyzer should look ahead for several characters to judge if they are in same token. In addition, a great deal of time is spent in locating the characters. Buffering techniques can reduce the amount of time when scanning input characters, here we only outline one of them. . ? The buffer we use is divided into two halves so that each half includes Ncharacters. When scanning, we should judge pointer “forward” if it reaches the end of the first half buffer, if yes, we should load the other half . . 8 ? Example There is a sentence in source program: Index := 2 * count +17。 they are identifiers, constants, operators, keywords and punctuation symbols (parentheses, mas and semicolons) . . Type 1: Keywords. They are the word of mand definition, such as “IF”, “FOR” . Type 2: Identifiers. They are the name of variable, procedure, function and so on, such as : “index”, “count”. Type 3: Constants. such as “65”, “－ ”,“” Type 4: Operators. For example, “+”, “＊ ” and “” are all operators. Type 5: Punctuation symbol. They are the symbols, such as “,” , “:” , “ 。Chapter 3 Lexical analyzer Zhang Jing, Yu SiLiang College of Computer Science amp。 Technology Harbin Engineering University 2 ? This chapter deals with the techniques of lexical analyzer. That is, how to build a lexical analyzer? How to construct a symbol table which includes the tokens ing from the source language? Then, how to produce lexical analyzer efficiently ? ? 3 Role of lexical analyzer ? The role of lexical analyzer is that it can recognize words—tokens from source program. The input of lexical analyzer is source program, the output of it are tokens. If we want to do lexical analyzer, we should firstly identify tokens and remove white space, enter, note and