Here is the full definition of our language:
definition of Exp is
rules
<axiom> ::= <exp_s> ;
<exp_s>
<exp_s> ::= <exp> ;
exp_s-list ((<exp>))
<exp_s> ::= <exp_s> ";" <exp> ;
exp_s-post (<exp_s>,<exp>)
<exp> ::= <variable> ":=" <exp> ;
assign (<variable>,<exp>)
<exp> ::= <factor> ;
<factor>
<exp> ::= <exp> "+" <factor> ;
plus (<exp>,<factor>)
<exp> ::= <exp> "-" <factor> ;
minus (<exp>,<factor>)
<factor> ::= <unary> ;
<unary>
<factor> ::= <factor> "*" <unary> ;
prod (<factor>,<unary>)
<unary> ::= <term> ;
<term>
<unary> ::= "-" <term> ;
uminus(<term>)
<term> ::= <variable> ;
<variable>
<term> ::= <int> ;
<int>
<term> ::= "(" <exp> ")" ;
<exp>
<variable> ::= %ID ;
variable-atom (%ID)
<int> ::= %INTEGER ;
integer-atom (%INTEGER)
abstract syntax
exp_s -> EXP + ... ;
assign -> VAR EXP ;
plus -> EXP EXP ;
minus -> EXP EXP ;
prod -> EXP EXP ;
uminus -> EXP ;
variable -> implemented as IDENTIFIER ;
integer -> implemented as INTEGER ;
EXP_S ::= exp_s ;
EXP ::= assign plus minus prod
uminus variable integer ;
VAR ::= variable ;
rules
<axiom> ::= "[EXP_S]" <exp_s> ;
<exp_s>
<axiom> ::= "[EXP]" <exp> ;
<exp>
<axiom> ::= "[VAR]" <variable> ;
<variable>
end definition
Normally the parser assumes that the very first production rule in the specification defines the beginning of a legal sentence. We may specify other entry points as well using the same left hand side as the first rule. This allows the parser to recognize program fragments instead of systematically trying to parse an entire program. The name of the first production rule is <axiom> which also appears on the left hand side of the last three rules so the parser will accept a list of expressions, a single expression, or just a variable as valid sentences. A special token appears on the right hand side of each axiom rule -the phylum name in brackets of the abstract syntax operator to be constructed. Since an operator may belong to different phyla, we specify the phyla that interests us explicitly, enabling the parser to construct the correct tree. Thus, if we want to parse just one expression instead of a list, we feed the line [EXP] 89 * Myvar to the parser.