Prefix to infix translation

When we produced postfix, all the prints came at the end (so that the children were already printed. The { actions } do not need to come at the end. We illustrate this by producing infix arithmetic (ordinary) notation from a prefix source.

In prefix notation the operator comes first so +1-23 evaluates to zero and +-123 evaluates to 2. Consider the following grammar, which generates the simple language of prefix expressions consisting of addition and subtraction of digits between 1 and 3 without parentheses (prefix notation and postfix notation do not use parentheses).

  P → + P P | - P P | 1 | 2 | 3

The table below shows both the semantic actions and rules used by the translator. Normally, one does not use both actions and rules.

The resulting parse tree for +1-23 with the semantic actions attached is shown on the right. Note that the output language (infix notation) has parentheses. 

Prefix to infix translatorProduction with Semantic ActionSemantic RuleP → + { print('(') } P₁ { print(')+(') } P₂ { print(')') }P.t := '(' || P₁.t || ')+(' || P.t || ')'P → - { print('(') } P₁ { print(')-(') } P₂{ print(')') }P.t := '(' || P₁.t || ')-(' || P.t || ')'P → 1 { print('1') }P.t := '1'P → 2 { print('2') }P.t := '2'P → 3 { print('3') }P.t := '3'