CSC 533: Organization of Programming Languages
Spring 2022

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

<statement> --> <assign> | <const> | <local> | <output> | <repeat> | <while> | <if> | <subdecl> | <subcall> <assign> --> <id> '=' <expr> <const> --> 'const' <assign> <local> --> 'local' <assign> <output> --> 'output' '(' { <expr> } ')' <repeat> --> 'repeat' <expr> { <statement> } 'end' <while> --> 'while' <expr> { <statement> } 'end' <if> --> 'if' <expr> { <statement> } { elseif <expr> { <statement> } } [ 'else' { <statement> } ] 'end' <subdecl> --> 'sub' <id> '(' { <id> } ')' { <statement> } 'end' <subcall> --> 'call' <id> '(' { <expr> } ')' <expr> --> <term> | '(' <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' <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 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. 21 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         b4         4b         a_101         _a101        CU#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 )        x + 1            ( -1 + x )        ( 1 + -x )  
  
    ( ( 2 * a ) + 1 )     flag             ( 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. 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            if ( a > b )           if ( avg >= 90 ) {           if x 
      x = 2              max = a                output "A"                   repeat 5
      y = 3            elseif                 elseif ( avg >= 80 )             x = ( x + 1 )
    end                  max = b                output "B"                   end
                       end                    elseif ( avg >= 70 )         end
                                               output "C"
                                             end
  5. 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 end each count as only one token).

  6. Give an example of a repeat loop (repeat) that is as short as possible, in terms of number of tokens (where keywords such as repeat and end 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 end 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 end each count as only one token).