Reference Book:
Compilers: Principles, Techniques and Tools
Syntax Directed Translation is a grammar oriented compilation technique in which the source program is translated by attaching its fragments to the productions of the grammar. The fragments or programming constructs are called attributes and the process of associating these attributes to the grammar productions is called syntax directed translation scheme.
Parsing is the method of generating the sequence in which a set of production rules of the given grammar are to be applied to construct the input string. Basically, parsing means analysing how the input string is generated by our grammar. This procedure requires the construction of parse tree.
Any context free grammar can be parsed in cubic (O(n3)) time. However, most programming languages today can be parsed in linear time only. Input of a parser,i.e., the attributes (or fragments / characters of the source program) are scanned from left to right. The output of the parser, i.e., the parse tree can be constructed either in top-down or bottom-up fashion. Top-down parsing is easy to visualize, while bottom-up parsing can handle a larger class of grammars and translation schemes.
Different types of Languages Index Role of Lexical Analyzer
