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!).
           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.
Powered by