The special ways to write characters with \ and # has highest precedence, followed by the operator …, followed by the operator ¬, followed by the operators * and +, followed by concatenation. Union has the lowest precedence.

For general information on parser generators, consult [1,2]. For specifics on LR(1), consult [1]. A parser generated by AAAAA's parser generator operates in two phases, lexer and parser. In the first phase, the input is divided into words by matching a set of regular expressions to the longest possible prefix of the input. That prefix is called a lexeme. If the lexeme is matched by a special regular expression called the skip expression, then it is discarded, otherwise the expression matching it, called its token type, is treated as the next non-terminal with respect to the second phase. The token type together with the lexeme is also called token. The regular expressions giving the token types are generally enclosed in curly braces, for example {a+}. For single characters, this is not necessary, so the syntax becomes a pure extension of the one used for ordinary context-free grammars. Note that the token type for two such occurrences are the same only if their textual representation is identical. In particular, {aa*} is a different token type than {a+}, even though they match the same lexemes.

When using some of AAAAA's features, performance can be sluggish. This section describes when and why this is likely to happen, and how to avoid unnecessary bad performance.

and the strings consisting of a block of left parenthesis followed by a block of right parenthesis, ( *)*, and consider the number of strings in the language as a function of the string length, you realize that the left-hand language has an exponential growth, the right-hand side a quadratic growth, and that the intersection contains exactly one string of each even length. Thus, writing a separate grammar for the language is the most efficient solution, but simply interchanging the order of the two languages in the intersection is a reasonable alternative. As a general practical tip: If the intersection is slow, try it the other way around. It may well improve drastically.

It is very easy to write Type 0 grammars which executes very slowly in AAAAA, and it is relatively hard to write grammars that executes efficiently. This is due to the inherent non-deterministic nature of the grammars, and the deterministic nature of the computer which simulates it. The key to efficient grammars is to avoid non-deterministic choices as much as possible, and especially to avoid multiple non-terminals which are simultaneously active in the production. It is much more efficient to have a single working non-terminal going from end to end in the string than it is to have a set of non-terminals all going in a single direction, for example. Using nonterminals to mark the end of the string is still a good idea, but you should avoid letting them disappear on their own accord. It is much preferable to have the worker seek them out and destroy them near the end of the computation.

The grammar above for a wellknown language is straightforward and clear, but unfortunately not too efficient when simulated on a computer. The reason is that there are so many ways to produce the same string. All the N-s move to the right, but it is possible to move the first one all the way before starting on the next one, or just part of the way, and so on. Another grammar for the same language, which is more suited to computer simulation, is the following:

This grammar is slightly more complex to understand, but much more efficient. There is a single worker, moving back and fourth over the block of b-s, alternating roles between a left-mover L and a right-mover R. When it hits the left end of the block of b-s, it either terminates or it drops an extra a and changes direction. That non-deterministic choice is necessary of course, since it determines the length of the string that is produced. When it hits the right end of the block of b-s, it drops an extra c and an extra b and changes direction.

The following grammar (for the language of strings which over a unary alphabet for some natural number have length 2ⁿ) suffers from both a large number of workers (the D-s), and the disappearing endmarkers.

Again, we use a single worker running multiple passes instead of using multiple workers. Also, notice the manner in which the endmarkers M are disposed of, by replacing both the right-going worker R and the right endmarker M with an eraser worker E which travels tot he left endmarker, destroys it and itself, and terminates.

This section describes the requirements for custom procedures needed to extend AAAAA LR(1) parsers with user actions. It is primarily aimed at those teachers who wishes to create other environments than expression evaluation, or customize the existing one, and thereby creating new exercises for students. It may also be of interest for the student who wishes to move one step closer to Yacc [2] and knows some Tcl [3,4]. To benefit from this section, the reader should have a working knowledge of how to write LR(1) parsers in AAAAA, some knowledge of bottom-up parsing [1,2], and a working knowledge of Tcl [3,4]].

1. Call new.
2. Call token and reduce in the order corresponding to shifts and reductions. Repeated some number of times.
3. Call accept.
4. Call format some number of times, corresponding to shifts and reductions.

proc id accept value
Informs the user that value was the result of the parse. May perform some extra processing, and return a modified value, or just return value.

proc id clear
Called when parser is created (including by "Update''), and when the user clicks "Reinitialize''. May be a no-op unless there is some state kept between inputs, in which case it should clear it.

proc id destroy
Called when parser is destroyed (clicking either "Update'' or "Dismiss'', or starting a new session). May be used to free memory (unset) or the like.

proc id format headsymbol headval
After the string has reached accept, the tree is traversed a second time in the same order as the first time. This time the string displayed in show values should be returned, given the value computed by the reduce command.

proc id new
Executed each time the parser is created or the user clicks "Update'' on the parser. May be a no-op unless there is some state to initialize, in which case it should initialize it.

proc id reduce headsymbol ?sym val...?
Executed each time the parser performs a reduction. (Well, actually not, but you should think of it that way anyway.) The headsymbol is the non-terminal it reduces to (the LHS of the production rule), and the rest of the arguments corresponds to the RHS of the production rule, giving the grammar symbol as sym, and its value as val. Should return the new value for headsymbol.

proc id token tokentype lexeme
Executed for each shifted symbol. The tokentype value is the regular expression that matched (note that if the expression was not enclosed in braces AAAAA may add such and possibly alter the expression in other ways), and the lexeme value is the string which matched. Should return the value for the token.

proc expr_eval {id cmd args} {

switch -- $cmd {

accept {

return [lindex $args 0]

}

destroy -

new -

clear {

return

}

token -

format {

return [lindex $args 1]

}

reduce {

set e {}

set rest [lrange $args 1 end]

foreach {sym val} $rest {

lappend e $val

}

if {[catch {set res [expr $e]}]} {

set res "?"

}

return $res

}

}

}

[1] Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers -- Principles, Techniques, and Tools. Addison-Wesley, 1986.

[2] S. C. Johnson. Yacc -- yet another compiler compiler. Computing Science Technical Report 32, AT&T Bell Laboratories, Murray Hill, N.J.

[3] John K. Ousterhout. Tcl and the Tk Toolkit. Addison-Wesley.

[4] Online information on Tcl/Tk: http://www.scriptics.com:8123/, http://www.tclconsortium.org/, and http://www.scriptics.com/ .