Reference no: EM133660834

Compiler design subject

Part 1:

Question: 1

Recursive Descent

Prolog programs consist of a list of clauses and the grammar for a clause is the following where the terminals are

"," "(" ")" and ":-."

and we also let "x" denote the token for identifiers.

Clause -> Pred :- Body

Body -> Pred Body1
Body1 -> , Pred Body1

Body1 -> epsilon
Pred -> x ( Terms )

Terms -> Term Terms1

Terms1 -> , Term Terms1

Terms1 -> epsilon

Term -> x M

M -> (Terms)
M -> epsilon
S -> P

Question 2:  Find the firsts and follows for each non-terminal C,P,B,B1,T, T1, S where the terminals are:- , ( ) x

2) create the LL1 parsing table for this language and determine if this grammar can be used to parse Prolog by using Recursive Descent.

3) draw a parse tree for the following clause, where the identifiers, sibling, parent_child, X,Y, Z are all tokens of type "X"

sibling(X, Y) :- parent_child(Z, X), parent_child(Z, Y).

(Prolog programs consist of a set of logic statements, this one says the X and Y are siblings if they have a common parent, Z.)

Part 2:

Firsts and Follows-3

Consider the following grammar where P is the start symbol and the terminals are {$,a,b,c,d} and epsilon is the empty string.
P -> S $
S -> E T b
T -> a E F
T -> epsilon
E -> c
F -> d
F -> epsilon
For each non-terminal N (in P,S,T,E,F) find the First set and Follow set for N, that is
1) what are all of the terminals that can begin a string derived from N and
2) what are all the terminals that can follow N in a derivation from the start symbol, P.

Part 3: Draw this NFA.

RE2NFA-3

Convert the following Regular Expression into an NFA:

(a|b)* | (a|c* | (b|c)*

which is the language of a, b, c sequences which only have two of the three letters appearing. Don't try to optimize the NFA.

Submit your answer below along with a short movie explaining how you got your answer and why it is correct.