Parse Tree | PPL | Prof. Jayesh Umre


A parse tree is a diagrammatic representation of the parsed structure of a sentence or string.
In the syntax analysis phase, a compiler verifies whether or not the tokens generated by the lexical analyzer are grouped according to the syntactic rules of the language. This is done by pare tree.
Than from parse tree intermediate code can be generated.
A parse tree for a grammar G is a tree where

  • the root is the start symbol for G
  • the interior nodes are the nonterminals of G
  • the leaf nodes are the terminal symbols of G.
  • the children of a node T (from left to right) correspond to the symbols on the right hand side of some production for T in G.

A grammar that produces more than one parse tree for some sentence is said to be ambiguous.
There are two ways to draw a parse tree:
1) Top-down Approach:

  • Starts with the starting symbol S
  • Goes down to tree leaves

2) Bottom-up Approach:

  • Starts from tree leaves
  • Proceeds upward to the starting symbol S
Leftmost and Rightmost Derivation of a String:
1) Leftmost derivation: A leftmost derivation is obtained by applying production to the leftmost variable in each step.
For example, S –>  a+b*c
2) Rightmost derivation: A rightmost derivation is obtained by applying production to the rightmost variable in each step.
For example, S –>  a+b*c

Principles of Programming Languages: covered following topics in these notes.

Previous years solved papers:

A list of Video lectures


  1. Sebesta,”Concept of programming Language”, Pearson Edu 
  2. Louden, “Programming Languages: Principles & Practices” , Cengage Learning 
  3. Tucker, “Programming Languages: Principles and paradigms “, Tata McGraw –Hill. 
  4. E Horowitz, “Programming Languages”, 2nd Edition, Addison Wesley