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''[http://www.oreilly.com/catalog/lex/]) 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  

(More to come)

Interestingly running bison 1.35 on this same input file results in 9 states.  Therefore taccle is 23% more efficient than bison. ''<g>''


----

Return to [Jason Tang]

----

[Category Application]