Haskell

More Information (Examples)

Lecture 6: Compilers, Languages, and Regular Expressions For Problems 5-7, give a regular expression for each description. Use ...$ to get an expression that matches a whole line of input. You don't have to find the shortest possible expression. 5. [6 points] The line consists of a natural number (0 and up), with no leading zero unless the whole thing is a single zero, and going right-to-left, groups of 3 digits are separated by commas. Examples: 0; 1; 12; 123; 1,234; 12,345; 1,000,000. Not examples: 01; 1000; 123,4; 12,34. F. Examples of Regular Expressions An identifier is a letter or underscore followed by any number of alphanumeric symbols (including underscore): [a-zA-2_][a-zA-Z0-9_]* Can't easily do: "A letter or underscore etc. except for the strings if, then, else" Not if: i followed by not f or non-i followed by anything ^i[a-eg-2](^i][a-z]$ matches all two character strings except for if An integer is a nonempty sequence of digits followed by an optional exponent. where an exponent is "e" followed by a nonempty sequence of digits [0-9]+([0-9+)? More examples Sequence of a's and b's with at least 3 a's . b*abab*a[ab]* First three a's take care of the minimum 3, the [ab]* takes care of any remaining a's Sequence of a's and b's with exactly 3 a's b*ab* ab* a matches strings with exactly 3 a's ending in a (not aaab, for example). Sequence of a's and b's with at most 3 a's. It's harder to say things like "not > 3"; we're doing it by specifying all the length 1, 2, and 3 strings b* a b* b* a b* a b* b* a b* a b* a b* A nonempty sequence of x separated by commas: x (,)* A nonempty sequence of x terminated by semicolons: (x ;) + or x ;(x;)* or x(;x)*; Can't do comparisons of arbitrary length (can only compare up to some fixed number of cases). E.g., can't do string of a's and b's with more a's than b's a, aab, aba, baa, aaab, aaba, abaa, baaa, aabb, abab, abba, baab, baba, ... But we can do string of a's and b's of length 3"; we're doing it by specifying all the length 1, 2, and 3 strings b* a b* b* a b* a b* b* a b* a b* a b* A nonempty sequence of x separated by commas: x (,)* A nonempty sequence of x terminated by semicolons: (x ;) + or x ;(x;)* or x(;x)*; Can't do comparisons of arbitrary length (can only compare up to some fixed number of cases). E.g., can't do string of a's and b's with more a's than b's a, aab, aba, baa, aaab, aaba, abaa, baaa, aabb, abab, abba, baab, baba, ... But we can do string of a's and b's of length