parsingbisonsemantic-analysis

Questions about Syntax Directed Translation and Bison Parser

I am confused between Syntax Directed Translation and parser written using Bison. (The main confusion is whether parser written in Bison already consists of syntax directed translator.)I rephrase the above sentence in parenthesis as (How does Bison implement Syntax Directed Translation, is it by attaching for E.g. $$ = $1 + $3)

This link says that

The C code in an action can refer to the semantic values of the components matched by the rule with the construct $n, which stands for the value of the nth component. The semantic value for the grouping being constructed is $$. (Bison translates both of these constructs into array element references when it copies the actions into the parser file.)

And also in chapter 5 (Syntax Directed Analysis) of the book says

Grammar + Semantic rules = Syntax Directed Translation

PRODUCTION          SEMANTIC RULE
šø ā†’šø1 + š‘‡          {šø.š‘š‘œš‘‘š‘’ = šø1.š‘š‘œš‘‘š‘’ ā”¤| š‘‡.š‘š‘œš‘‘š‘’ |ā€²+ā€²}

When looking at the following snippet of translation rules for a simple parser from the book Flex and Bison 

%%
E:  F default $$ = $1
        | E ADD F { $$ = $1 + $3; }
        | E SUB F { $$ = $1 - $3; }
    ;
%%

Is the .code equavelent to $$ I am so confused. Is syntax directed analysis the same as semantic analysis? The more I read more I get confused. Someone please help me sort this out.

Solution

  • Your understanding seems correct, but is confused by the fact that your example from the Dragon book and example parser are doing two different things -- the Dragon book is translating the expression into code, while the simple parser is evaluating the expression, not translating (so this is really syntax directed evaluation, not syntax directed translation).

    In the semantic rules described in the Dragon book, symbols can have multiple attributes, both synthesized and inherited. That's what the .code suffix means -- its an attribute of the symbols it is applied to. Bison on the other hand allows each symbol to have a single synthesized attribute -- no more, and no inherited attributes. If you want multiple attrbutes, you can gather them together into a struct and use that as your attribute (requires some careful management). If you want inherited attributes you can use $0 and even more careful management, or you can use globals to get the same effect.

    The bison snippet that would correspond to your Dragon book example snippet would be something like:

    E : E ADD F { $$ = AppendCode($1, $3, PLUS); }

    using the single bison attribute for the .code attribute and doing the append operation for the code being generated as a function.