When I started programming EasyExtend in 2006 one of the major problems was the correct grammar -> NFA translation. I used big grammars and testing for correctness required lots of source code. The first heuristics I used was ugly and complex and it took about 2 or so years to find a neat trick which finally lead to replace it completely. The basic problem of systematic phrase or expression generation for testing purpose persisted though - until last week when I implemented a TokenTracer.
Tracers
A typical production rule in the Trail parser generator is translated into a single NFA which might look as in the following example
1005: ["funcdef: [decorators] 'def' NAME parameters ':' suite",
(1005, 0, 1005),
{(1, 3, 1005): [(1006, 4, 1005)],
(11, 5, 1005): [(1043, 6, 1005)],
('def', 2, 1005): [(1, 3, 1005)],
(1004, 1, 1005): [('def', 2, 1005)],
(1005, 0, 1005): [('def', 2, 1005), (1004, 1, 1005)],
(1006, 4, 1005): [(11, 5, 1005)],
(1043, 6, 1005): [(None, '-', 1005)]}],It is not created for readability but it is nevertheless easy to decode. The funcdef grammar rule is assigned a numerical value, a rule identifier - here 1005. Asscociated with the rule identifier is a 3-list consisting of
- The rule in plain text
- The start state of a finite automaton (1005, 0, 1005)
- A finite automaton encoded as a dictionary of transitions.
Starting with (1005, 0, 1005) one can step through the automaton. The follow states are [('def', 2, 1005), (1004, 1, 1005)]. The first one obviously represents the def keyword whereas the second is a representation of the decorators non-terminal which has the rule identifier 1004. When you select the (1004, 1, 1005) state there is a single follow state, which is again the state of the def keyword otherwise you get the follow state (1, 3, 2005) of (’def’, 2, 1005). The state (None, ‘-’, 1005) doesn’t have a follow state and it is the only one.
You can now define a function that keeps track of this stepping process through a rule. This function is called a Tracer.
A Tracer acts as follows:
>>> tracer = Tracer(rules)
>>> tracer.select(1005) # selects automaton 1005 and returns the rule ids of the
['def', 1004] # possible follow states
>>> tracer.select('def')
[1]
>>> tracer.select(1)
[1006]
...It is possible that a Tracer has to keep track of multiple traces at once. For example the exprlistrule
1069: ["exprlist: expr (',' expr)* [',']",
(1069, 0, 1069),
{(12, 2, 1069): [(1053, 3, 1069)],
(12, 4, 1069): [(None, '-', 1069)],
(1053, 1, 1069): [(12, 4, 1069), (12, 2, 1069), (None, '-', 1069)],
(1053, 3, 1069): [(12, 4, 1069), (12, 2, 1069), (None, '-', 1069)],
(1069, 0, 1069): [(1053, 1, 1069)]}],defines transitions of the kind
(1053, 1, 1069): [(12, 4, 1069), (12, 2, 1069), (None, '-', 1069)]
with two rules of rule id 12 in the follow set. When 12 is selected in the Tracer all follow sets of all rules with rule id = 12 are unified:
>>> tracer.select(1069)
[1053]
>>> tracer.select(1053)
[12, None]
>>> tracer.select(12)
[1053, None]
...
TokenTracers
This kind of tracing functionality is central to EasyExtends implementation of Trace Based Parsing (TBP). For single grammar rules TBP coincides with “Thompson NFA” style parsing discussed at length by Russ Cox or more recently by Carl Friedrich Bolz who gave a Python implementation.
We want to consider now a different sort of tracer which is more complicated to create than those for single grammar rules. Those tracers have to meet the following requirement:
The list of rule id’s returned from tracer.select() shall contain only None or rule id’s of terminal symbols.
The rule id’s of terminals are exactly the token types. The select function of a TokenTracer returns a list of token types and gets fed with a single token type. In the following example we step through the token stream of a simple function
Here we go
>>> tracer = TokenTracer(rules)
>>> tracer.select(1001) # a single select using a top level non-terminal
[0, 1, 2, 3, 4, 7, ... , 'assert', 'break', 'class', 'continue', 'def', ...]
>>> tracer.select('def')
[1]
>>> tracer.select(1) # foo
[7]
>>> tracer.select(7) # (
[1, 7, 8, 16, 36]
>>> tracer.select(8) # )
[11]
>>> tracer.select(11) # :
[0, 1, 2, 3, 4, 7, ... , 'assert', 'break', 'class', 'continue', 'def', ...]
>>> tracer.select(4) # \n
[5]
>>> tracer.select(5) # INDENT
[0, 1, 2, 3, 4, 7, ... , 'assert', 'break', 'class', 'continue', 'def', ...]
>>> tracer.select('print')
[1, 2, 3, 4, 7, 9, 13, 13, 14, 15, 25, 26, 32, 35, 'lambda', 'not']
>>> tracer.select(2) # 42
[4, 7, 9, 12, ..., 36, 48, '<>', 'and', 'if', 'in', 'is', 'is', 'not', 'or']
>>> tracer.select(4) # \n
[1, 2, 3, 6, 7, ... , 'try', 'while', 'with', 'yield']
>>> tracer.select(6) # DEDENT
[0, 1, 2, 3, 4, 7, ... , 'assert', 'break', 'class', 'continue', 'def', ...]
>>> tracer.select(0) # ENDMARKERApplication 1 - error detection
Using a TokenTracer it is dead simple to localize a syntax error which is - in the context free case - always an unexpected token. In principle Trail could delegate error recovery entirely to a TokenTracer.
Application 2 - autocorrection
A constant token is a token with a constant token string e.g. ‘;’ or ‘:’. Closely related are token like INDENT where the token string can be derived from context and a prescribed indentation. In sharp contrast are token like NAME, NUMBER and STRING where the token string is not language but user determined. In the select() sequence above we find constant token lists of length = 1 like [11] or [7]. If one of those token is omitted it can be inserted without guessing.
Application 3 - expression generation
The most intriguing aspect of TokenTracers is that each random token sequence which is constrained by a TokenTracer is syntactically correct. This can be used to create expression generators: first write a grammar G to describe the language syntax, then you derive a TokenTracer(G). Finally an expression generator ExprGen(TokenTracer(G)) is created which is used to build random token sequences being compliant with G by means of the TokenTracer. Those token-sequences can either be turned into valid parse trees and get compiled or un-tokenized into source code.
A valuation function fitness(expr) -> float on expressions motivates the use of genetic programming for breeding expressions of a certain kind. For example I’m strongly interested in compact grammars which create big NFA expansions in Trail. It is not easy to see how those can be built by hand. Using GP one could set an arbitrary threshold like n = 1000 for the number of states in a single expanded NFA and tries to minimize the size of a grammar, where the size is measured in the number of tokens used for a grammar description in some meta-grammar ( e.g. EBNF ).