CSC 533: Organization of Programming Languages
Spring 2021

HW1: Syntax and EBNF Grammars


In the first half of the semester, you will be developing an interpreter for a simple scripting language named SILLY (Simple, Interpreted, Limited Language for You). The EBNF grammar rules for SILLY v. 20.0 are as follows:

<statement> --> <assign> | <vardec> | <output> | <compound> | <repeat> | <while> | <if> | <subdecl> | <subcall> <assign> --> <id> '=' <expr> ';' <vardec> --> <type> <assign> <output> --> 'output' [ <e-list> ] ';' <e-list> --> <expr> { ',' <expr> } <compound> --> '{' { <statement> } '}' <repeat> --> 'repeat' <expr> <compound> <while> --> 'while' <expr> <compound> <if> --> 'if' <expr> <compound> 'else' <compound> <subdecl> --> 'sub' <id> '(' [ <p-list> ] ')' <compound> <p-list> --> <type> <id> { ',' <type> <id> } <subcall> --> 'call' <id> '(' [ <e-list> ] ')' ';' <expr> --> <unary_op> <term> | <term> [ <binary_op> <term> ] <term> --> <id> | <integer> | <string> | <boolean> | '(' <expr> ')' <id> --> <letter> { ( <letter> | <digit> | '_' ) } <integer> --> [ '-' ] <digit> { <digit> } <string> --> '"' { <char> } '"' <boolean> --> 'true' | 'false' <type> --> 'int' | 'str' | 'boo' <letter> --> 'a' | 'b' | 'c' | ... | 'z' | 'A' | 'B' | 'C' | ... | 'Z' <digit> --> '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' <char> --> any non-whitespace character other than '"' <unary_op> --> 'not' | '#chars' <binary_op> --> '+' | '-' | '*' | '/' | '%' | '^' | '@index' | 'and' | 'or' | '==' | '!=' | '>' | '>=' | '<' | '<='

Recall that | denotes alternatives within a rule, [ ] denotes an optional (0 or 1) element, and { } denotes a repetitive (0 or arbitrarily many) element. There are no spaces between the characters in an identifier, integer, or string. Otherwise, tokens in the other rules are all separated by whitespace.

Answer the following questions about the syntax of SILLY v. 20 based on the above grammar rules.

  1. Which of the following are valid identifiers? For each valid identifier, provide a parse tree (with the id abstraction at the root). If invalid, briefly describe what aspect violates the rules.
        A        x1        1x        x_1        _x1        a1_b2        a1$b2
    
  2. Which of the following are valid expressions? For each valid expression, provide a parse tree (with the expr abstraction at the root). If invalid, briefly describe what aspect violates the rules.
        4                  -1 + x             1 + -x           ( ( 2 ) )  
      
        ( 2 * a ) + 1      1 + ( 2 * a )      not flag         not not flag
    
  3. How is operator precedence and associativity handled in SILLY? For example, are the following expressions valid? If so, provide parse trees and identify precedence and associativity. If not, explain why they are invalid.
        not true or false                3 + 4 * 5                8 / 4 / 2
    
  4. Do variable declarations (vardec) require a semicolon at the end? Justify your answer by referring to the appropriate grammar rule(s).

  5. Are curly braces always required when specifying the statements to be executed by a repeat loop (repeat)? Justify your answer by referring to the appropriate grammar rule(s).

  6. Which of the following are valid if statements? If valid, provide a parse tree (with the if abstraction at the root). If invalid, briefly describe what aspect violates the rules.
        if 2 == 3 { } else         if true {                 if ( a > b ) {
        { output ; }                 output "yes" ;            max = a ;
                                   }                           min = b ;
                                                             }
                                                             else {
                                                               max = b ;
                                                               min = a ;
                                                             }      
    
  7. Give an example of an if statement (if) that is as short as possible, in terms of number of tokens (where keywords such as if and true each count as only one token).

  8. Give an example of a while loop (while) that is as short as possible, in terms of number of tokens (where keywords such as while and true each count as only one token).

  9. Provide an example of a valid subroutine declaration (subdecl) and provide a parse tree for it.

  10. Provide an example of a valid subroutine call (subcall) and provide a parse tree for it.