next up previous contents index
Next: Parser report Up: Parser Specification Previous: expect: n

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

lhs
:
A11 A12 ¼A1n1
  |  
A21 A22 ¼A2n2
:
  |  
Am1 Am2 ¼Amnm

where lhs is the non-terminal and Aij'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 tex2html_wrap_inline6015

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.



Allen Leung
Mon Apr 7 14:33:55 EDT 1997