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

Homework 3 (Due: 25 February (Tuesday))

  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));

    SOLUTION:

    lisp => num ;
         => ( * num num ) ;
         => ( * (CAR list) num ) ;
         => ( * (CAR ( seq )) num ) ;
         => ( * (CAR ( seq num )) num ) ;
         => ( * (CAR ( seq num num )) num ) ;
         => ( * (CAR ( seq num num num )) num ) ;
         => ( * (CAR ( num num num num )) num ) ;
         => ( * (CAR ( 2 num num num )) num ) ;
         => ( * (CAR ( 2 4 num num )) num ) ;
         => ( * (CAR ( 2 4 (+ num num) num )) num ) ;
         => ( * (CAR ( 2 4 (+ 2 num) num )) num ) ;
         => ( * (CAR ( 2 4 (+ 2 4) num )) num ) ;
         => ( * (CAR ( 2 4 (+ 2 4) 8 )) num ) ;
         => ( * (CAR ( 2 4 (+ 2 4) 8 )) (/ num num) ) ;
         => ( * (CAR ( 2 4 (+ 2 4) 8 )) (/ 27 num) ) ;
         => ( * (CAR ( 2 4 (+ 2 4) 8 )) (/ 27 9) ) ;
    

  2. Write a context-free grammar for "Datalog Rules". A Datalog rule is of the form:
    p :- q1, ..., qn.
    
    where n>0 and p, q1, ..., and qn are atomic formulas of the form:
    r(x1, ..., xm)
    
    where m>0 and r is a relation name and x1 , ..., xm are either numbers or variables. Relation names and variables are made up of lower-case alphabetic letters or digits and start with a lower-case alphabetic letter. Numbers are positive integers or zero. Some examples of Datalog rules are:
    ancestor(x1,y1) :- parent(x1,y1).
    teaches(tno,cno) :- faculty(tno), course(cno), assigned(tno,cno).
    p(x,y) :- q(2,x), r(y,45,z), s(a,b,22).
    

    SOLUTION:

    datalog : atom IF atomlist DOT
    atom : NAME LPAREN args RPAREN
    args : arg
    args : args COMMA arg
    arg : NUMBER
    arg : NAME
    atomlist : atom
    atomlist : atomlist COMMA atom
    
  3. 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;
    

    SOLUTION:

    vars : dtype varlist SEMI
    dtype : INT
    dtype : INTARRAY
    varlist : var
    varlist : varlist COMMA var
    var : NAME
    var : NAME EQUALS value
    value : NUMBER
    value : LBRACE numlist RBRACE
    numlist : NUMBER
    numlist : numlist COMMA NUMBER
    
  4. Consider the alphabet {a, b, c} and the language over this alphabet consisting of strings with the following properties:
    • a's appear before b's and b's appear before c's, and
    • the number of a's, b's, and c's are equal.
    Examples of strings in the language are aaabbbccc, aabbcc, abc, etc. Write an attribute grammar for this language. You will solve this problem in 2 steps:
    • Step 1: Write a context free grammar for the language in which the a's appear before b's and the b's appear before c's. This grammar need not consider the second condition that the number of a's, b's, and c's are equal (In fact it is impossible to construct a context free grammar to satisfy the second condition).
    • Step 2: Introduce attributes for non-terminals in your grammar and define the attribute computation functions and predicates to enforce the second condition.

    SOLUTION:

    Step 1: Grammar for a*b*c*
    
    S : A B C
    A : A a
    A : ε
    B : B b
    B : ε
    C : C c
    C : ε
    
    Step 2: Attribute grammar
    
    Introduce synthesized attribute "count" for non-terminals A, B, and C.
    
    Syntax Rule: S : A B C
    Predicate: A.count == B.count and B.count = C.count
    
    Syntax Rule: A : A a
    Semantic Rule: A[0].count = 1 + A[1].count
    
    Syntax Rule: A : a
    Semantic Rule: A[0].count = 1
    
    Syntax Rule: B : B b
    Semantic Rule: B[0].count = 1 + B[1].count
    
    Syntax Rule: B : b
    Semantic Rule: B[0].count = 1
    
    Syntax Rule: C : C c
    Semantic Rule: C[0].count = 1 + C[1].count
    
    Syntax Rule: C : c
    Semantic Rule: C[0].count = 1
    

  5. Consider the following grammar:
    btree : NIL | LPAREN btree COMMA value COMMA btree RPAREN
    value : digit | digit value
    digit : 0|1|2|3|4|5|6|7|8|9
    
    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.

    SOLUTION:

    Introduce synthesized attribute "height" for non-terminal btree.
    
    Syntax Rule: btree : NIL
    Semantic Rule: btree[0].height = -1
    Predicate: True
    
    Syntax Rule: btree : LPAREN btree COMMA value COMMA btree RPAREN
    Semantic Rule: btree[0].height = 1 + max(btree[2].height,btree[6].height)
    Predicate: abs(btree[2].height - btree[6].height) <= 1
    

  6. Write denotational semantics for Boolean expressions defined in the following grammar:
    bool : TRUE | FALSE | var | boolExpr
    boolExpr : leftExpr bop rightExpr | NOT leftExpr
    leftExpr : TRUE | FALSE | var
    rightExpr : TRUE | FALSE | var
    bop : AND | OR
    
    You can assume that a VARMAP function is available that will contain boolean values for boolean variables. If variables have value undef the denotational semantics should return error.

    SOLUTION:

    Universe of objects: {True, False}
    
    Mb(bool,s) =
      case bool of
        TRUE     => True
        FALSE    => False
        var      => if (VARMAP(var,s)==undef) then error else VARMAP(var,s)
        boolExpr =>
           case boolExpr of
              leftExpr bop rightExpr => 
                 if Mb(leftExpr,s) == error or Mb(rightExpr,s) == error
                 then error
                 else if (bop == AND) then Mb(leftExpr,s) and Mb(rightExpr,s)
                 else Mb(leftExpr,s) or Mb(rightExpr,s)
              NOT leftExpr =>
                 if (Mb(leftExpr,s) == error) then error else not Mb(leftExpr,s)
    
    Mb(leftExpr,s) =
      case leftExpr of
        TRUE  => True
        FALSE => False
        var   => if VARMAP(var,s) == undef then error else VARMAP(var,s)
    
    Similar definition for Mb(rightExpr,s)
    
    Note: Here and, or, and not are boolean operators on boolean values True and False.