A Simple Syntax-Directed Translator

Definition of Grammars

A context-free grammar composed of:

  • A set of terminal symbols referred to as “tokens”.
  • A set of nonterminals called “syntactic variables”.
  • A set of productions, where each production consists of a nonterminal, called the head or left side of the production, an arrow, and a sequence of terminals and/or nonterminals, called the body or right side of the production.
  • A designation of one of the nonterminals as the start symbol.

For example:

The 10 productions for the nonterminal digit ( as you know, production (4) can be splited into 10 productions of the form like $digit \rightarrow 0$ ) allow it to stand for any of the terminals 0, 1, 2, …, 9. From production (3), a single digit by itself is a list. So, we can deduce 9-5+2 is a list as follows:

  • 9 is a list by production (3)
  • 9-5 is a list by production (2)
  • 9-5+2 is a list by production (1)

Parsing is the problem of taking a string of terminals and figuring out how to derive it from the start symbol of the grammar.

A parse tree:

if nonterminal A has a production $A \rightarrow XYZ$, then a parse tree may have an interior node labeled A with three children labeled X, Y, and Z, from left to right.

Formally, given a context-free grammar, a parse tree according to the grammar is a tree with the following properties:

  1. The root is labeled by the start symbol.
  2. Each leaf is labeled by a terminal or by $\epsilon$.
  3. Each interior node is labeled by a nonterminal.
  4. If A is the nonterminal labeling some interior node and X1, X2, …, Xn are the labels 🏷 of the children of that node from left to right, then there must be a production $A \rightarrow X1X2…Xn$.

A Simple Syntax-Directed Translator




Posted on


Updated on


Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.


You forgot to set the shortname for Disqus. Please set it in _config.yml.