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.
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).
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...
#1 We are given the grammar rules A ➝ F B E B ➝ A C...
#1 We are given the grammar rules A ➝ F B E B ➝ A C These rules are only some of the rules of a larger grammar G, but we are not given the remaining rules of G. We are told that A is the start symbol of G and that the following holds: {ε, c, d} ⊆ FIRST(C) {ε, e} ⊆ FIRST(E) {ε, f, g} ⊆ FIRST(F) Recall that end of file is denoted EOF. The symbol ⊆...
(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))  
For the following functions f and g : f(x, y) = e^ax − (1 − a)lny...
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 (x, y) define positivly...
The position vector F(t) of a moving particle at time t[s] is given by F(t)= e^t...
The position vector F(t) of a moving particle at time t[s] is given by F(t)= e^t sin(t)i-j+e^t cos(t)k a) Calculate the acceleration a(t). b) Find the distance traveled by the particle at time t = 3π/2, if the particle starts its motion at time t = π/2. c) Find the unit tangent vector of this particle at time t = 3π/2. d) Find the curvature of the path of this particle at time t = 3π/2.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT