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

Homework 2 (Due: 23 June (Tuesday); Late submission by 26 June (Friday))

1. [DERIVATION AND PARSE TREE]
   Consider the following grammar for "Datalog Atoms" from Homework 1:

   atom : NAME LPAREN args RPAREN  
     
   args : args COMMA arg  
   args : arg  
     
   arg  : NUMBER  
   arg  : STRING  
   arg  : NAME
   

   Write a "left-most" derivation for p(x,20,x,y,"john") and draw the parse tree.

2. [GRAMMAR]
   A JSON expression is one of four types:
   1. STRING
   2. NUMBER
   3. JSON object, which starts with a left brace (LBRACE), followed by a list of key-value pairs separated by COMMAs and ends with a right brace (RBRACE). The key-value pair has a COLON between the key and the value. The keys are STRINGS enclosed within double-quotes and values can be any JSON expression.
   4. JSON array, which starts with a left bracket (LBRACKET), followed by a list of JSON expresssions separated by COMMAs, and ends with a right bracket (RBRACKET).
   Some examples of JSON expressions are:

   25
   
   "jones"
   
   [20, 30, 40]
   
   [20,"jones",22]
   
   [{"a" : 20},{"b": 30}]
   
   { "name" : "John",
     "age" : 23,
     "address" : { "street" : "123 main street",
                   "city"   : "Atlanta",
                   "state"  : "Georgia",
                   "zip"    : "30303"
                 },
     "phone" : ["111-1234","111-1235"]
   }
   

   Write a context-free grammar for JSON expressions. Then, input the grammar rules into PLY programs (Lexer, Parser, and Main) and test this. Include the SEMI token at the end of the JSON expression, read from terminal, and call the parse() method. You need not construct a data structure - so you simply do not include the assignment statement that assigns a value into p[0]! However, for the start rule, include the assignment statement that assigns True to p[0]. This way you can check for return value and print a "VALID" or "INVALID" message. Use the main program JSON.py. A sample run is shown below:

   macbook-pro:json raj$ python3 JSON.py
   JSON: 45;
   VALID
   JSON: "jones";
   VALID
   JSON: [1,2,3];
   VALID
   JSON: [1,"jones",3];
   VALID
   JSON: {"a":2, "b":5};
   VALID
   JSON: { "street" : "123 main street", "city"   : "Atlanta", "state"  : "Georgia", "zip"    : "30303" };
   VALID
   JSON: [{"a":10},{"b":20}];
   VALID
   JSON: {"a": [1,2,3], "b": [3,4,5]};
   VALID
   JSON: [1,2,,];
   Syntax error in input!
   INVALID
   JSON: {1,2,3};
   Syntax error in input!
   INVALID
   JSON: exit;
   

3. [ATTRIBUTE GRAMMARS]
   Consider the WAE grammar from Week 1 lectures:

   waeStart : wae SEMI
   wae : NUMBER
   wae : ID
   wae : LBRACE PLUS wae wae RBRACE
   wae : LBRACE MINUS wae wae RBRACE
   wae : LBRACE TIMES wae wae RBRACE
   wae : LBRACE DIV wae wae RBRACE
   wae : LBRACE IF wae wae wae RBRACE
   wae : LBRACE WITH LBRACE alist RBRACE wae RBRACE
   alist : LBRACE ID wae RBRACE
   alist : LBRACE ID wae RBRACE alist
   

   Solve the following two problems independently (i.e. the first attribute grammar may accept what the second attribute grammar rejects and vice versa):
   1. Augment this grammar with attributes, attribute computation functions, and predicates to reject WAE expressions which contain WITH sub-expressions with duplicate variable names in their alist. For example, the following WAE expression should be rejected:

      { + 20 {with {{x 2} {y 4} {x 5}} {+ x y}}}
      

      Note that the WITH sub-expression contains two occurrences of the variable x.
   2. Augment this grammar with attributes, attribute computation functions, and predicates to reject WAE expressions that cannot be evaluated due to the fact that variables do not have a value. For example, the following WAE expression should be rejected:

      { + 20 {with {{x 2} {y 4}} {+ x z}}}
      

      Note that the variable z does not have a value when you try to evaluate it. HINT: Keep track of "free variables" at each node of the parse tree. A free variable in a sub-expression is one for which there is no value in an outer WITH expression.
   3. Implement both of these attribute grammars in PLY. Modify the code in WAE Code by replacing the third line in each parser function by appropriately assigning values into p[0] to make the checks. The final value returned by the parse() method should be a boolean value, True for accept and False for reject. Use WAE1.py and WAE2.py for the main programs for these two problems.
   Here are the sample runs for the two programs:

   macbook-pro:with-repeat raj$ python3 WAE1.py
   WAE: 3;
   ACCEPT: No Repeated With-Vars
   WAE: x;
   ACCEPT: No Repeated With-Vars
   WAE: {+ 2 3};
   ACCEPT: No Repeated With-Vars
   WAE: {with {{x 3}{y 4}} {+ x y}};
   ACCEPT: No Repeated With-Vars
   WAE: {with {{x 3}{x 4}} {+ x y}};
   REJECT: Repeated With-Vars
   WAE: exit;
   
   macbook-pro:cannot-evaluate raj$ python3 WAE2.py 
   WAE: 5;
   ACCEPT: CAN EVALUATE
   WAE: x;
   REJECT: CANNOT EVALUATE
   WAE: {+ 2 x};
   REJECT: CANNOT EVALUATE
   WAE: {+ 2 3};
   ACCEPT: CAN EVALUATE
   WAE: {+ 2 {with {{x 1}{y 2}} {+ x y}}};
   ACCEPT: CAN EVALUATE
   WAE: {+ 2 {with {{x 1}{y 2}} {+ x z}}};
   REJECT: CANNOT EVALUATE
   WAE: exit;
   

4. [DENOTATIONAL SEMANTICS]
   Assume that you are given the following two denotational functions:
   • M_B(bool,s), a denotational function that defines the meaning of Boolean expression, bool (maps to True, False, or error)
   • M_S(stmt,s), a denotational function that defines the meaning of a single statement, stmt (maps to a new state resulting from the execution of the stmt).
   Consider the following grammar rules that define if-then-else and stmt-list:

     if-then-else : IF bool THEN stmt-list ELSE stmt-list 
   
     stmt-list : stmt
     stmt-list : stmt SEMI stmt-list
   

   Complete the denotational function definitions for if-then-else and stmt-list:

   M_C(if-then-else,s) =

   M_SL(stmt-list,s) =