In the following grammar that is used for math expressions(and other grammars) how do I know where should I place action symbols(@add, @mul, @pushID)? Is there a algorithm for it?

E -> TE`
E'-> +T @add E'|ϵ
T -> FT`
T'-> xF @mul T'|ϵ
F -> (E)|@pushID id

For example why @add is between +T and E' and not after E'? I searched for it's algorithm but didn't find anything useful.

  • $\begingroup$ What is the semantic of those actions in your parser generator? It looks like you create a prefix notation? $\endgroup$ – Raphael Jun 11 '12 at 10:41
  • $\begingroup$ I don't know if "formal grammars" have a defined action concept, but it looks like the ones you've mentioned apply the next term and perhaps some item(s) already on the stack and return something on the stack. If you have action items that do not process "forward" then they'd need to come at the end of the expression. $\endgroup$ – Mark Hurd Jun 15 '12 at 1:07

Generally, there isn't an algorithm for placing the action symbols. You always need logic in there.

In your case, you want to take the action @add right after you read the second operand of +. The derivations are leftmost, which means that the leftmost rules are going to be expanded and evaluated before the right rules. That said if you have an input of id1 + id2 * id3, the @add action symbol will be useful after id2 because up to then you have the two operands that you want to add. Exactly the same with the @mul, which is useful after id3.

Another issue is the precedence rules of the operations. We want multiplications execute before additions. The above example should be executed as id1 + (id2 * id3). Your grammar takes that into account :) . Let's see the syntax tree and I'm sure that will explain everything to you:

The parse tree for id1 + id2 * id3

Now you can see the actual sequence of the rules, the precedence of Multiplication and why the position of action symbols isn't something fixed.

In another grammar, somebody would first read the id and after that have an action symbol to take it into the symbol table (usually in programming languages like Fortran).

Don't hesitate to comment me if I did not cover you.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.