COMPUTING SCIENCE 370 -- Programming Languages

Exercise Set 1 -- EBNF

Due Date: Friday, Sept. 24, start of lab session (12:50 p.m.)

Objectives

• To learn how to read EBNF and syntax diagrams.
• To understand the connection between a grammar and a language.
• To understand the difference between context-sensitive, context-free and regular grammars and languages.

Exercises

1. Given the following EBNF declarations (based on Modula-2)

   <simple expression> ::= [ + | - ] <term> { + <term> | - <term> | OR <term> }^*

   <term> ::= <factor> { * <factor> | / <factor> | DIV <factor> | MOD <factor> | AND <factor> | & <factor> }^*

   <factor> ::= <number> | <ident> | (<simple expression>) | NOT<factor>

   <ident> ::= <letter> { <letter> | <digit> }^*

   simplify the expressions for <simple expression> and <term> by adding other nonterminal definitions so that you can reduce the number of options in the braces.

2. Construct five examples of a <simple expression>, using only terminals in the language. Try to make each example significantly different from the others so as to illustrate the range of expressions which this definition encompasses. Assume simple definitions for <letter> (i.e., a..z, A..Z), <digit> (i.e., 0..9), and <number> (i.e., <digit>⁺) [although the actual definitions in Modula-2 are more complex].

3. Draw a set of syntax diagrams which are equivalent to the following EBNF declarations. Note that the vertical bar inside the braces in the first clause is a terminal in the language, not EBNF's symbol for 'or'. Following the practice used in several programming language reference books, I have enclosed non-alphabetic symbols ('|', ':', ',', and '..') in single quotation marks to indicate clearly that they are terminal symbols; omit the single quotation marks when drawing your syntax diagrams. (I have also specified boldface rendering, but this may or may not be visible in all browsers.) You only need to provide diagrams for the non-terminals on the left-hand side of each definition below; you may assume that all other non-terminals which may be used on the right-hand sides of the definitions are defined elsewhere.

   <case statement> ::= CASE <expression> OF <case> { '|' <case> }^* [ ELSE <statement sequence> ] END

   <case> ::= [ <case label list> ':' <statement sequence> ]

   <case label list> ::= <case label> { ',' <case label> }^*

   <case label> ::= <const expr> [ '..' <const expr> ]

   
   
   

4. According to the EBNF definitions given in the previous exercise, indicate whether each of the following examples is or is not a legal case statement. For those that are not, explain why they are illegal according to the grammar. Assume that integers and single characters enclosed in single quotation marks are constant expressions (i.e., <const expr>), that a variable name qualifies as an <expression>, that a <statement sequence> is a sequence of semicolon-separated statements, and that a procedure call (indicated by a simple identifier, not followed by parentheses) and an assignment statement (where':=' is the assignment operator) are examples of statements. Also, 'DIV' is a legal division operator in this example language (Modula-2).

   1. CASE nextChar OF
        'a' : ScanIdentifier |
        'b' : ScanIdentifier;
              bold := 1 |
        '0' : ScanNumber
      ELSE Error
      END
      

   2. CASE nextChar OF
        'a' .. 'z' : ScanIdentifier
      ELSE
        '0' .. '1' : ScanNumber
      END
      

   3. CASE nextChar OF
        'a' .. 'z' : ScanIdentifier
      ELSE
        ScanNumber
      ELSE
        ScanOperator
      END
      

   4. CASE nextChar OF
        'a' .. 'z', 'A' .. 'Z' : ScanIdentifier |
        '0' .. '9' : ScanNumber |
        '+', '-', '*', '/', '^' : ScanOperator |
      END
      

   5. CASE nextChar OF
        'a', 'b', 'c', .. 'z' : ScanIdentifier |
        '0' .. '9' : ScanNumber |
        '+', '-', '*', '/', '^' : ScanOperator
      END
      

   6. CASE op OF
      | '+' : total := total + operand
      | '-' : total := total - operand
      | '*' : total := total * operand
      | '/' : total := total DIV operand
      END
      

   7. CASE op1, op2 OF
        '+' : total := total + operand |
        '-' : total := total - operand |
        '*' : total := total * operand |
        '/' : total := total DIV operand |
      END
      

   8. CASE ident OF
      END
      

   
   
   

5. In the lecture notes on The Chomsky Hierarchy of Languages, we point out that the "balanced parentheses" language defined by

   <expression> ::= <balanced>*
<balanced> ::= (<expression>)

   is a context-free language because it requires a recursive grammar to define it.

   Revise the grammar to make the "balanced parentheses" language a regular language by restricting the level to which pairs of balanced parentheses may be nested to 3.

Submission

Hand in a hardcopy of your assignment solutions. Hand-drawn syntax diagrams and hand-written or -printed answers are acceptable (and encouraged, to save you time), but please ensure that all answers are clearly legible.