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

Homework 2 (Due: 7 February (Wednesday))

1. Prove that the following grammars are ambiguous (Note:In the following grammars, we have two terminal symbols, 'a' and 'b' and all non-terminal symbols are in upper-case letters, such as 'A' and 'S'. 'S' is the start symbol and ε is the empty string.):
   
   Grammar G1

   S -> SS
   S -> ab
   S -> ba
   S -> ε
   

   Grammar G2

   S -> AabaA
   A -> aA
   A -> bA
   A -> ε
   

   Grammar G3

   S -> aSb
   S -> bSa
   S -> SS
   S -> ε
   

2. Consider the following grammar:

   S -> aScB | A | b
   A -> cA | c
   B -> A | d
   

   Here again, we assume lower-case symbols such as a,b,c,d are terminals and upper-case symbols S, A, and B are non-terminals and S is the start symbol. Which of the following sentences are in the language generated by the grammar:
   1. abcd
   2. acccbd
   3. accbcc
   4. acd
   5. accc

3. Write ANTLR4 grammar and lexer rules 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 alphabetic letters or digits and start with a lower-case alphabetic letter. Numbers are positive integers or zero very much like numbers in the WAE example. 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).
   

   Put the grammar in a file, DLG.g4 and test it out.

4. Write a grammar for the language consisting of strings that have n copies of the letter a followed by the same number of copies of the letter b. For example, the strings ab, aaabbb, and aaaaabbbbb are in the language but aaabb, bbaa, and aba are not. Draw the parse tree for aaabbb.