taccle is a complement to fickle in that it reads a taccle specification file to generate working LALR(1) parser. In other words, it is to Tcl what yacc (or bison) is to C/C++. taccle differs from yeti in that the grammar is written before hand as a straight text file rather than generated by procedure calls.
taccle spec files are structured nearly identical to those used by yacc. The following example (blantantly stolen from chapter 8 of lex & yacc[L1 ]) may be interpreted equally by the two:
%token A R %% start: x | y R; x: A R; y: A;
Incidentally both yacc and taccle would recognize the shift/reduce conflict above.
I originally wrote taccle to learn about the fun world of LALR(1). As that I do not have a PhD in automata theory the LALR(1) generation is a bit inefficient; I calculate the canonical LR(1) and then merge cores. For those learning parsing theory and syntax parsing in tcl taccle can be set to display every step. taccle calculates seven states in the canonical LR(1):
lr(1) table:
state 0:
start' -> . start, {$}
start -> . x, {$}
start -> . y R, {$}
x -> . A R, {$}
y -> . A, R
transitions: A => s1 start => s2 x => s3 y => s4
state 1:
x -> A . R, {$}
y -> A ., R
transitions: R => s5
state 2:
start' -> start ., {$}
state 3:
start -> x ., {$}
state 4:
start -> y . R, {$}
transitions: R => s6
state 5:
x -> A R ., {$}
state 6:
start -> y R ., {$}{$} is the standard end of input symbol. Converting to LALR(1) gains nothing in this case. The fully generated parse table is:
generated lalr(1) parse table:
state A R start x y $
0 sh1 go2 go3 go4
1 sh5
2 accept
3 re1
4 sh6
5 re3
6 re2 Note how taccle resolved the shift/reduce conflict in state 1 by giving precedence to shift. Running bison 1.35 on this same input file results in 9 states. Therefore taccle is 23% more efficient than bison. <g>
(More to come)
Return to Jason Tang