2 of 32

What is this about ?

Chapter 2 presents a recursive-descent parser for the syntax analysis phase of a small compiler. Manual construction of such parsers is both time consuming and error prone, especially when applied at the scale of a real programming language.
At first glance, the code for a recursive-descent parser may appear to be written ad hoc. Fortunately, there are principles at work. This chapter discusses these principles and their applications in tools that automate the parsing phase of a compiler.
In this chapter, we discuss top-down parsers in greater detail, analyzing the conditions under which such parsers can be reliably and automatically constructed from grammars.

4 of 32

Top-down parsers are in theory not as powerful as the bottom-up parsers
However, because of their simplicity, performance, and excellent error diagnostics, top-down parsers have been constructed for many programming languages, almost always using the recursive-descent approach.
Such parsers are also convenient for prototyping relatively simple front-ends of larger systems that require a rigorous definition and treatment of the system’s input.

PNP FACT

5 of 32

In this chapter, we study the following two forms of top-down parsers:

• Recursive-descent parsers contain a set of mutually recursive procedures that cooperate to parse a string. Code for these procedures can be written directly from a suitable grammar.

• Table-driven LL parsers use a generic LL(k) parsing engine and a parse table that directs the activity of the engine. The entries for the parse table are determined by the particular LL(k) grammar.

top-down parsers

Table-driven LL parsers

Recursive-descent parsers

6 of 32

Fortunately, context-free grammars (CFGs) with certain properties can be used to generate such parsers automatically.

Tools that operate in this fashion are generally called compiler compilers or parser generators. They take a grammar description file as input and attempt to produce a parser for the language defined by the grammar.

The term “compiler compiler” applies because the parser generator is itself a compiler: it accepts a high-level expression of a program (the grammar definition file) and generates an executable form of that program (the parser).

7 of 32

This approach makes parsing one of the easiest and most reliable phases of compiler construction for the following reasons:

When the grammar serves as a language’s definition, parsers can be automatically constructed to perform syntax analysis in a compiler. The automatic construction guarantees that the resulting parser is faithful to the language’s syntactic specification.

When a language is revised, updated, or extended, the associated modifications can be applied to the grammar description to generate a parser for the new language.

8 of 32

As discussed in Chapters 2 and 4, every string in a grammar’s language can be generated by a derivation that begins with the grammar’s start symbol. While it is relatively straightforward to use a grammar’s productions to generate sample strings in its language, reversing this process does not seem as simple.
That is, given an input string, how can we show why the string is or is not in the grammar’s language?
This is the parsing problem.This parsing technique is known by the following names:

Top-down, because the parser begins with the grammar’s start symbol and grows a parse tree from its root to its leaves.
Predictive, because the parser must predict at each step in the derivation which grammar rule is to be applied next.
LL(k), because these techniques scan the input from left to right (the first “L” of LL), produce a leftmost derivation (the second “L” of LL), and use k symbols of lookahead.
Recursive descent, because this kind of parser can be implemented by a collection of mutually recursive procedures.

9 of 32

Video Time for LL(k) gramars

https://youtu.be/iACdVbRAEr4

https://www.youtube.com/watch?v=QBa5ll_WglY&t=205s

10 of 32

Exercise ( fix )

and suppose the (input) sentence is aabbcc.

First we try the top-down parsing method.

Suppose we have the monotonic grammar for the language a^n b^n c^n

11 of 32

A -> A α | B

12 of 32

Please eliminate the Left recursion of the following Grammar

A -> A α | β

13 of 32

A -> A α | β

15 of 32

Top Down Parsing

https://www.youtube.com/watch?v=nv9J5Jb7IxM

16 of 32

Table driven LL(1) parses

The task of creating recursive-descent parsers as presented is mechanical and can therefore be automated. However, the size of the parser’s code grows with the size of the grammar.
Moreover, the overhead of method calls and returns can be a source of inefficiency. In this section we examine how to construct a table-driven LL(1) parser.
Actually, the parser itself is standard across all grammars, so we need only provide an adequate parse table.
To generate the table is necesary to generate the First and Follow set

21 of 32

Full Example

22 of 32

LL1 parsing table

Fill Columns with First set of Non terminals
If First ( Non- terminal ) contains epsilon , look for Follow Set
If multiple entries appears in column, then we can conclude that the given grammar is not LL1
If the grammar is LL1 , then is un ambiguos

24 of 32

Now … what ?

Assume that you have the input (id) which is valid

stack	inputs	moves
$E	(id)$	E->TE’
$E’T	(id)$	T->FT’
$E’T’F	(id)$	F->(E)
$E’T’)E(	(id)$	Pop ‘(’
$E’T)E	id)$	E->TE’
$E’T’)E’T	id)$	T->FT’
$E’T’)E’T’F	id)$	F->id
$E’T’)E’T’id	id)$	Pop id
$E’T’)E’T’	)$	T’->e
$E’T’)E’	)$	E’->e
$E’T’)	)$	Pop )
$E’T’	$	T’->e
$E’	$	E’->e
$	$

25 of 32

Another Full example

28 of 32

Another Full example

29 of 32

The non blank entries in the above table indicate the number of the rule that should be applied, given a nonterminal on top-of-stack and an input symbol as lookahead.

30 of 32

31 of 32

Recursive descent parsers

Video Time : )

https://www.youtube.com/watch?v=SH5F-rwWEog

IMPORTANT : https://www.youtube.com/watch?v=b89J-m4YsZ8

Extra: https://www.youtube.com/watch?v=uRLIjbMeXVU&list=LLHTlHBK7QS0yuSmFtoEjZkA&index=2&t=197s

32 of 32

Summary

Crafting a compiler Chapter 5 until Section 5.3

Complement your summary with:

Videos:

https://www.youtube.com/watch?v=PnOCNxckV48

https://www.youtube.com/watch?v=SH5F-rwWEog

Read Chapter 3 of

https://dickgrune.com/Books/PTAPG_1st_Edition/

Extra links

http://faculty.ycp.edu/~dhovemey/fall2012/cs340/lecture/lecture05.html

http://www.csd.uwo.ca/~moreno/CS447/Lectures/Syntax.html/node8.html

http://www.iitg.ac.in/gkd/ma513/sep/sep27/note-0.pdf

Exam will be about these subjects

1 of 32