I am reading dragon book for compilers. I am not able to understand in which phase does syntax directed translation actually happen.

A CFG can have set of semantic rules attached to it which is evaluated. For example, we can have semantic rules attached to a CFG which adds the type of identifier in the symbol table. Does it happen in syntax analysis or semantic analysis phase?

  • $\begingroup$ Can anyone answer please? $\endgroup$
    – Ramesh
    Commented Dec 6, 2017 at 15:43
  • $\begingroup$ Please be patient. It may take some time for people to see your question. Thank you. $\endgroup$
    – D.W.
    Commented Dec 6, 2017 at 17:13
  • $\begingroup$ I asked it again so that my question doesn't get lost. $\endgroup$
    – Ramesh
    Commented Dec 6, 2017 at 18:20

1 Answer 1


I do not have the dragon book with me so my answer may be off. But generally speaking the syntax directed translation means that you start with a sequence of token (so right after the lexer) and produce something. The translation is said to be directed by the syntax because the something must be produced in a very specific way. For each grammar rule, the translation defines the translation of the left-hand-side nonterminal as a function of the right-hand-side nonterminals' translations, and the values of the right-hand-side terminals.

Here is an example. If you have the following grammar rule: $$stmt \rightarrow\boldsymbol{if}(expr)\text{ }stmt\text{ }\text{ }\boldsymbol{else}\text{ }stmt$$ And if we denote by $[\cdot]$ the translation then the above rule generates the translation rule $$[\boldsymbol{if}(e)\text{ }s_1\text{ }\text{ }\boldsymbol{else}\text{ }s_2]=T_{if}([e],[s_1],[s_2])$$ where $T_{if}$ if the translation action for this rule.

One obvious use of SDT is to generate the AST of the input. In which case $T_{if}$ would look something like (I use ML-like syntax) $$T_{if}(e,s_1,s_2)=AstIfNode(e,s_1,s_2).$$ But they are other possibilities. Furthermore, it is possible to generate an AST with attributes so that we can perform semantic analysis at the same time. For example if we have the rule $$expr\rightarrow expr\boldsymbol{+}expr$$ then a translation for a "calculator-like" language could be $$T_{+}(e_1,e_2)=\begin{cases}\{type=int,val=e_1.val+e_2.val\}&\text{if }e_1.type=int\text{ and }e_1.type=int\\\{type=error\}&\text{otherwise}\end{cases}$$

If we start to have identifiers, then we can attach a symbol table to the nodes. For a simple language you can build an entire compiler with a SDT (one-pass compiler), going from source code to machine code. But more advanced compilers usually just use SDT to produce an AST and then do more complicated things (notably they modify the AST).

  • $\begingroup$ So my example which is adding type of identifiers in the symbol table happens in syntax analysis phase with the help of semantic actions ? Then why do we do type checking (which is executing the action next to CFG) in semantic analysis phase ? It can be done in syntax analysis phase itself right? $\endgroup$
    – Ramesh
    Commented Dec 7, 2017 at 5:58
  • $\begingroup$ Yes we can do the entire semantic analysis in this phase if we want (including type checking). But it is not considered good practice to mix those different phases because they do vastly different things and doing everything at once makes the code too complicated. Also one cannot really do optimizations in SDT. $\endgroup$ Commented Dec 7, 2017 at 9:23
  • $\begingroup$ Ok. I think we cannot make a clear distinction of whether SDT takes place in syntax analysis or semantic analysis phase and that's the reason book doesn't clearly state this. $\endgroup$
    – Ramesh
    Commented Dec 7, 2017 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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