Production rules

The syntax of the production rules is as follows:

Production_Rule	::=	Id [ Type_Exp ] :
		[ One_Alt  - ¼ - One_Alt ] ;
One_Alt	::=	[ Symbol  ¼ Symbol ]	one alternative
Symbol	::=	Id	non-terminal
	|	Cons	terminal (a datatype constructor)
	|	String	terminal (a datatype constructor)
	|	Char	terminal (from the ASCII character set)
	|	?	the error terminal
	|	$	the end of file terminal
	|	{ Code }	embedded actions

Each rule specifies a set of productions of the form

where lhs is the non-terminal and A_ij's are a mixture of terminals, non-terminals and embedded actions. If synthesized attributes are used, then the type of the s-attribute should be annotated next to the lhs non-terminal.

Terminals can be specified in a few ways: (i) a character literal is a predefined terminal of the same name, (ii) a string literal is matched with a datatype or a lexeme class constructor of the same name, (iii) an identifier is a terminal if there is a datatype constructor of the same name. Any other identifiers are assumed to be non-terminals.

For example, the following are two sets of production rules used in the Prop translator itself:

ty Ty:  simple_ty               { $$ = $1; }
|       ty '=' exp              { $$ = DEFVALty($1,$3); }
|       ty '*'                  { $$ = mkptrty($1); }
|       ty '&'                  { $$ = mkrefty($1); }
|       ty '[' ']'              { $$ = mkptrty($1); }
|       ty '[' exp ']'          { $$ = mkarrayty($1,$3); }
;
exp Exp:
        app_exp                 { $$ = $1; }
|       exp '+' exp             { $$ = BINOPexp("+",$1,$3); }
|       exp '-' exp             { $$ = BINOPexp("-",$1,$3); }
|       exp '*' exp             { $$ = BINOPexp("*",$1,$3); }
|       exp '/' exp             { $$ = BINOPexp("/",$1,$3); }
|       exp '%' exp             { $$ = BINOPexp("%",$1,$3); }
|       exp '^' exp             { $$ = BINOPexp("^",$1,$3); }
|       exp "+=" exp            { $$ = BINOPexp("+=",$1,$3); }
|       exp "-=" exp            { $$ = BINOPexp("-=",$1,$3); }
|       exp "*=" exp            { $$ = BINOPexp("*=",$1,$3); }
|       exp "/=" exp            { $$ = BINOPexp("/=",$1,$3); }
|       exp "%=" exp            { $$ = BINOPexp("%=",$1,$3); }

etc

Here, ty is the non-terminal of this production. The type of the synthesized attribute of this rule is Ty, and it is written next to the non-terminal. Like yacc, the synthesized attribute of a rule can be referenced using the $ variables: variable $$  denote the synthesized attribute of the current rule, while $n  where n is 1, 2, 3, ...denote the synthesized attribute of the nth rhs symbol of the current rule.