aycock(3tcl)					  Aycock-Horspool-Earley parser generator for Tcl				      aycock(3tcl)

__________________________________________________________________________________________________________________________________________________

NAME

       aycock - Aycock-Horspool-Earley parser generator for Tcl

SYNOPSIS

       package require Tcl  8.5

       package require grammar::aycock	?1.0?

       ::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. Practi-
       cal 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:

       ::aycock::parser grammar ?-verbose?
	      Generates a parser for the given grammar, and returns its name.  If the optional -verbose flag is given, dumps  verbose  information
	      relating	to the generated parser to the standard output.  The returned parser is an object that accepts commands as shown in OBJECT
	      COMMAND below.

OBJECT COMMAND

       parserName parse symList valList ?clientData?
	      Invokes a parser returned from ::aycock::parser. symList is a list of grammar symbols representing the terminals in an input string,
	      and valList is a list of their semantic values. The result is the semantic value of the entire string when parsed.

       parserName destroy
	      Destroys a parser constructed by ::aycock::parser.

       parserName terminals
	      Returns a list of terminal symbols that may be presented in the symList argument to the parse object command.

       parserName nonterminals
	      Returns a list of nonterminal symbols that were defined in the parser's grammar.

       parserName save
	      Returns  a  Tcl  script that will reconstruct the parser without needing all the mechanism of the parser generator at run time.  The
	      reconstructed parser depends on a set of commands in the package grammar::aycock::runtime, which is also automatically  loaded  when
	      the grammar::aycock package is loaded.

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:

       o      The name of the nonterminal symbol that the rule reduces.

       o      The literal string, ::=

       o      Zero or more names of terminal or nonterminal symbols that comprise the right-hand-side of the rule.

       o      Finally, a Tcl script to execute when the rule is reduced.  Within the given script, a variable called _	contains  a  list  of  the
	      semantic	values of the symbols on the right-hand side. The value returned by the script is expected to be the semantic value of the
	      left-hand side.  If the clientData parameter was passed to the parse method, it is available in a variable called clientData.  It is
	      permissible  for	the  script to be the empty string.  In this case, the semantic value of the rule will be the same as the semantic
	      value of the first symbol on the right-hand side.  If the right-hand side is also empty,	the  semantic  value  will  be	the  empty
	      string.

       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 (c) 2006 by Kevin B. Kenny <kennykb@acm.org>
       Redistribution permitted under the terms of the Open Publication License <http://www.opencontent.org/openpub/>

grammar_aycock								1.0							      aycock(3tcl)