Skip to content

Lecture No. 03

Dated: 13-03-2025

A parse can be represented by a parse tree or syntax tree.

cs606_e_3_1.svg

A syntax tree for parsing \(x + 2 - y\)

The deviations can be extracted by starting from the root node and working towards each leaf node.

Abstract Syntax Tree

Sometimes the syntax tree contains a lot of unnecessary data and compilers often use abstract syntax tree.

cs606_e_3_2.svg

Abstract Syntax Tree for the example above

ASTs are one kind of intermediate representations which are a lot more concise and summarize the grammar without the details of deviations.

Back End

The back end translate the intermediate representation into the target machine code.
The back end

  • Ensures conformance with system interfaces.
  • Decides which values to keep in registers to prevent memory accesses as accessing memory is slow.
  • Responsible for instruction selection to produce fast and compact code.
  • Takes advantage of the addressing modes on the target machine.

The instruction selection problem is viewed as a pattern matching problem that can be solved using the dynamic programming1 based algorithms.

References

  1. Read more about dynamic programming. ↩