CSc 4330/6330 Programming Language Concepts

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