1 of 15

Syntax analyzer� (Parser)�second phase of Compiler��Top-Down Parsing [ LL Parser ]�Bottom Up Parsing [ LR , SLR , LALR, CLR ]�

1

2 of 15

Syntax analyzer (Parsing)

COMPILER M.H.NAJI

2

Parsing

3 of 15

Top-down X Bottom-up

Top-down parsing

Recursive-descent parsing
LL(1) parsing

LL(1) parsing algorithm
First and follow sets
Constructing LL(1) parsing table
Error recovery

What to reduce

Bottom-up parsing

Shift-reduce parsers
LR(0) parsing

LR(0) items
Finite automata of items
LR(0) parsing algorithm
LR(0) grammar

SLR(1) parsing

SLR(1) parsing algorithm
SLR(1) grammar
Parsing conflict

When to reduce

COMPILER M.H.NAJI

3

Parsing

4 of 15

Top–Down Parsing Bottom–Up Parsing

A parse tree is created from root to leaves
The traversal of parse trees is a preorder traversal
Tracing leftmost derivation
Two types:

Backtracking parser
Predictive parser

A parse tree is created from leaves to root
The traversal of parse trees is a reversal of postorder traversal
Tracing rightmost derivation
More powerful than top-down parsing

COMPILER M.H.NAJI

4

Parsing

Backtracking: Try different structures and backtrack if it does not matched the input

Predictive: Guess the structure of the parse tree from the next input

5 of 15

Parse Trees and Derivations

E ^⇒ E + E

^⇒ id + E

^⇒ id + E * E

^⇒ id + id * E

^⇒ id + id * id

E ^⇒ E + E

^⇒ E + E * E

^⇒ E + E * id

^⇒ E + id * id

^⇒ id + id * id

COMPILER M.H.NAJI

5

Parsing

Top-down parsing

Bottom-up parsing

id

E

*

E

id

+

E

+

*

id

E

6 of 15

Backus-Naur Form

For programming languages, syntax rules are often expressed in BNF (Backus-Naur Form), a system that was developed by computer scientists John Backus and Peter Naur in the late 1950s.
BNF often used to describe the syntax of languages
BNF cannot express all possible syntax rules.
In BNF, a syntactic category is written as a word enclosed between "<" and ">".

COMPILER M.H.NAJI

6

Parsing

<expression>	::= <term> { + <term> \| - <term> }
<term>	::= <factor> { × <factor> }
<factor>	::= <constant> \| ( <expression> )
<constant>	::= <digit> { <digit> }
<digit>	::= 0 \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8 \| 9

7 of 15

Recursive-Descent Parser

Write one procedure for each set of productions with the same nonterminal in the LHS
Each procedure recognizes a structure described by a nonterminal.
A procedure calls other procedures if it needs to recognize other structures.
A procedure calls match procedure if it needs to recognize a terminal.

COMPILER M.H.NAJI

7

Parsing

لغرض بناء محلل اللغة Recursive Descent Parser نقوم بما يلي

انشاء دالة اختبار لكل اشتقاق اي المتغير في جهة اليسار (Nonterminal) ويمكن لكل دالة استدعاء دالة اخرى
مطابقة العناصر( terminal) حسب الدالة ( ) match ضمن الدوال المستدعاة
عند المطابقة نتحرك لقراءة العنصر التالي
عدد الدوال او الاجراءات ( procedures) النهائي = عدد Nonterminal+2

8 of 15

Recursive-Descent Parser

Suppose the grammar is

E ـــــ> dE’
E’ـــــــ> +dE’ | Ɛ

COMPILER M.H.NAJI

8

Parsing

E( )

{ If ( L== ”d”)

{

match(“d”);

E’( );

}

E’( )

{ If ( L== ”+”)

{ match(“d”);

match(“+”);

E’( );

}

Else return

}

match(char c)

{ If ( L== c)

L=getchar()

Else

Print(“Error”)

}

main( )

{

E( );

If ( L== $)

Print(“Accepted”)

}

9 of 15

Recursive-Descent Parser

Suppose the grammar is

E ـــــ> dE’
E’ـــــــ> +dE’ | Ɛ
Check the string d+d $

COMPILER M.H.NAJI

9

Parsing

main	E( )	E’( )	Match(c)
	E🡪dE’		d
		E’🡪+dE’	+
		E’🡪+ d	d
		E’🡪Ɛ	$
			d + d $

10 of 15

LL(1) Parsing

LL(1)

Read input from (L) left to right
Simulate (L) leftmost derivation
1 lookahead symbol

Use stack to simulate leftmost derivation

Part of sentential form produced in the leftmost derivation is stored in the stack.
Top of stack is the leftmost nonterminal symbol in the fragment of sentential form.

COMPILER M.H.NAJI

10

Parsing

11 of 15

Concept of LL(1) Parsing

Simulate leftmost derivation of the input.
Keep part of sentential form in the stack.
If the symbol on the top of stack is a terminal, try to match it with the next input token and pop it out of stack.
If the symbol on the top of stack is a nonterminal X, replace it with Y if we have a production rule X → Y.

Which production will be chosen, if there are both X → Y and X → Z ?

COMPILER M.H.NAJI

11

Parsing

12 of 15

FIRST & FOLLOW

COMPILER M.H.NAJI

12

Parsing

FIRST is a function find all terminals that can appear at the beginning of each non-terminal (variable). Epsilon (neither a terminal nor a non-terminal) may also be included in this FIRST function

FOLLOW function shows us the terminals that can come after a derived non-terminal. The follow of non-terminal is the first of the next non-terminal

S -> aABb

A -> aAc | Ɛ

B -> bB | c

13 of 15

COMPILER M.H.NAJI

13

Parsing

EX: construct FIRST and FOLLOW function for the following grammar

S -> ABCDE

A -> a| Ɛ

B -> b| Ɛ

C -> c

D -> d| Ɛ

E -> e| Ɛ

	FIRST	FOLLOW
S	{ a, b , c }	{ $ }
A	{ a , Ɛ }	{ b , c }
B	{ b , Ɛ }	{c}
C	{ c }	{d,e,$}
D	{ d ,e, Ɛ }	{e , $}
E	{ e , Ɛ }	{$}

14 of 15

Construct parsing LL table

COMPILER M.H.NAJI

14

Parsing

E -> E + T | T

T -> T * F | F

F -> (E) | id

Suppose the following grammar

Remove LR

A--- > Aα|β

A--- > βA'

A'---> αA'|Ɛ

نستخدم القانون

Left recursion grammar

E 🡪 T E‘

E' 🡪 + T E'| Ɛ

T 🡪 F T‘

T' 🡪 * F T'| Ɛ

F 🡪 (E) | id

grammar After remove recursion

15 of 15

COMPILER M.H.NAJI

15

Parsing

First & Follow

Construct LL table