Csc 4330/6330, Programming Language Concepts (Spring 2022)

Homework 3a (Due: 22 February (Tuesday))

(Late submission deadline: 23 February (Wednesday)

1. Consider the following grammar for "lisp" expressions:

   lisp : num SEMI
   
   num: NUMBER 
   num: LPAREN PLUS num num RPAREN
   num: LPAREN MINUS num num RPAREN
   num: LPAREN TIMES num num RPAREN
   num: LPAREN DIV num num RPAREN
   num: LPAREN CAR list RPAREN
   
   list: LPAREN seq RPAREN
   list: LPAREN CDR list RPAREN
   
   seq: num
   seq: seq num
   

   This grammar derives valid LISP expressions from the start non-terminal lisp. You may assume NUMBER token matches any number. Other tokens are self-explanatory and CAR and CDR are keywords. Some valid LISP expressions are shown below:

   34;
   (+ 20 30);
   (* (+ 1 2) (/ 8 4));
   (* (car (2 4 (+ 2 4) 8)) (/ 27 9));
   (+ (car (2 3 4)) (car (cdr (cdr (9 8 7 6)))));
   

   1. Write a "left-most" derivation for (* (car (2 4 (+ 2 4) 8)) (/ 27 9));
   2. Draw the parse tree for (* (car (2 4 (+ 2 4) 8)) (/ 27 9));

2. Prove that the following grammars are ambiguous (Note:In the following grammars, we have two terminal symbols, 'a' and 'b' and all non-terminal symbols are in upper-case letters, such as 'A' and 'S'. 'S' is the start symbol and ε is the empty string.):
   
   Grammar G1

   S -> SS
   S -> ab
   S -> ba
   S -> ε
   

   Grammar G2

   S -> AabaA
   A -> aA
   A -> bA
   A -> ε
   

   Grammar G3

   S -> aSb
   S -> bSa
   S -> SS
   S -> ε
   

3. Consider the following grammar:

   S -> aScB | A | b
   A -> cA | c
   B -> A | d
   

   Here again, we assume lower-case symbols such as a,b,c,d are terminals and upper-case symbols S, A, and B are non-terminals and S is the start symbol. Which of the following sentences are in the language generated by the grammar:
   1. abcd
   2. acccbd
   3. accbcc
   4. acd
   5. accc

4. Assume that you are tasked with the job of writing a context-free grammar for Java variable declarations. We shall limit the data types to be either int or int[], i.e. integer type or array of integer types. We shall assume that variables begin with a lower-case letter and may be followed by zero or more lower-case letters or digits. We shall also assume that integer constants are written with an optional sign (+ or -) and followed by a string of digits without leading zeroes. Write a Context-Free Grammar for strings that denote one declaration of variables of either integers or array of integers. For example, the following are some valid declarations of variables in Java:

   int x, y = -2, sum = 0;
   int[] scores = {10, 20, 30}, age;
   

5. Consider the following grammar for a binary tree data structure:

   btree : NIL
   btree : LPAREN btree COMMA NUMBER COMMA btree RPAREN
   

   Some examples of binary trees are:

   (NIL,12,NIL)
   ((NIL,12,NIL),20,(NIL,15,NIL))
   ((NIL,3,NIL),8,((NIL,12,NIL),20,(NIL,15,NIL)))
   

   Augment this grammar with attributes and the attribute computation functions and predicates to accept binary trees that are "balanced". A balanced binary tree is one in which the heights of the subtrees at each interior node are within one of each other.

6. Assume that you are given the following two denotational functions:
   • M_B(bool,s), a denotational function that defines the meaning of Boolean expression, bool (maps to True, False, or error)
   • M_S(stmt,s), a denotational function that defines the meaning of a single statement, stmt (maps to a new state resulting from the execution of the stmt).
   Consider the following grammar rules that define if-then-else and stmt-list:

     if-then-else : IF bool THEN stmt-list ELSE stmt-list 
   
     stmt-list : stmt
     stmt-list : stmt SEMI stmt-list
   

   Complete the denotational function definitions for if-then-else and stmt-list:

   M_C(if-then-else,s) =

   M_SL(stmt-list,s) =