CSC 533: Programming Languages
Spring 2026

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

<statement> --> <assign> | <var> | <print> | <if> | <while> | <repeat> | <sub> | <call> | <exit> <assign> --> <id> 'gets' <expr> <var> --> 'var' <assign> <print> --> 'print' <expr> <if> --> 'if' <expr> 'then' <body> { 'elseif' <expr> 'then' <body> } [ 'else' <body> ] 'endif' <while> --> 'while' <expr> 'do' <body> 'endwhile' <repeat> --> 'repeat' <expr> 'times' <body> 'endrepeat' <body> --> { <statement> } <sub> --> 'sub' <id> '(' { <id> } ')' 'does' <body> 'endsub' <call> --> 'call' <id> '(' { <expr> } ')' <exit> --> 'exit' <expr> --> <integer> | <boolean> | <string> | <list> | <id> | '(' <unary-op> <expr> ')' | '(' <expr> <binary-op> <expr> ')' <id> --> <letter> { (<letter> | <digit>) } <integer> --> [ '-' ] <digit> { <digit> } <string> --> '"' { <nwnq> } '"' <boolean> --> 'true' | 'false' <list> --> '[' { <expr> } ']' <letter> --> 'a' | 'b' | 'c' | ... | 'z' | 'A' | 'B' | 'C' | ... | 'Z' <digit> --> '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' <nwnq> --> any non-whitespace character other than '"' or '\'' <unary-op> --> '!' | '#' <binary-op> --> '&' | '|' | '+' | '*' | '/' | '%' | '^' | '@' | '=' | '\' | '>' | '<'

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, number, character or string. Delimiters (e.g., '{' and '}') and operators (e.g., '+' and '@') do not require spaces to separate them from other tokens, but all others do.

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. 
        X          2b         x1y2       a_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)          (1 + -4)         x                x*10
  
    (x * 10)     (a & !b)      (a & (!b))       (3 > 2 > 1)      ((2 < 3) | true)
  3. 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 (x = y) then       if true then        if (m > n) then          if (grade > 90) then     
      print "eq"          else endif            print 0                  x gets "A"
    endif                                     else if (m = n) then     elseif (grade > 80) then        
                                                print 1                  x gets "B"        
                                              else                     endif
                                                print 2
                                              endif
  4. Is it valid to mix the types of values in a list, e.g., ["foo" 3]? If so, provide a parse tree for this list expression. If not, explain why not.

  5. Is it valid to nest a list inside another list, e.g., [1 [2 3]]? If so, provide a parse tree for this list expression. If not, explain why not.

  6. Give an example of an assignment statement (assign) that is as short as possible, in terms of number of tokens. Note that keywords (such as gets) are indivisible and thus count as a single token. You do not need to provide a parse tree.

  7. Give an example of a while statement (while) that is as short as possible, in terms of number of tokens. You do not need to provide a parse tree.

  8. Give an example of a subroutine declaration (sub) that is as short as possible, in terms of number of tokens. You do not need to provide a parse tree.

  9. Give an example of a subroutine call (call) that is as short as possible, in terms of number of tokens. You do not need to provide a parse tree.