1grammar::aycock(nA)ycock-Horspool-Earley parser generator for Tgcrlammar::aycock(n)
2______________________________________________________________________________
6
8 grammar::aycock - Aycock-Horspool-Earley parser generator for Tcl
9
11 package require Tcl 8.5
12 package require grammar::aycock ?1.0?
14 ::aycock::parser grammar ?-verbose?
16 parserName parse symList valList ?clientData?
18 parserName destroy
20 parserName terminals
22 parserName nonterminals
24 parserName save
26______________________________________________________________________________
28
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
36 The grammar::aycock package exports the single procedure:
37 ::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
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 re‐
50 sult is the semantic value of the entire string when parsed.
51 parserName destroy
53 Destroys a parser constructed by ::aycock::parser.
54 parserName terminals
56 Returns a list of terminal symbols that may be presented in the
57 symList argument to the parse object command.
58 parserName nonterminals
60 Returns a list of nonterminal symbols that were defined in the
61 parser's grammar.
62 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
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 • The name of the nonterminal symbol that the rule reduces.
76 • The literal string, ::=
78 • Zero or more names of terminal or nonterminal symbols that com‐
80 prise the right-hand-side of the rule.
81 • 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 Parsing is done with an Earley parser, which is not terribly efficient
95 in speed or memory consumption, but which deals effectively with am‐
96 biguous grammars. For this reason, the grammar::aycock package is per‐
97 haps best adapted to natural-language processing or the parsing of ex‐
98 traordinarily complex languages in which ambiguity can be tolerated.
99
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 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 The example, when run, prints 40.
120
122 Aycock, Earley, Horspool, parser, compiler
123
125 ambiguous, aycock, earley, grammar, horspool, parser, parsing, trans‐
126 ducer
127
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/>
134tcllib 1.0 grammar::aycock(n)