YSpec - A Macro Preprocessor for Parser Generators

YSpec is a preprocessor for the Yacc and Bison parser generators. It extends their input language by the facility to define and use macro productions. A macro production is a production where the left-hand side looks like a function declaration: a nonterminal symbol with a list of formal parameters. The right-hand side may contain the formal parameters.

Additionally, any right-hand side of a rule may contain macro calls, that is, invocations of a macro production with actual parameters composed from terminals, nonterminals, parameters, and other macro invocations.

The preprocessor specializes the macro productions with respect to the actual parameters of the macro calls. Thus, the resulting grammar is a plain context-free grammar suitable for processing with Yacc or Bison. The crux is that this specialization may not be terminating. For this reason, YSpec analyses the macro grammar before starting the specialization and rejects those grammars for which specialization would not terminate.

Example code from a macro grammar

%{
/* API for generic list construction */
List makeSingleton (void * elem);
List addLast (List, void * elem);
%}

/* parameterized rule */
commalist.1 (item)
: item
        { $$ = makeSingleton ((void *)$1); }
| commalist.1 (item) ',' item
        { $$ = addLast ($1, (void *)$3); }
;

/* two uses, both returning results of type List */
patternlist:    commalist.1(pattern) ;
explist1:       commalist.1(expr) ;
    

Excerpt from specialized grammar

/* parameterized rule */
commalist.1__nexpr__1_0
: expr_
        { $$ = makeSingleton ((void *)$1); }
| commalist.1__nexpr__1_0 ',' expr_
        { $$ = addLast ($1, (void *)$3); }
;

/* parameterized rule */
commalist.1__npattern__1_0
: pattern_
        { $$ = makeSingleton ((void *)$1); }
| commalist.1__npattern__1_0 ',' pattern_
        { $$ = addLast ($1, (void *)$3); }
;
    

Download

Paper describing the theory behind YSpec