CSC 533: Organization of Programming Languages
Spring 2023

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. 22 are as follows:

<statement> --> <vardecl> | <assign> | <output> | <compound> | <while> | <do> | <if> | <subdecl> | <subcall> <vardecl> --> <type> <assign> <assign> --> <id> '=' <expr> <output> --> 'output' ( <expr> | '{' [ <exprseq> ] '}' ) <compound> --> '{' { <statement> } '}' <while> --> 'while' <expr> 'do' <compound> <do> --> 'do' <compound> 'until' <expr> <if> --> 'if' <expr> 'then' <compound> ( 'noelse' | 'else' <compound> ) <subdecl> --> 'sub' <id> '(' [ <paramseq> ] ')' <compound> <subcall> --> 'call' <id> '(' [ <exprseq> ] ')' <expr> --> <id> | <integer> | <string> | <boolean> | '(' <unary_op> <expr> ')' | '(' <expr> <binary_op> <expr> ')' <exprseq> --> <expr> { ',' <expr> } <paramseq> --> <type> <id> { ',' <type> <id> } <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' | '#' <binary_op> --> '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 is no whitespace (i.e., spaces, tabs or new lines) between the characters in an identifier, integer, or string. Otherwise, whitespace may appear between tokens but is not required.

Answer the following questions about the syntax of SILLY 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. 
        Q         abc         4b        a1b23        123        X_1
  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      (4)      -4        x + 1        (x + 1)        1+(2*a)   
  
    ((2*a)+1)   flag     (not true)      (not (true))      (not (not true))
  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. Which of the following are valid output statements? For each valid statement, provide a parse tree (with the output abstraction at the root). If invalid, briefly describe what aspect violates the rules. 
        output "foo"        output 1+2        output (1+2)        
  
    output ( )          output { }        output { 1, a, true }
  5. 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 true then        if true then        if (a > b) then {         if (avg >= 80) then {          
    noelse              { }                     max = a                   if (avg >= 90) then {
                        noelse              }                                 output "A"
                                            else {                        }
                                                max = b               } else {
                                            }                             output "B"
                                                                      }
  6. Give an example of a while statement (while) that is as short as possible, in terms of number of tokens (where keywords such as while and do each count as only one token).

  7. Give an example of a subroutine declaration (subdecl) that is as short as possible, in terms of number of tokens (where keywords such as sub and ( each count as only one token).

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