Average length of stack in parsing LR(1)

Question

Consider the following grammar:

$S \rightarrow A$

$S \rightarrow xb$

$A \rightarrow aAb$

$A \rightarrow B$

$B \rightarrow x$

The average length of the stack used while parsing the string "axb$" using LR(1) parser is _________.

I am getting 5, but answer is 2.5.

Comments

[edit]

*****considered reduction only parsing need complete calculation*****

Thanks!

---

don't we need to push DFA state number along with symbol?

---

I'm getting 2.5
My stack lengths are
(1 + 2 + 3 + 3 + 3 + 4 + 2 + 2) /8 = 2.5

Try to pop same number of symbols which are on RHS of reduced state.

---

@Ashwin I am agree with you. But don,t we need to push the DFA's state number also, so that the parser when parsing the string get to know to which state it has to go.

Like, at initial the stack content is:

dollar | 0

and input buffer is axb$, and on seeing a on state 0 we have to push a, and also push the next state number from the LR(1) parsing tBle.

---

can u plz explain me on a piece of paper?

---

First of all we need table of this grammar through dfa ,after construction of dfa table will be,

 in stack dfa state no. Also be placed .so average length should be ,- $\frac{1+3+5+5+5+7+3+3}{8}$=4.i think 4 should be answer.