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

Homework 3a (Due: 16 February (Friday))

Handin under Assignment 3a
  1. 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.

  2. 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:
    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.

  3. 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.