Parser

Question

What is the meaning of reverse order for bottom up parsing use rightmost derivation in reverse order

Comments

is the sentence correct? i hope it is as  

either reverse order for bottom up parsing use rightmost derivation

or  bottom up parsing use rightmost derivation in reverse order

it means take a string derivation in Bottom-up parser.... note the steps in 1,2,3,4

now frame the steps in 4,3,2,1 ===> it is equivalent to right most derivation of a string.

---

Let the productions of a Grammar be

S->AA

A->aA

A->b

w=abab

We try to derive this string by rightmost derivation. The blue color indicates the non terminal being replaced and the green indicates the rhs of the production that replaces the blue non terminal.

S->AA 

AA->AaA

AaA-> Aab

Aab->aAab

aAab -> abab

Now in bottom up parsing we start from "abab" and not from that start symbol S. If we can reach the start symbol S by back tracking then the string is accepted.

Just trace back the above derivation(which is a right most derivation) from last to first [i.e. in the reverse order].

abab -> aAab ->Aab ->AaA ->AA ->S

We reach the starting Symbol. So abab is accepted by the language.

What we did above is we went in the reverse direction of the rightmost derivation. This is how bottom up parser works.