【正文】 a, aa, aaa, aaaa, … ? L(r*) = L(r)* ? Example: L((a|bc)*) = L(a|bc)* = {a, bb}* ={ε, a, bb, aa, abb, bbbb, aaa, aabb, abba, abbbb, bbabb, bbbba, bbbbbb,…} Precedence of Operations ? Repetition ? Concatenation ? Alternative ? Example: a|cb* is interpreted as a|(c(b*)) ? Parentheses are used to indicate the precedence as usual. Highest Lowest Names for Regular Expressions ? Often,it is helpful to use regular definitions of names. ? Example: digit=0|1|2…|9 ? The name bees a metasymbol and should be distinguished from the string (digit in the example). ? We can use names in regular expressions like digit digit* Example ? Σ = {a, b, c} ? Find a regular expression for the strings of Σ that contain exactly one b. ? (a|c)*b(a|c)* ? b does not have to be a center of a matched string. Example ? Σ = {a, b, c} ? Find a regular expression for the strings of Σ that contain at most one b. ? We can use a solution to the previous example and add another case matching the strings with no b. (a|c)*|(a|c)*b(a|c)* A|B A: no b B : Just only one b ? Another solution: (a|c)*(b|ε)(a|c)* (Its structure is similar to ) Example ? Σ = {a, b} ? Consider a set of strings consisting of a single b surrounded by the same number of a?s. S = {b, aba, aabaa, aaabaaa, …} ? Regular expression a*ba* does not work. ? This set of strings cannot be described by a regular expression. ? This can be proved using a famous theorem called the pumping lemma. Example ? Σ = {a, b, c} ? Determine a description of a language generated by ((b|c)*a(b|c)*a)*(b|c) ? This generates the language if strings containing an even number of a?s. ? ( Pay more attention to a special element ) Extensions to Regular Expressions One or more repetitions r r* = r+ Any character . Alternatives [09] [abc] Any character not in a given set ~(a|b|c) [^abc] Optional subexpression ? natural = [09] signedNatural = (+|)? Natural Extension Regular Expressions for Numbers nat = [09]+ signedNat = (+|)? nat number = signedNat (“.” nat)?(E signedNat)? ? “ “ are escape characters. They turn off the special meaning of metacharacters Comments ? Comments are ignored during scanning process. ? A scanner must recognize ments and discard them. ? There may be no explicit token for ments – pseudotoken. ? {Pascal ment} {(~})*} ? Ada ment (~newline)* Reserved Words and Identifiers reserved = if | while | do | … letter = [azAz] digit = [09] identifier = letter(letter|digit)* Token Delimiters ? Token delimiters are characters that imply that a longer string cannot represent a token. – xtemp=ytemp。 } TokenRecord。 char * stringval。, etc. 3. Numbers and identifiers: , myName, myGrade, etc. 4. Literals: “Hello, world!”, ?a?, ?b?, etc. ? Tokens are usually defined as an enumerated type typedef enum {IF, THEN, ELSE, PLUS, MINUS, NUM, ID,…} TokenType。Chapter 2 Scanning Instructor Jianhui Yue Software College SCU Introduction ? The scanning, or lexical analysis phase, reads the source program as a stream of characters and divides them into tokens. ? This is a special case of pattern matching – Need to study methods of pattern specification and recognition ? Regular expressions ? Finite automata ? The scanner must operate as efficiently as possible. Introduction (cont ) Scanner Parser Semantic Analyzer Source Code Optimizer Code Generator Target Code Optimizer Source Code Target Code Tokens Syntax Tree Intermediate code Target Code Literal Table Symbol Table Error Handler Tokens ? Logical units that the scanner generates. ? Example: a[index] = 4 + 2。 a identifier