Skip to content

Lecture No. 13

Dated: 25-03-2025

Top down Parser

The root node is labeled as goal which is the starting symbol of the grammar.
The top down parsing algorithm is as follows:

  1. Construct the root node of the parse tree.1
  2. Repeat until the fringe of the parse tree1 matches input string.2
    1. At a node labeled \(A\), select a production with \(A\) on its left hand side.
    2. for each symbol on its right hand side, construct the appropriate child.
    3. When a terminal symbol is added to the fringe and it does not match the fringe, backtrack.

Example

\[\text{input}= x - 2 * y\]
P Sentential Form Input
- Goal x - 2 * y
1 expr x - 2 * y
2 expr + term x - 2 * y
4 term + term x - 2 * y
7 factor + term x - 2 * y
9 + term x - 2 * y
9 + term x - 2 * y

The parser2 made made the wrong choice of choosing + in step 2 and has to backtrack and use a different production.

P Sentential Form Input
- Goal x - 2 * y
1 expr x - 2 * y
2 expr - term x - 2 * y
4 term - term x - 2 * y
7 factor - term x - 2 * y
9 - term x - 2 * y
9 - term x - 2 * y

Since the - match, let's continue

P Sentential Form Input
- - term x - 2 * y
7 - factor x - 2 * y
9 - x - 2 * y
- - x - 2 * y

The 2 match but there is still non terminals in sentential form which need to be expanded, therefore we backtrack.

P Sentential Form Input
- - term x - 2 * y
5 - term * factor x - 2 * y
7 - factor * factor x - 2 * y
8 - * factor x - 2 * y
- - * factor x - 2 * y
- - * factor x - 2 * y
- *
9 x - 2 * y
- *
- x - 2 * y

Left Recursion

P Sentential Form input
- Goal x - 2 * y
1 expr x - 2 * y
2 expr + term x - 2 * y
3 expr + term + … x - 2 * y

Top down parsers cannot handle left recursion grammars.
A grammar is left recursive if \(\exists A \in NT\) such that a derivation \(A \implies ^* A \alpha\) for some string \(\alpha \in (NT \cup T)^*\).
Consider the following

\[A \to A \alpha\]
\[| \beta\]

We can re-write it as

\[A \to \beta A\]
\[A^\prime \to \alpha A^\prime\]
\[| \epsilon\]
expr  ->   term expr'
expr' -> + term expr'
      |  - term expr'

term  ->   factor term'
term' -> * factor term'
      |  / factor
      |    term'
      |    e

These fragments use only right recursion.
They retain the original left associativity.
A top-down parser will terminate using them.

Predictive Parsing

Instead of backtracking, we can look ahead in arbitrary amount to provide enough context to pick the correct production.
Given \(A \to \alpha | \beta\), the parser3 should be able to choose between \(\alpha\) and \(\beta\).
To accomplish this, the parser needs FIRST and FOLLOW sets4

First Sets4

For some right hand side \(\alpha \in G\) defines FIRST(\(\alpha\)) as set4 of tokens5 that appear as the first symbol in some string2 derived from \(\alpha\).

\[x \in FIRST(\alpha) \iff \alpha \implies ^*x \gamma\]

For some \(\gamma\).

References

  1. Read more about parse trees. ↩↩

  2. Read more about strings. ↩↩↩

  3. Read more about parsers. ↩

  4. Read more about sets. ↩↩↩

  5. Read more about tokens. ↩