Tcl Library Source Code

Documentation
Login
EuroTcl/OpenACS 11 - 12 JULY 2024, VIENNA


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

NAME

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

Table Of Contents

SYNOPSIS

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

DESCRIPTION

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. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.4254

PROCEDURES

The grammar::aycock package exports the single procedure:

OBJECT COMMAND

DESCRIPTION

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.

EXAMPLE

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.

KEYWORDS

Aycock, Earley, Horspool, parser, compiler

KEYWORDS

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

CATEGORY

Grammars and finite automata

COPYRIGHT

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