CODEWITHSUNDEEP
grammarpostfix-notation
Pat K
Pat K

Reputation: 321

Postfix -> Evaluate in terms of grammar (conceptual)

String: 

ab/c*efg*h/+d-+

Postfix grammar:

<postfix> = <identifier> | <postfix><postfix><operator>
<operator> = + | - | * | /
<identifier> = a | b | ... | z

Questions:

Is the string above a valid postfix expression? Explain in terms of GRAMMAR FOR POSTFIX expressions.

No this isn't a graded assignment. Yes this is from a book. I'm looking for a conceptual answer to the problem not necessarily code. How do I look at the grammar, and evaluate the string for a match?

Upvotes: 0

Views: 393

Answers (1)

rici
rici

Reputation: 241881

How do I look at the grammar, and evaluate the string for a match?

In other words, "how do I parse the string using the grammar?", right?

The easiest way is with an oracular parser; that is, a parser which can just consult an oracle and decide which production to reduce.

Parsing is the inverse of derivation. If we can derive the string from the start symbol, then we can reverse the procedure to construct a parse tree from the string. Having a reliable oracle handy makes it easy to go either way. So let's produce the rightmost derivation. Recall that in a rightmost derivation, it is always the rightmost non-terminal which gets expanded.

(For compactness I represented non-terminals as capital letters P, O and I. I also right-aligned the strings so you can see what the "corresponding character" is more easily.):

              P   P => P P O
            PPO   O => +
            PP+   P => P P O
          PPPO+   O => -
          PPP-+   P => I
          PPI-+   I => d
          PPd-+   P => P P O
        PPPOd-+   O => +
        PPP+d-+   P => P P O
      PPPPO+d-+   O => /
      PPPP/+d-+   P => I
      PPPI/+d-+   I => h
      PPPh/+d-+   P => P P O
    PPPPOh/+d-+   O => *
    PPPP*h/+d-+   P => I
    PPPI*h/+d-+   I => g
    PPPg*h/+d-+   P => I
    PPIg*h/+d-+   I => f
    PPfg*h/+d-+   P => I
    PIfg*h/+d-+   I => e
    Pefg*h/+d-+   P => P P O
  PPOefg*h/+d-+   O => *
  PP*efg*h/+d-+   P => I
  PI*efg*h/+d-+   I => c
  Pc*efg*h/+d-+   P => P P O
PPOc*efg*h/+d-+   O => /
PP/c*efg*h/+d-+   P => I
PI/c*efg*h/+d-+   I => b
Pb/c*efg*h/+d-+   P => I
Ib/c*efg*h/+d-+   I => a
ab/c*efg*h/+d-+

So how did the oracle figure out what to say? Well, if the rightmost non-terminal is <operator> or <identifier>, it just needs to take a look at the corresponding character of the target string to see what the expansion will be. If the rightmost non-terminal is <postfix>, then there are two possibilities: <postfix> => <postfix> <postfix> <operator> and <postfix> => <identifier>. The corresponding character of the target string will then line up with either the <operator> or the <identifier> non-terminal, so it's really easy to know which of the two possible productions will be able to continue. And that's precisely how I produced the derivation, using a tiny Lua program as my oracle.

Now, what happens if we actually need to go forward, starting with the string and ending up with the single non-terminal <postfix>? Well, we just have to reverse our steps. If we are looking at a letter, we will need to derive it from <identifier>, and then immediately derive that identifier from <postfix>. If we are looking at an operator, we will need to derive it from <operator>, and then immediately derive the last two <postfix> plus the operator to a new <postfix>.

Is that conceptual enough?

Upvotes: 1

Related Questions