Chapter 6
Lexer

6.1 Regular expression syntax

The lexer is based on the re1 module. TPG profits from the power of Python regular expressions. This document assumes the reader is familiar with regular expressions.

You can use the syntax of regular expressions as expected by the re module except from the grouping by name syntax since it is used by TPG to decide which token is recognized.

Here is a summary2 of the regular expression syntax:

”.”
(Dot.) In the default mode, this matches any character except a newline. If the DOTALL flag has been specified, this matches any character including a newline.
ˆ
(Caret.) Matches the start of the string, and in MULTILINE mode also matches immediately after each newline.
”$”
Matches the end of the string or just before the newline at the end of the string, and in MULTILINE mode also matches before a newline. foo matches both ’foo’ and ’foobar’, while the regular expression foo$ matches only ’foo’. More interestingly, searching for foo.$ in ’foo1\nfoo2\n’ matches ’foo2’ normally, but ’foo1’ in MULTILINE mode.
”*”
Causes the resulting RE to match 0 or more repetitions of the preceding RE, as many repetitions as are possible. ab* will match ’a’, ’ab’, or ’a’ followed by any number of ’b’s.
”+”
Causes the resulting RE to match 1 or more repetitions of the preceding RE. ab+ will match ’a’ followed by any non-zero number of ’b’s; it will not match just ’a’.
”?”
Causes the resulting RE to match 0 or 1 repetitions of the preceding RE. ab? will match either ’a’ or ’ab’.
*?, +?, ??
The ”*”, ”+”, and ”?” qualifiers are all greedy; they match as much text as possible. Sometimes this behaviour isn’t desired; if the RE < .* > is matched against ’<H1>title</H1>’, it will match the entire string, and not just ’<H1>’. Adding ”?” after the qualifier makes it perform the match in non-greedy or minimal fashion; as few characters as possible will be matched. Using .*? in the previous expression will match only ’<H1>’.
{m}
Specifies that exactly m copies of the previous RE should be matched; fewer matches cause the entire RE not to match. For example, a{6} will match exactly six ”a” characters, but not five.
{m,n}
Causes the resulting RE to match from m to n repetitions of the preceding RE, attempting to match as many repetitions as possible. For example, a{3,5} will match from 3 to 5 ”a” characters. Omitting m specifies a lower bound of zero, and omitting n specifies an infinite upper bound. As an example, a{4,}b will match aaaab or a thousand ”a” characters followed by a b, but not aaab. The comma may not be omitted or the modifier would be confused with the previously described form.
{m,n}?
Causes the resulting RE to match from m to n repetitions of the preceding RE, attempting to match as few repetitions as possible. This is the non-greedy version of the previous qualifier. For example, on the 6-character string ’aaaaaa’, a{3,5} will match 5 ”a” characters, while a{3,5}? will only match 3 characters.
\
Either escapes special characters (permitting you to match characters like ”*”, ”?”, and so forth), or signals a special sequence; special sequences are discussed below.
[]
Used to indicate a set of characters. Characters can be listed individually, or a range of characters can be indicated by giving two characters and separating them by a ”-”. Special characters are not active inside sets. For example, [akm$] will match any of the characters ”a”, ”k”, ”m”, or ”$”; [a - z] will match any lowercase letter, and [a - zA - Z0 - 9] matches any letter or digit. Character classes such as \w or \S (defined below) are also acceptable inside a range. If you want to include a ”]” or a ”-” inside a set, precede it with a backslash, or place it as the first character. The pattern []] will match ’]’, for example.

You can match the characters not within a range by complementing the set. This is indicated by including a ”ˆ ” as the first character of the set; ”ˆ ” elsewhere will simply match the ”ˆ ” character. For example, [ˆ 5] will match any character except ”5”, and [ˆ ˆ ] will match any character except ”ˆ ”.

