CSC362 2011F, Class 07: Regular Expressions
Overview:
* Lexing Example, Continued.
* Regular Expressons.
* Simplifying Regular Expressions.
* Common Shorthands.
* Sample Regular Expressions.
* Limitations.
* Using Regular Expressions for Describing Tokens.
* Lab. (Hah! Do it on your own if you think it would be helpful)
Admin:
* Reading for Monday: Aho et al., 3.6.
* HW 2 assigned: Tokens for Pascal.
* Today's lexing code should be in Examples/LA.
* EC for Robotics talk next Thursday.
* Assignment 1 returned.
* In order to receive your given grade, you must write a one- or two-paragraph summary of my comments. (No summary => 0)
* If you got an F on the assignment because you turned in non-compiling or non-working code, you may redo it for potential regrading (cap of C).
Lexical Analysis
* Go until 1:40.
* Recall
Policy: "Ignore whitespace between things"
Comments: /* ... */
Words: Sequences of letters
Integers: Sequences of digits
+: Plus
*: Star
-: Dash
/: Slsh
* What do we have left to do?
* Comments
* Things that require more than one character
* Words
* Integers
Regular Expressions
* Notation(s) for describing sets of strings over an alphabet, Sigma
CONCEPT PRECISE NOTATION USUAL LANGUAGE
empty string epsilon L[epsilon] = { "" }
1 character s in Sigma s L[s] = { "s" }
Concatenation (RS) RS L[(RS) =
{ concat(r,s) s.t.
` r = L[R] and s in L[S] }
Alternation (R|S) R|S L[(R|S)] = L[R] union L[S]
Kleene Star (R*) R* { "" } union
(R(R*))
Concatentation of 0 or more strings from R