Syntax Directed Definition for a grammar to print the parsing string

Question

---> Consider the grammar below:

  S->SaS|bB
  B->AcB| ε
  A->dAd| ε

For the grammar given above, write the syntax directed definition that prints the string that is being parsed and construct an annotated parse tree for the string ‘bddcab’.

Solution:

Now rewriting above grammar we have:

    S->S1aS2
    S->bB
    B->AcB1
    B-> ε
    A->dA1d
    A-> ε
   ( The numbers 1 and 2 following the non-terminal actually denote subscripts. And the subscripts in above grammar denote instances of the non-terminal.) 

The above grammar along with the semantic rules.

    Productions        Semantic Rules

    S->S1aS2        S.val=S1.val+a.lexval + S2.val { print S.val }
    S->bB           S.val=b.lexval + B.val { Print S.val}
    B->AcB1         B.val=A.val+c.lexval + B1.val
    B-> ε
    A->dA1d         A.val=d.lexval  + A1.val + d.lexval
    A-> ε

      ** The '+' operator is merely for concatenation.

Is this solution alright? I have a feeling that it might not be accurate.

Here's the annotated parse tree.

Answer 1

I think that those print actions in the S rules will backfire because S can occur multiple times.

S can generate SaS. But each of those S's can also generate SaS.

Basically, if you're building the printed representation as a semantic property, you can only do the print outside of the grammar once it is fully evaluated, ensuring that it happens only once.

This could be shown by introducing a pseudo start symbol X. S is reduced to X just once, and so the print happens just once, pulling the final val from the top-level S.

X -> S { print S.val }  // print the top-level S's val, just once.

The other approach would be to have truly syntax-directed printing, whereby the side effect of printing happens as the parsing reductions takes place. E.g. Yacc-like embedded rule among the right hand symbols:

S -> S1 a { print a.lexeme } S2 { /* other semantic rules go here */ }

In every rule that recognizes a terminal, print the terminal as soon as it is recognized. So here, we know that the reduction of S1 causes all of its terminals to be printed (by similar rules all over the grammar). Then we recognize an a and print it, and then S2 is recognized and reduced, causing all of its terminals to be printed. You may recognize that this is closely analogous to an inorder traversal of a tree.