'\"
'\" Generated from file 'aycock\&.man' by tcllib/doctools with format 'nroff'
'\" 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/>
'\"
.TH "grammar::aycock" n 1\&.1 tcllib "Aycock-Horspool-Earley parser generator for Tcl"
.\" The -*- nroff -*- definitions below are for supplemental macros used
.\" in Tcl/Tk manual entries.
.\"
.\" .AP type name in/out ?indent?
.\"	Start paragraph describing an argument to a library procedure.
.\"	type is type of argument (int, etc.), in/out is either "in", "out",
.\"	or "in/out" to describe whether procedure reads or modifies arg,
.\"	and indent is equivalent to second arg of .IP (shouldn't ever be
.\"	needed;  use .AS below instead)
.\"
.\" .AS ?type? ?name?
.\"	Give maximum sizes of arguments for setting tab stops.  Type and
.\"	name are examples of largest possible arguments that will be passed
.\"	to .AP later.  If args are omitted, default tab stops are used.
.\"
.\" .BS
.\"	Start box enclosure.  From here until next .BE, everything will be
.\"	enclosed in one large box.
.\"
.\" .BE
.\"	End of box enclosure.
.\"
.\" .CS
.\"	Begin code excerpt.
.\"
.\" .CE
.\"	End code excerpt.
.\"
.\" .VS ?version? ?br?
.\"	Begin vertical sidebar, for use in marking newly-changed parts
.\"	of man pages.  The first argument is ignored and used for recording
.\"	the version when the .VS was added, so that the sidebars can be
.\"	found and removed when they reach a certain age.  If another argument
.\"	is present, then a line break is forced before starting the sidebar.
.\"
.\" .VE
.\"	End of vertical sidebar.
.\"
.\" .DS
.\"	Begin an indented unfilled display.
.\"
.\" .DE
.\"	End of indented unfilled display.
.\"
.\" .SO ?manpage?
.\"	Start of list of standard options for a Tk widget. The manpage
.\"	argument defines where to look up the standard options; if
.\"	omitted, defaults to "options". The options follow on successive
.\"	lines, in three columns separated by tabs.
.\"
.\" .SE
.\"	End of list of standard options for a Tk widget.
.\"
.\" .OP cmdName dbName dbClass
.\"	Start of description of a specific option.  cmdName gives the
.\"	option's name as specified in the class command, dbName gives
.\"	the option's name in the option database, and dbClass gives
.\"	the option's class in the option database.
.\"
.\" .UL arg1 arg2
.\"	Print arg1 underlined, then print arg2 normally.
.\"
.\" .QW arg1 ?arg2?
.\"	Print arg1 in quotes, then arg2 normally (for trailing punctuation).
.\"
.\" .PQ arg1 ?arg2?
.\"	Print an open parenthesis, arg1 in quotes, then arg2 normally
.\"	(for trailing punctuation) and then a closing parenthesis.
.\"
.\"	# Set up traps and other miscellaneous stuff for Tcl/Tk man pages.
.if t .wh -1.3i ^B
.nr ^l \n(.l
.ad b
.\"	# Start an argument description
.de AP
.ie !"\\$4"" .TP \\$4
.el \{\
.   ie !"\\$2"" .TP \\n()Cu
.   el          .TP 15
.\}
.ta \\n()Au \\n()Bu
.ie !"\\$3"" \{\
\&\\$1 \\fI\\$2\\fP (\\$3)
.\".b
.\}
.el \{\
.br
.ie !"\\$2"" \{\
\&\\$1	\\fI\\$2\\fP
.\}
.el \{\
\&\\fI\\$1\\fP
.\}
.\}
..
.\"	# define tabbing values for .AP
.de AS
.nr )A 10n
.if !"\\$1"" .nr )A \\w'\\$1'u+3n
.nr )B \\n()Au+15n
.\"
.if !"\\$2"" .nr )B \\w'\\$2'u+\\n()Au+3n
.nr )C \\n()Bu+\\w'(in/out)'u+2n
..
.AS Tcl_Interp Tcl_CreateInterp in/out
.\"	# BS - start boxed text
.\"	# ^y = starting y location
.\"	# ^b = 1
.de BS
.br
.mk ^y
.nr ^b 1u
.if n .nf
.if n .ti 0
.if n \l'\\n(.lu\(ul'
.if n .fi
..
.\"	# BE - end boxed text (draw box now)
.de BE
.nf
.ti 0
.mk ^t
.ie n \l'\\n(^lu\(ul'
.el \{\
.\"	Draw four-sided box normally, but don't draw top of
.\"	box if the box started on an earlier page.
.ie !\\n(^b-1 \{\
\h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul'
.\}
.el \}\
\h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul'
.\}
.\}
.fi
.br
.nr ^b 0
..
.\"	# VS - start vertical sidebar
.\"	# ^Y = starting y location
.\"	# ^v = 1 (for troff;  for nroff this doesn't matter)
.de VS
.if !"\\$2"" .br
.mk ^Y
.ie n 'mc \s12\(br\s0
.el .nr ^v 1u
..
.\"	# VE - end of vertical sidebar
.de VE
.ie n 'mc
.el \{\
.ev 2
.nf
.ti 0
.mk ^t
\h'|\\n(^lu+3n'\L'|\\n(^Yu-1v\(bv'\v'\\n(^tu+1v-\\n(^Yu'\h'-|\\n(^lu+3n'
.sp -1
.fi
.ev
.\}
.nr ^v 0
..
.\"	# Special macro to handle page bottom:  finish off current
.\"	# box/sidebar if in box/sidebar mode, then invoked standard
.\"	# page bottom macro.
.de ^B
.ev 2
'ti 0
'nf
.mk ^t
.if \\n(^b \{\
.\"	Draw three-sided box if this is the box's first page,
.\"	draw two sides but no top otherwise.
.ie !\\n(^b-1 \h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c
.el \h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c
.\}
.if \\n(^v \{\
.nr ^x \\n(^tu+1v-\\n(^Yu
\kx\h'-\\nxu'\h'|\\n(^lu+3n'\ky\L'-\\n(^xu'\v'\\n(^xu'\h'|0u'\c
.\}
.bp
'fi
.ev
.if \\n(^b \{\
.mk ^y
.nr ^b 2
.\}
.if \\n(^v \{\
.mk ^Y
.\}
..
.\"	# DS - begin display
.de DS
.RS
.nf
.sp
..
.\"	# DE - end display
.de DE
.fi
.RE
.sp
..
.\"	# SO - start of list of standard options
.de SO
'ie '\\$1'' .ds So \\fBoptions\\fR
'el .ds So \\fB\\$1\\fR
.SH "STANDARD OPTIONS"
.LP
.nf
.ta 5.5c 11c
.ft B
..
.\"	# SE - end of list of standard options
.de SE
.fi
.ft R
.LP
See the \\*(So manual entry for details on the standard options.
..
.\"	# OP - start of full description for a single option
.de OP
.LP
.nf
.ta 4c
Command-Line Name:	\\fB\\$1\\fR
Database Name:	\\fB\\$2\\fR
Database Class:	\\fB\\$3\\fR
.fi
.IP
..
.\"	# CS - begin code excerpt
.de CS
.RS
.nf
.ta .25i .5i .75i 1i
..
.\"	# CE - end code excerpt
.de CE
.fi
.RE
..
.\"	# UL - underline word
.de UL
\\$1\l'|0\(ul'\\$2
..
.\"	# QW - apply quotation marks to word
.de QW
.ie '\\*(lq'"' ``\\$1''\\$2
.\"" fix emacs highlighting
.el \\*(lq\\$1\\*(rq\\$2
..
.\"	# PQ - apply parens and quotation marks to word
.de PQ
.ie '\\*(lq'"' (``\\$1''\\$2)\\$3
.\"" fix emacs highlighting
.el (\\*(lq\\$1\\*(rq\\$2)\\$3
..
.\"	# QR - quoted range
.de QR
.ie '\\*(lq'"' ``\\$1''\\-``\\$2''\\$3
.\"" fix emacs highlighting
.el \\*(lq\\$1\\*(rq\\-\\*(lq\\$2\\*(rq\\$3
..
.\"	# MT - "empty" string
.de MT
.QW ""
..
.BS
.SH NAME
grammar::aycock \- Aycock-Horspool-Earley parser generator for Tcl
.SH SYNOPSIS
package require \fBTcl 8\&.5 9\fR
.sp
package require \fBgrammar::aycock ?1\&.1?\fR
.sp
\fB::aycock::parser\fR \fIgrammar\fR ?\fB-verbose\fR?
.sp
\fIparserName\fR \fBparse\fR \fIsymList\fR \fIvalList\fR ?\fIclientData\fR?
.sp
\fIparserName\fR \fBdestroy\fR
.sp
\fIparserName\fR \fBterminals\fR
.sp
\fIparserName\fR \fBnonterminals\fR
.sp
\fIparserName\fR \fBsave\fR
.sp
.BE
.SH DESCRIPTION
.PP
The \fBgrammar::aycock\fR package
implements a parser generator for the class of parsers described
in John Aycock and R\&. Nigel Horspool\&. Practical Earley Parsing\&.
\fIThe Computer Journal,\fR \fI45\fR(6):620-630, 2002\&.
\fIhttp://citeseerx\&.ist\&.psu\&.edu/viewdoc/summary?doi=10\&.1\&.1\&.12\&.4254\fR
.SH PROCEDURES
The \fBgrammar::aycock\fR package exports the single procedure:
.TP
\fB::aycock::parser\fR \fIgrammar\fR ?\fB-verbose\fR?
Generates a parser for the given \fIgrammar\fR, and returns its
name\&.  If the optional \fB-verbose\fR 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
\fBOBJECT COMMAND\fR below\&.
.PP
.SH "OBJECT COMMAND"
.TP
\fIparserName\fR \fBparse\fR \fIsymList\fR \fIvalList\fR ?\fIclientData\fR?
Invokes a parser returned from \fB::aycock::parser\fR\&. \fIsymList\fR is
a list of grammar symbols representing the terminals in an input
string, and \fIvalList\fR is a list of their semantic values\&. The
result is the semantic value of the entire string when parsed\&.
.TP
\fIparserName\fR \fBdestroy\fR
Destroys a parser constructed by \fB::aycock::parser\fR\&.
.TP
\fIparserName\fR \fBterminals\fR
Returns a list of terminal symbols that may be presented in the
\fIsymList\fR argument to the \fBparse\fR object command\&.
.TP
\fIparserName\fR \fBnonterminals\fR
Returns a list of nonterminal symbols that were defined in the
parser's grammar\&.
.TP
\fIparserName\fR \fBsave\fR
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 \fBgrammar::aycock::runtime\fR,
which is also automatically loaded
when the \fBgrammar::aycock\fR package is loaded\&.
.PP
.SH DESCRIPTION
The \fBgrammar::aycock::parser\fR command accepts a grammar expressed as
a Tcl list\&.  The list must be structured as the concatenation of a set
of \fIrule\fRs\&. Each \fIrule\fR comprises a variable number of
elements in the list:
.IP \(bu
The name of the nonterminal symbol that the rule reduces\&.
.IP \(bu
The literal string, \fB::=\fR
.IP \(bu
Zero or more names of terminal or nonterminal symbols that
comprise the right-hand-side of the rule\&.
.IP \(bu
Finally, a Tcl script to execute when the rule is reduced\&.
Within the given script, a variable called \fB_\fR 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 \fIclientData\fR parameter was passed to the
\fBparse\fR method, it is available in a variable called
\fBclientData\fR\&.  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\&.
.PP
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 \fBgrammar::aycock\fR package is
perhaps best adapted to natural-language processing or the parsing of
extraordinarily complex languages in which ambiguity can be tolerated\&.
.SH EXAMPLE
The following code demonstrates a trivial desk calculator, admitting
only \fB+\fR, \fB*\fR and parentheses as its operators\&.  It also
shows the format in which the lexical analyzer is expected to present
terminal symbols to the parser\&.
.CS


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

.CE
The example, when run, prints \fB40\fR\&.
.SH KEYWORDS
Aycock, Earley, Horspool, parser, compiler
.SH KEYWORDS
ambiguous, aycock, earley, grammar, horspool, parser, parsing, transducer
.SH CATEGORY
Grammars and finite automata
.SH COPYRIGHT
.nf
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/>

.fi