parser

Question

What is the maximum number of reduce moves that can be taken by a bottom up parser for a grammar without epsilon and unit production (i.e., of type A →∈ and A →B ) to parse a string with n tokens?

1.   2n – 1
2.    2ⁿ
3.    n – 1
4.    n/2

Comments

is the given explanation correct as nowhere question ensures the grammar will be in  Chomsky normal form

As per the question there shall be no unit or epsilon production. Let us consider the following grammar:
S → PQ -------- (1)
P → p -------- (2)
Q → q -------- (3)
We shall be doing bottom-up parsing for the following string “pq”
pq ⇒ Pq -------- [using production 2]
⇒ PQ -------- [using production 3]
⇒ S -------- [using production 1]

For a string of length 2, the number of reductions is 3 which goes with the form 2n – 1 = 2 * 2 – 1 = 3

---

Yes Every derication of chomskey normal form  for string of n letters has exactly 2n-1 steps.

---

where in the question is given that grammar is in chomskey normal form  ?

G is said to be in Chomsky normal form if all of its production rules are of the form:

A → BC,   or

A → a,   or

S → ε,

---

we can take it like that " CYK algorithm is used in Bottom up parsing and CYK operates only on context free grammar and Context free grammar can be converted to CNF to have best result. "

Answer 1

Here they asked about max no of reduce moves and condition imposed is No epsilon or Unit production

So either we can have combination of terminals or nonterminalor both in RHS of production

For max no of reduce moves we need min no of entry at RHS

So in that case if we have two nonterminal or a terminal in RHS of production it needs maximum no of reduce move.

So the grammar should be in CNF form

So Max no of reduce moves=2n-1