Question

In: Computer Science

Consider the following grammar G: E -> E + T | T T -> T F...

Consider the following grammar G:
E -> E + T | T
T -> T F | F
F -> F* | a | b

This grammar can be used to generate regular expressions over the alphabet {a,b} with standard precedence rules.
Show your solution for each of the following 5 points:

    1. Remove left recursion and write the resulting grammar G1.
    2. For the grammar G1, compute and write the sets FIRST for every right hand side of every production,
       and the sets FOLLOW for every left hand side (i.e. any non-terminal).
    3. Find and write the table for a predictive parser
    4. Is G1 LL(1)? Justify your answer.
    5. If the answer to (4) above is yes, then trace parsing of: a* + ab*

Solutions

Expert Solution

1) Left Recursive Grammar leads to unterminated state. and the grammar is look like as follows

A ---> Aα/β (here A is repeated contineously)

for example consider this , above line can be look like this...

A(){

A() // this leads to unterminated condition

  α

}

>>> In order to remove left recursion the grammar which is in the form A ---> Aα/β will be converted to following form.

A ---> βA'

A' ---> ε/αA'

>>> We need to identify what is alfa and what is beta and just replace it in the original form.

>>> after I have done all that the converted grammar is as follows.

E ---> TE'

E' ---> ε/+TE'

T ---> FT'

T' ---> ε/FT'

F ---> aF'/bF' (here we have two beta's)

F' ---> ε/*

2)Follow sets are

First(E) = {a,b}, First(E') = {ε,+}, First(T) = {a,b}, First(T') = {ε,a,b}, First(F) = {a,b}, First(F') = {ε,*}.

Follow(E) = {$} and follow of all other variables also is {$}.

3)

4)yes it is LL(1)

5)


Related Solutions

Give the grammar following: E --> E + T | T T --> T* F |...
Give the grammar following: E --> E + T | T T --> T* F | F F --> (E) | id Eliminating the left recursion rules and getting a non-left recursive equivalent grammar.
Consider the following context-free grammar G: E ® T + E ® * T i E...
Consider the following context-free grammar G: E ® T + E ® * T i E ® f i E ® * f + T ® + Questions: (5 points) Compute the Canonical LR(1) Closure set for state I0 for grammar G. (10 points) Compute (draw) the DFA that recognizes the Canonical LR(1) sets of items for grammar G. (5 points) Construct the corresponding Canonical LR(1) parsing table. (10 points) Compute (draw) the DFA for LALR(1). (5 points) Construct LALR(1)...
Let f(t) =t^2−1 and g(t) =e^t. (a) Graph f(g(t)) and g(f(t)). (b) Which is larger,f(g(5)) or...
Let f(t) =t^2−1 and g(t) =e^t. (a) Graph f(g(t)) and g(f(t)). (b) Which is larger,f(g(5)) or g(f(5))? Justify your answer. (c) Which is larger, (f(g(5)))′or g(f(5))′? Justify your answer.
Find Consider the following context-free grammar G: S --> T#T T --> C A --> aA...
Find Consider the following context-free grammar G: S --> T#T T --> C A --> aA | epsilon B --> bB | epsilon C --> cC C --> c a) Give the set of unproductive symbols in G? b) Give an equivalent grammar without useless symbols.
E ::= E + T | T T ::= T * F | F F ::=...
E ::= E + T | T T ::= T * F | F F ::= num | (E) Num ::= 0 | 1 | 2 | 3 | 4 | 5 | . . . . . . . Question: 1 a. Show the Left-most derivation for the expression: 5 * 7 + 6 * (1 + 2). b. Show the Right-most derivation for the expression: 5 * 7 + 6 * (1 + 2).
Problem 3. Let G be the grammar we saw in homework 3: E -> E +...
Problem 3. Let G be the grammar we saw in homework 3: E -> E + T | E - T | T T -> T * F | F F -> ( E ) | x | y Let w be (x + y) * x - y a) Show the leftmost derivation for w in G. Number the rules for G and show the corresponding rule number under each substitution arrow in the derivation. Hint: it may be...
Consider the following relational schema and set of functional dependencies. S(A,B,C,D,E,F,G) D → E E →...
Consider the following relational schema and set of functional dependencies. S(A,B,C,D,E,F,G) D → E E → B C → FG BE → AC Is the decomposition of S into S1(E,G,F) and S2(A,B,C,D,G) a lossless join decomposition? Choose one of the following queries as your answer: SELECT ’lossy’; SELECT ’lossless’;
Consider the reaction, 2 D(g) + 3 E(g) + F(g) => 2 G(g) + H(g) When...
Consider the reaction, 2 D(g) + 3 E(g) + F(g) => 2 G(g) + H(g) When H is increasing at 0.85 mol/Ls, how quickly is F decreasing?
For the following functions f and g : f(x, y) = e ax − (1 −...
For the following functions f and g : f(x, y) = e ax − (1 − a)lny a > 0 g(x, y, z) = −3x 2 − 3y 2 − 3z 2 + 2xy + 2xz + 2yz 1. Calculate the Hessian matrices of f and g noted Hf (x, y) and Hg(x, y, z) 2. Show that Hg(x, y, z) is define negativly for all (x, y, z) ∈ Dg 3. For what value o a is , Hf...
(a) (f ∘ g)(3) (b) g(f(2)) (c) g(f(5)) (d) (f ∘ g)(−3) (e) (g ∘ f)(−1) (f) f(g(−1))
(a)    (f ∘ g)(3) (b)    g(f(2)) (c)    g(f(5)) (d)    (f ∘ g)(−3) (e)    (g ∘ f)(−1) (f)    f(g(−1))  
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT