Operator precedance parsing

operator precedence parsing

1. Operator Precedence Parsing

2. Bottom-up Parsing In general the bottom-up parsing is also known as shift-reduce parsing. T ypes of bottom-up parsing: Operator-Precedence parsing LR parsing

3. Operator Precedence Parser An operator precedence parser is a bottom-up parser that interprets an operator grammar. This parser is only used operator grammars .  Ambiguous grammars are not allowed in any parser except operator precedence parser. Operator precedence grammar is kinds of shift reduce parsing method. It is applied to a small class of operator grammars .

4. Operator Precedence Grammar A grammar is said to be operator precedence grammar if it has two properties: No R.H.S. of any production has a ∈. No two non-terminals are adjacent. Operator precedence can only established between the terminals of the grammar. It ignores the non-terminal.

5. Operator Precedence Grammar Example-1 E→AB E→EOE E→E+E | A→a E→id E*E | B→b O→+|*|/ E/E | id not operator grammar not operator grammar operator grammar

6. Operator Precedence Grammar Example-2 S →SAS/a S →S bSb S /a/ S b S A →bSb /b Replace non terminal A and convert it into operator grammar not operator grammar operator grammar

7. Operator Precedence Relations: There are the three operator precedence relations :- a ⋗ b means that terminal "a" has the higher precedence than terminal "b". a ⋖ b means that terminal "a" has the lower precedence than terminal "b". a ≐ b means that the terminal "a" and "b" both have same precedence.

8. Operator Precedence parsing Rule: How to assign these relation ??? Rule-01 :   If precedence of a is higher than precedence of b, a>b If precedence of b is same as precedence of a, a = b If precedence of a is lower than precedence of b, a <b   Rule-02:   An identifier(id) is always given the higher precedence than any other symbol. $ symbol is always given the lowest precedence.   Rule-03:   If two operators have the same precedence, then we consider the rule of associativity .

9. Building the operator precedence parsing table: Example:-consider the following grammar E-> E+E | E*E | id For this grammar the precedence table looks something like this: The table size is n*n where n is the number of terminal symbols in the grammar c id + * $ id - . > . > . > + < . . > < . . > * < . . > . > . > $ < . < . < . acc

10. Operator-Precedence Parsing Algorithm The input string is w$, the initial stack is $ and a table holds precedence relations between certain terminals Algorithm: set p to point to the first symbol of w$ ; repeat forever if ( $ is on top of the stack and p points to $ ) then return else { let a be the topmost terminal symbol on the stack and let b be the symbol pointed to by p; /* SHIFT */ if ( a < . b or a =· b ) then { push b onto the stack; advance p to the next input symbol; } else if ( a . > b ) then /* REDUCE */ repeat pop stack until ( the top of stack terminal is related by < . to the terminal most recently popped ); else error(); }

11. Operator-Precedence Parsing –Example Problem-01 : Consider the following grammar- E → EAE | id A → + | x Construct the operator precedence parser and parse the string id + id x id . Solution- We convert the given grammar into operator precedence grammar. The equivalent operator precedence grammar is- E → E + E | E x E | id The terminal symbols in the grammar are { id, + , x , $ } We construct the operator precedence table as-   c id + * $ id - . > . > . > + < . . > < . . > * < . . > . > . > $ < . < . < . acc

12. Operator-Precedence Parsing Algorithm --Example   Given Grammar E → E + E | E x E | id c id + * $ id - . > . > . > + < . . > < . . > * < . . > . > . > $ < . < . < . acc stack $ input id+id*id$ action $ < . id shift $id +id*id$ id . > + reduce E  id $ +id*id$ shift $+ id*id$ shift $+id *id$ id . > * reduce E  id $+ *id$ shift $+* id$ shift $+*id $+* $ $ id . > $ reduce E  id * . > $ reduce E  E*E $+ $ + . > $ reduce E  E+E $ $ accept parse the string id + id x id$

13. Advantages and Disadvantages Advantages: – It is simple to implement operator precedence parsing. – powerful enough for expressions in programming languages Disadvantages : – It cannot handle the unary minus . – It is applicable only to a small class of grammars.    

14. Precedence Functions The storage space however can be efficiently managed if we can build an efficient data structure to represent adequately the precedence relationships between the terminals. For this we can construct two functions f and g where the following hold: If a. >b then f(a)>g(b) If a< . b then f(a)<g(b) If a. =b then f(a)=g(b)

15. Constructing Precedence Functions To construct these functions we create a directed graph with nodes fi and gi where i is the i th terminal, obeying the following rules: If a. =b then fa and fb are merged, and ga and gb are merged If a. >b then a directed edge is introduced from fa to gb If a< . b then a directed edge is introduced to fa from gb Following these rules, the precedence graph for the above mentioned precedence table looks something like this: Example: consider the following table c id + * $ id - . > . > . > + < . . > < . . > * < . . > . > . > $ < . < . < . acc

16. Constructing Precedence Functions Using the algorithm leads to the following graph: c id + * $ id - . > . > . > + < . . > < . . > * < . . > . > . > $ < . < . < . acc f * f $ f id f + g id g + g * g $

17. Constructing Precedence Functions From which we extract the following precedence functions: