Compilers

I am reading Compilers: Principles, Techniques, and Tools by Aho, Sethi, and Ullman.

Syntax - What the programs look like.

Semantics - What the programs mean.

Context-Free Grammar

if (expression) statement else statement

stmt -> if (expr) stmt else stmt

1. Set of tokens called terminal symbols. (Examples: digits, signs like < >=, and strings such as while)
2. A set of nonterminals. (Examples: stmt and expr above)
3. A set of productions where each production consists of a nonterminal, called the left side of the production, an arrow, and a sequence of tokens and/or nonterminals, called the right side of the production.
4. A designation of one of the nonterminals as the start symbol.

Syntax-Directed Translation

Wikipedia says, this refers to a method of compiler implementation where the source language translation is completely driven by the parser. And that a common method of syntax-directed translation is translating a string into a sequence of actions by attaching one such action to each rule of a grammar. Thus, parsing a string of the grammar produced a sequence of rule applications. SDT provides a simple way to attach semantics to any such syntax.

C:PTT calls this a grammar oriented technique. The syntax-directed translator is a combination of a syntax analyzer and an intermediate code generator.

Syntax-Directed Definitions

CPTT says this uses a context-free grammar to specify the syntactic structure of the input. With each grammar symbol, it associates a set of attributes, and with each production, a set of semantic rules for computing values of the attributes associated with the symbols appearing in that production.

Translation: input-output mapping.

The output for x: first construct a parse tree for x. Say there is a node n in the parse tree labeled by the grammar symbol X. Write X.a to denote the value of attribute a of X at that node. The value is computed using the semantic rule for attribute a associated with the X-production used at node n. A parse tree that shows the attribute values at each node is called an annotated parse tree.

Synthesized Attributes