AB, where A and B can be arbitrary REs, creates a regular expression that will match either A or B. An arbitrary number of REs can be separated by the ”” in this way. This can be used inside groups (see below) as well. As the target string is scanned, REs separated by ”” are tried from left to right. When one pattern completely matches, that branch is accepted. This means that once A matches, B will not be tested further, even if it would produce a longer overall match. In other words, the ”” operator is never greedy. To match a literal ””, use \∣, or enclose it inside a character class, as in [].
(...)
Matches whatever regular expression is inside the parentheses, and indicates the start and end of a group; the contents of a group can be retrieved after a match has been performed, and can be matched later in the string with the \number special sequence, described below. To match the literals ”(” or ”)”, use \( or \), or enclose them inside a character class: [(] [)].
(?=...)
Matches if ... matches next, but doesn’t consume any of the string. This is called a lookahead assertion. For example, Isaac(? = Asimov) will match ’Isaac ’ only if it’s followed by ’Asimov’.
(?!...)
Matches if ... doesn’t match next. This is a negative lookahead assertion. For example, Isaac(?!Asimov) will match ’Isaac ’ only if it’s not followed by ’Asimov’.
(?<=...)
Matches if the current position in the string is preceded by a match for ... that ends at the current position. This is called a positive lookbehind assertion. (? <= abc)def will find a match in ”abcdef”, since the lookbehind will back up 3 characters and check if the contained pattern matches. The contained pattern must only match strings of some fixed length, meaning that abc or ab are allowed, but a* and a{3,4} are not.
(?<!...)
Matches if the current position in the string is not preceded by a match for .... This is called a negative lookbehind assertion. Similar to positive lookbehind assertions, the contained pattern must only match strings of some fixed length. Patterns which start with negative lookbehind assertions may match at the beginning of the string being searched.
\A
Matches only at the start of the string.
\b
Matches the empty string, but only at the beginning or end of a word. A word is defined as a sequence of alphanumeric or underscore characters, so the end of a word is indicated by whitespace or a non-alphanumeric, non-underscore character. Note that \b is defined as the boundary between \w and \W, so the precise set of characters deemed to be alphanumeric depends on the values of the UNICODE and LOCALE flags. Inside a character range, \b represents the backspace character, for compatibility with Python’s string literals.
\B
Matches the empty string, but only when it is not at the beginning or end of a word. This is just the opposite of \b, so is also subject to the settings of LOCALE and UNICODE.
\d
Matches any decimal digit; this is equivalent to the set [0 - 9].
\D
Matches any non-digit character; this is equivalent to the set [ˆ 0 - 9].
\s
Matches any whitespace character; this is equivalent to the set [ \t\n\r\f\v].
\S
Matches any non-whitespace character; this is equivalent to the set [ˆ  \t\n\r\f\v].
\w
When the LOCALE and UNICODE flags are not specified, matches any alphanumeric character and the underscore; this is equivalent to the set [a-zA-Z0-9_]. With LOCALE, it will match the set [0 - 9_] plus whatever characters are defined as alphanumeric for the current locale. If UNICODE is set, this will match the characters [0 - 9_] plus whatever is classified as alphanumeric in the Unicode character properties database.
\W
When the LOCALE and UNICODE flags are not specified, matches any non-alphanumeric character; this is equivalent to the set [ˆ a - zA - Z0 - 9_]. With LOCALE, it will match any character not in the set [0 - 9_], and not defined as alphanumeric for the current locale. If UNICODE is set, this will match anything other than [0 - 9_] and characters marked as alphanumeric in the Unicode character properties database.
\Z
Matches only at the end of the string.
\a \f \n \r \t \v \x \\
Most of the standard escapes supported by Python string literals are also accepted by the regular expression parser.
\0xyz, \xyz
Octal escapes are included in a limited form: If the first digit is a 0, or if there are three octal digits, it is considered an octal escape. As for string literals, octal escapes are always at most three digits in length.

6.2 Token definition

6.2.1 Predefined tokens

Tokens can be explicitely defined by the token and separator keywords.

A token is defined by:

a name
which identifies the token. This name is used by the parser.
a regular expression
which describes what to match to recognize the token.
an action
which can translate the matched text into a Python object. It can be a function of one argument or a non callable object. If it is not callable, it will be returned for each token otherwise it will be applied to the text of the token and the result will be returned. This action is optional. By default the token text is returned.

Token definitions must end with a ; when no action is specified. The dots after the token name are optional.

See figure 6.1 for examples.




Figure 6.1: Token definition examples
    #     name     reg. exp        action  
    token integer: ’\d+’           int;  
    token ident  : ’[a-zA-Z]\w*’   ;  
    token bool   : ’True|False’    $ lambda b: b==’True’  
 
    separator spaces  : ’\s+’;     # white spaces  
    separator comments: ’#.*’;     # comments



The order of the declaration of the tokens is important. The first token that is matched is returned. The regular expression has a special treatment. If it describes a keyword, TPG also looks for a word boundary after the keyword. If you try to match the keywords if and ifxyz TPG will internally search if\b and ifxyz\b. This way, if won’t match ifxyz and won’t interfere with general identifiers (\w+ for example). This behaviour can be disabled since the version 3 of TPG (see 5.3.2).

There are two kinds of tokens. Tokens defined by the token keyword are parsed by the parser and tokens defined by the separator keyword are considered as separators (white spaces or comments for example) and are wiped out by the lexer.

6.2.2 Inline tokens

Tokens can also be defined on the fly. Their definition are then inlined in the grammar rules. This feature may be useful for keywords or punctuation signs. Inline tokens can not be transformed by an action as predefined tokens. They always return the token in a string.

See figure 6.2 for examples.




Figure 6.2: Inline token definition examples
    IfThenElse ->  
        ’if’ Cond  
        ’then’ Statement  
        ’else’ Statement  
        ;



Inline tokens have a higher precedence than predefined tokens to avoid conflicts (an inlined if won’t be matched as a predefined identifier).

6.3 Token matching

TPG works in two stages. The lexer first splits the input string into a list of tokens and then the parser parses this list. The default lexer is lazy in TPG 3. Tokens are generated while parsing. This way TPG 3 need less memory when parsing huge files.

6.3.1 Splitting the input string

The lexer split the input string according to the token definitions (see 6.2). When the input string can not be matched a tpg.LexicalError exception is raised.

The lexer may loop indefinitely if a token can match an empty string since empty strings are everywhere.

6.3.2 Matching tokens in grammar rules

Tokens are matched as symbols are recognized. Predefined tokens have the same syntax than non terminal symbols. The token text (or the result of the function associated to the token) can be saved by the infix / operator (see figure 6.3).




Figure 6.3: Token usage examples
    S -> ident/i;



Inline tokens have a similar syntax. You just write the regular expression (in a string). Its text can also be saved (see figure 6.4).




Figure 6.4: Token usage examples
    S -> ’(’ ’\w+’/i ’)’;