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!). You can report additional information as well, if you want. 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 $. Add the $ to the grammar and incorporate it in your answers 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.
