【正文】 [ left bracket index identifier ] right bracket = assignment 4 number + plus sign 2 number Tokens (cont) ? The tokens fall into three categories 1. Reserved words: if , then, etc. 2. Special symbols: +, , 。 Token Attributes ? The string of characters represented by a token is called its string value or its lexeme. – Token must be distinguished from the string of characters it represent. ? Some tokens have one lexeme – Reserved words and special characters ? Potentially, a token can represent infinitely many lexemes. – ID token represents all identifiers. ? Any value associated with a token is called an attribute. – Lexeme, numerical value for a NUM token. Token Record ? Token attributes are collected into a single structured data type. typedef struct { TokenType tokenval。 int numval。 Regular Expressions ? Regular expressions represent patterns. ? A set of strings that matches a regular expression r is called the language generated by r and written as L(r). ? The set of characters or symbols that are available is called the alphabet. – The alphabet is denoted by Σ. ? A regular expression contains symbols of Σ, but they indicate a pattern. – Pattern will be written in boldface ? A regular expression may contain metacharacters or metasymbols Basic Regular Expressions ? These are just the single characters from the alphabet, which match themselves. ? r = a, L(a)={a} ? ε denotes an empty string: L(ε)= {ε} ? Φ matches no string: L(Φ ) = { }. Token Function ? The scanner returns the next token from the input on demand via a function TokenType getToken( )。 = delimits two indentifiers – Blanks, tabs, and new line are delimiters. ? Delimiters end the token string, but they may be part of the next token string. ? Delimiter is not removed from the rest of the input. – By returning it to the input (backing up). – By looking ahead before removing the delimiter. Ambiguity ? Some strings can be matched by several different regular expressions. – if and while could be either keywords or identifiers ? Language definition must give disambiguating rules. – Keyword interpretation is preferred. – Principle of longest substring. Finite Automata ? Finite automata, or finitestate machines, are a mathematical way of describing particular kinds of algorithms. ? Finite automata can be used to recognize patterns. ? There is a strong relationship between finite automata and regular expressions. ? ( regular expression FA) Example ? identifier = letter(letter|digit)* ? Circles represent states. ? The arrowed lines represent transitions upon a match of the labeled characters. ? Start state is indicated by unlabeled arrow ? Accepting states are indicated by doubleline border. 1 2 letter letter digit Deterministic Final Automata ? A DFA M consists of – An alphabet Σ – A set of states S – A transition function T: (S x Σ) S – A start state s0 S – A set of accepting states A S ? The language accepted by M, written L(M), is the set of strings of characters c1c2…c n with each ci Σ such that there exist states s1=T(s0,c1), s2=T(s1,c2), …. sn=T(sn1,) with sn an element of A. ? ? ?Error Transitions 1 2 letter digit Error other other letter By convention, the error transitions are not drawn in the diagram, but assumed to always exist. other = ~letter other = ~(letter|digit) Example ? The set of strings that contain exactly one b is accepted by the following DFA: ? ? (~a)*b(~a)* (Regular expression ) ? We will omit labels when it is not necessary to refer to the states by name. b no