CSc 4330/6330 Programming Language Concepts

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

Homework 3 (Due: 25 February (Tuesday))

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