Tcl Library Source Code

EuroTcl/OpenACS 11 - 12 JULY 2024, VIENNA

[ Main Table Of Contents | Table Of Contents | Keyword Index | Categories | Modules | Applications ]


grammar::aycock - Aycock-Horspool-Earley parser generator for Tcl

Table Of Contents


package require Tcl 8.5 9
package require grammar::aycock ?1.1?

::aycock::parser grammar ?-verbose?
parserName parse symList valList ?clientData?
parserName destroy
parserName terminals
parserName nonterminals
parserName save


The grammar::aycock package implements a parser generator for the class of parsers described in John Aycock and R. Nigel Horspool. Practical Earley Parsing. The Computer Journal, 45(6):620-630, 2002.


The grammar::aycock package exports the single procedure:



The grammar::aycock::parser command accepts a grammar expressed as a Tcl list. The list must be structured as the concatenation of a set of rules. Each rule comprises a variable number of elements in the list:

Parsing is done with an Earley parser, which is not terribly efficient in speed or memory consumption, but which deals effectively with ambiguous grammars. For this reason, the grammar::aycock package is perhaps best adapted to natural-language processing or the parsing of extraordinarily complex languages in which ambiguity can be tolerated.


The following code demonstrates a trivial desk calculator, admitting only +, * and parentheses as its operators. It also shows the format in which the lexical analyzer is expected to present terminal symbols to the parser.

set p [aycock::parser {
    start ::= E {}
    E ::= E + T {expr {[lindex $_ 0] + [lindex $_ 2]}}
    E ::= T {}
    T ::= T * F {expr {[lindex $_ 0] * [lindex $_ 2]}}
    T ::= F {}
    F ::= NUMBER {}
    F ::= ( E ) {lindex $_ 1}
puts [$p parse {(  NUMBER +  NUMBER )  *  ( NUMBER +  NUMBER ) }  {{} 2      {} 3      {} {} {} 7     {} 1      {}}]
$p destroy

The example, when run, prints 40.


Aycock, Earley, Horspool, parser, compiler


ambiguous, aycock, earley, grammar, horspool, parser, parsing, transducer


Grammars and finite automata


Copyright © 2006 by Kevin B. Kenny Redistribution permitted under the terms of the Open Publication License http://www\.opencontent\.org/openpub/