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)))));
- Write a "left-most" derivation for (* (car (2 4 (+ 2 4) 8)) (/ 27 9));
- 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) ) ;
- 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
- 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
- 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.
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
- 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
-
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.