gr...ock(3tcl)

💖 gr...ock(3tcl) — Aycock-Horspool-Earley parser generator for Tcl 💖

okay bestie, gather round, because this page lives in the tcllib manual set and it is genuinely one of the coolest little things in Tcl land. it's the manpage for grammar::aycock, and no, "gr...ock" is not a typo, that's just the nickname the manpage system gave it. iconic behavior honestly. 🦋

---

✨ NAME ✨

grammar::aycock — Aycock-Horspool-Earley parser generator for Tcl. that's the whole vibe. it makes parsers. for you. 💅

---

✨ 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 ✨

so 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. and yes, here's the link, go read it, it's giving academic baddie:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.4254

---

✨ PROCEDURES ✨

the grammar::aycock package exports exactly one procedure. just the one. quality over quantity, periodt. 👑

• ::aycock::parser grammar ?-verbose? — generates a parser for the given grammar, and hands you back its name. if you pass the optional -verbose flag, it dumps verbose information relating to the generated parser to the standard output (yes, it will yap at you, that's the point 🗣️). the returned parser is an object that accepts commands, and those commands are all listed down in OBJECT COMMAND below. go look.

---

✨ OBJECT COMMAND ✨

• parserName parse symList valList ?clientData? — invokes a parser that came back 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 once it's parsed. this is the main character command fr fr. 🌟
• parserName destroy — destroys a parser constructed by ::aycock::parser. bye bestie 🫶
• 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. so like, the runtime comes free with the main package, no separate install moment. slay.

---

✨ DESCRIPTION (the grammar part, pay attention bestie) ✨

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. and each rule is made up of a variable number of elements in the list:

• the name of the nonterminal symbol that the rule reduces.
• the literal string, ::=
• zero or more names of terminal or nonterminal symbols that comprise the right-hand-side of the rule.
• 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's 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. noted and memorized. 📝

parsing is done with an Earley parser, which is not terribly efficient in speed or memory consumption, but which deals effectively with ambiguous grammars. so like, it's not the fastest girly in the room but she handles chaos beautifully. 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. iykyk. 🌸

ngl bestie, "not terribly efficient in speed or memory" is right there in the original and i'm not gonna lie to you about it. she's a vibes parser, not a speedrun parser. 💀

---

✨ EXAMPLE ✨

this 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. so cute, so educational. 🎀

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. no cap. the math is mathing. 🔥

---

✨ KEYWORDS ✨

Aycock, Earley, Horspool, parser, compiler

---

✨ KEYWORDS (yes there are two, and yes i'm keeping both) ✨

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/>

---

and that's the whole page bestie!! this gem comes to you from the tcllib manual collection, version 1.1, filed under gr...ock(3tcl) — and that's a wrap, go build a parser, you're gonna eat. 💖✨🦋💅🫶🌈👑