1grammar::aycock(nA)ycock-Horspool-Earley parser generator for Tgcrlammar::aycock(n)
2
3
4
5______________________________________________________________________________
6

NAME

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

SYNOPSIS

11       package require Tcl  8.5
12
13       package require grammar::aycock  ?1.0?
14
15       ::aycock::parser grammar ?-verbose?
16
17       parserName parse symList valList ?clientData?
18
19       parserName destroy
20
21       parserName terminals
22
23       parserName nonterminals
24
25       parserName save
26
27______________________________________________________________________________
28

DESCRIPTION

30       The grammar::aycock package implements a parser generator for the class
31       of parsers described in John Aycock and R.  Nigel  Horspool.  Practical
32       Earley   Parsing.    The   Computer   Journal,   45(6):620-630,   2002.
33       http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.4254
34

PROCEDURES

36       The grammar::aycock package exports the single procedure:
37
38       ::aycock::parser grammar ?-verbose?
39              Generates a parser for the given grammar, and returns its  name.
40              If  the  optional -verbose flag is given, dumps verbose informa‐
41              tion relating to the generated parser to  the  standard  output.
42              The  returned parser is an object that accepts commands as shown
43              in OBJECT COMMAND below.
44

OBJECT COMMAND

46       parserName parse symList valList ?clientData?
47              Invokes a parser returned from ::aycock::parser.  symList  is  a
48              list  of  grammar symbols representing the terminals in an input
49              string, and valList is a list  of  their  semantic  values.  The
50              result is the semantic value of the entire string when parsed.
51
52       parserName destroy
53              Destroys a parser constructed by ::aycock::parser.
54
55       parserName terminals
56              Returns  a list of terminal symbols that may be presented in the
57              symList argument to the parse object command.
58
59       parserName nonterminals
60              Returns a list of nonterminal symbols that were defined  in  the
61              parser's grammar.
62
63       parserName save
64              Returns  a  Tcl  script that will reconstruct the parser without
65              needing all the mechanism of the parser generator at  run  time.
66              The  reconstructed  parser  depends  on a set of commands in the
67              package grammar::aycock::runtime, which  is  also  automatically
68              loaded when the grammar::aycock package is loaded.
69

DESCRIPTION

71       The  grammar::aycock::parser  command  accepts a grammar expressed as a
72       Tcl list.  The list must be structured as the concatenation of a set of
73       rules. Each rule comprises a variable number of elements in the list:
74
75       ·      The name of the nonterminal symbol that the rule reduces.
76
77       ·      The literal string, ::=
78
79       ·      Zero  or more names of terminal or nonterminal symbols that com‐
80              prise the right-hand-side of the rule.
81
82       ·      Finally, a Tcl script to  execute  when  the  rule  is  reduced.
83              Within  the given script, a variable called _ contains a list of
84              the semantic values of the symbols on the right-hand  side.  The
85              value  returned  by  the  script  is expected to be the semantic
86              value of the left-hand side.  If the  clientData  parameter  was
87              passed to the parse method, it is available in a variable called
88              clientData.  It is permissible for the script to  be  the  empty
89              string.   In  this  case, the semantic value of the rule will be
90              the same as the semantic value of the first symbol on the right-
91              hand  side.   If the right-hand side is also empty, the semantic
92              value will be the empty string.
93
94       Parsing is done with an Earley parser, which is not terribly  efficient
95       in  speed  or  memory  consumption,  but  which  deals effectively with
96       ambiguous grammars.  For this reason, the  grammar::aycock  package  is
97       perhaps  best  adapted to natural-language processing or the parsing of
98       extraordinarily complex languages in which ambiguity can be tolerated.
99

EXAMPLE

101       The following code demonstrates a trivial  desk  calculator,  admitting
102       only  +,  * and parentheses as its operators.  It also shows the format
103       in which the lexical analyzer is expected to present  terminal  symbols
104       to the parser.
105
106
107              set p [aycock::parser {
108                  start ::= E {}
109                  E ::= E + T {expr {[lindex $_ 0] + [lindex $_ 2]}}
110                  E ::= T {}
111                  T ::= T * F {expr {[lindex $_ 0] * [lindex $_ 2]}}
112                  T ::= F {}
113                  F ::= NUMBER {}
114                  F ::= ( E ) {lindex $_ 1}
115              }]
116              puts [$p parse {(  NUMBER +  NUMBER )  *  ( NUMBER +  NUMBER ) }  {{} 2      {} 3      {} {} {} 7     {} 1      {}}]
117              $p destroy
118
119       The example, when run, prints 40.
120

KEYWORDS

122       Aycock, Earley, Horspool, parser, compiler
123

KEYWORDS

125       ambiguous,  aycock,  earley, grammar, horspool, parser, parsing, trans‐
126       ducer
127

CATEGORY

129       Grammars and finite automata
130
132       Copyright (c) 2006 by Kevin B. Kenny <kennykb@acm.org>
133       Redistribution permitted under the terms of the Open Publication License <http://www.opencontent.org/openpub/>
134
135
136
137
138tcllib                                1.0                   grammar::aycock(n)
Impressum