# Programming Languages Homework 1 SOLUTION

Consider the following EBNF grammar for a very simple programming language:
program ::= statemt {statemt}
statemt ::= asignmt | ifstmt | until | read | write
asignmt ::= ident ~ exprsn ;
ifstmt  ::= I comprsn @ {statemt} [% {statemt}] &
until   ::= U ( comprsn ) D {statemt} \
read    ::= R ident {, ident} ;
write   ::= W ident {, ident} ;
comprsn ::= ( oprnd opratr oprnd )
exprsn  ::= factor {+ factor}
factor  ::= oprnd {* oprnd}
oprnd   ::= integer | ident | ( exprsn )
opratr  ::= < | = | | !
ident   ::= letter {char}
char    ::= letter | digit
integer ::= digit {digit}
letter  ::= _ | X | Y | Z
digit   ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

The tokens are: ~ ; I @ % & U ( ) D \ R , W + * < = ! _ X Y Z 0 1 2 3 4 5 6 7 8 9
Nonterminals are shown as lowercase words.

1. Draw Syntax Diagrams for the above grammar.

2. Show that the grammar satisfies the two rules of predictive parsing.
(it does, you just need to prove it).

3. Implement a recursive-descent recognizer.
- Prompt the user for an input stream.
- The start symbol is *program* (as defined above)
- Report "legal" or "errors found" (not both!).
For example, knowing where your program finds an error could
be helpful for me to assign partial credit, if it's wrong.
- Assume the input stream is the token stream.  Assume that any
whitespace has already been stripped out by the lexical scanner.
(i.e., each token is one character - lexical scanning has been completed)
- Assume the token stream is terminated with a \$.
to questions #1 and #2 above, where appropriate.
- Use Java, C, or C++, or ask your instructor if you wish
to use another language.
- Limit your source code to ONE file.
- Make sure your program works on ATHENA before submitting it.
- INCLUDE INSTRUCTIONS FOR COMPILING AND RUNNING IN A COMMENT
BLOCK AT THE TOP OF YOUR PROGRAM.  BE SPECIFIC!!  DON'T JUST
SAY "use Eclipse" or something like that.  Tell me exactly how
to compile and run your program, step by step.  Also explain
any input format particulars that your program expects the
user to enter.

4. Attach your source file to the drop box in SacCT.

5. Turn in your syntax diagrams and satisfaction proof as attachments
in the same dropbox (in SacCT).  They can be handwritten/scanned,
or computer-drawn.