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

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

**Handin under Assignment 3a**

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

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

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