Scribd
Upload
79 views

14-03-2021 Lecture Notes Operator Precedence Parser

The document discusses operator precedence parsing (bottom-up parsing) and provides two examples. It explains that operator grammars must follow two rules: 1) no two adjacent non-terminals and 2) no null productions. The first example converts a context-free grammar to an operator grammar and shows the operator precedence table and parsing of the string "Id + id * id $". The second example provides another operator grammar and parses the string "a + b * c * d $".

Uploaded by

Soha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
79 views

14-03-2021 Lecture Notes Operator Precedence Parser

The document discusses operator precedence parsing (bottom-up parsing) and provides two examples. It explains that operator grammars must follow two rules: 1) no two adjacent non-terminals and 2) no null productions. The first example converts a context-free grammar to an operator grammar and shows the operator precedence table and parsing of the string "Id + id * id $". The second example provides another operator grammar and parses the string "a + b * c * d $".

Uploaded by

Soha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

Operator precedence parser (Bottom-Up parsing)

Can handle some of ambiguous grammars

Operator Grammar:

1) No two adjacent Non Terminals


2) No Null production

Example:

E EAE | id

A + | *

We need to convert this grammar into operator grammar

E E+E | E*E |id -------------- (Operator Grammar)

Example:

SSAS | a

A bSb |b

We need to convert this grammar into operator grammar

S SbSbS | SbS | a -------------------------------- (operator grammar)

ab = a*b (Not Equal)

Implementation Example:

E E+E | E*E | id

Find all terminals from the operator grammar and build operator relational table.

Id + * $

Id -- > > >

+ < > < >

* < > > >

$ < < < Accept


Rules for filling table:

1) Id has highest precedence.


2) Id van not be compared with any other id.
3) $ has least precedence.
4) When $ is compared with $ that means you are at accepting state.
5) If two same operators are compared then we need to check associativity of that operator.

Rules for Parsing Input String:

If > (Greater than) symbol found then pop (Reduce).

If< (Less Than) Symbol found then push (Shift).

Stack Input String Actions

$ Id + id * id $ Shift id

$ id + id * id $ Reduce E id

$E + id * id $ Shift +

$E+ Id * id $ Shift id

$ E + id *id $ Reduce E id

$E+E *id $ Shift *

$E+E* Id $ Shift id

$ E + E * id $ Reduce E id

$E+E*E $ Reduce E  E*E

$E+E $ Reduce E E+E

$E $ Accept

When top of stack is $ and Input pointer is also on $ then we can conclude the string is parsed
successfully.
Example no 2:

E E+T | T

T T*V | V

V a| b | c | d

We need to identify terminals in the above operator grammar.

+ * A B C D $

+ > < < < < < >

* > > < < < < >

A > > -- -- -- -- >

B > > -- -- -- -- >

C > > -- -- -- -- >

D > > -- -- -- -- >

$ < < < < < < Accept

Input string which needs to be parsed is a + b * c * d $

Stack Input String Actions

$ a+b*c*d$ Shift a

$a +b*c*d$ Reduce Va

$V +b*c*d$ Shift +

$V+ b*c*d$ Shift b


$V+b *c * d $ Reduce V b

$V+V *c * d $ Shift *

$V+V* c*d$ Shift c

$V+V*c *d $ Reduce Vc

$V+V*V *d $ Reduce T V

$V+V*T *d $ Reduce ET

$V+V*E *d $

The given string can not be parsed completely.

You might also like