1
$\begingroup$

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?

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

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).

$\endgroup$
  • $\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$ – Rajesh R Dec 7 '17 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$ – Amaury Pouly Dec 7 '17 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$ – Rajesh R Dec 7 '17 at 9:34

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.