PL Grammar -- Sample Solution (Assignment 2)

The following non-terminals are helpers:

<null>   ::= 0
<vdigit> ::= 1|2|3|4|5|6|7|8|9
<digit>  ::= <null> | <vdigit>

<digit-sequence> ::= <empty> |
                     <digit> <digit-sequence> 

<pos-int> ::= <vdigit> <digit-sequence>

The following non-terminals are lexical tokens:

<null>  ::= 0
<semi>  ::= ';'
<colon> ::= ':'

<variable> ::= 'X' <pos-int> |
               'Y' <pos-int> |
               'Z' <pos-int>

<label> ::= 'l' <pos-int>

<assign> ::= '<='

<inc> ::= '++'

<loop> ::= 'loop'
<endloop> ::= 'endloop'
<goto> ::= 'goto'


Here is the context-free part of the grammar, with start symbol
<program>:

<program> ::= <empty> |
              <lstatement> <program> 

<lstatement> ::= <label> <colon> <statement> |
                 <statement>

<statement> ::= <variable> <inc> <semi>|
                <variable> <assign> <null> <semi> |
                <goto> <label> <semi> |
                <loop> <variable> <semi> <program> <endloop> <semi>


Remarks:

- Notice that <null> appears both as a token and as a helper -- and
  remember the "longest match" rule": 'X20' is ONE token, not a
  <variable> token followed by a <null> token!
- If arbitrary sequences of digits are allowed (instead of only those
  not starting with 0), it's not  big deal.
- The first versions of the slides had an additional semicolon before
  the 'endloop' -- we'll accept both version as correct.
- If somebody has a composite token '<= 0', that is bad style (because
  white space between tokens should be insignificant), but not too
  bad.
- Quotes such as in '0' are optional