Exercise 1: Describe, in English, the language defined by the following grammar :

<S> ::= a <A> b | ab | a <B> b
<A> ::= a | a <B> | a <A>
<B> ::= b | b <A> | b <B>

Answer: All strings over the alphabet {a,b} that start with 'a' and end with 'b'.

Exercise 2: Which of the following sentences are in the following grammar:

<S> ::= a <S> c <B>

<S> ::= <A> | b

<A> ::= c <A> | c

<B> ::= d | <A>

1. abcd       Yes 

2. acccbd     No

3. acccbcc    No 

4. acd        No 

Exercise 3: Give an example of a static property of a program and an example of a dynamic property of a program.

Answer: The types for the identifiers are usually a static property and the final result that the program computes is dynamic property.

Exercise 4: Give an example of a programming language that is typically interpreted and a programming language that is typically compiled.

Answer: Perl and BASIC are interpreted. C and Pascal are compiled.

Exercise 5: Rewrite the following EBNF grammar in BNF.

         <decl> ::= <ident_list> : (int | float | char);
         <ident_list> ::= <identifier>{,<identifier}
        

Answer:

<decl> ::= <ident_list> : int;
<decl> ::= <ident_list> : float;
<decl> ::= <ident_list> : char;
<ident_list> ::= <identifier> | <identifier> ,<ident_list>