Study of Operator Precedence

Problem Statement : Study of Operator Precedence.

Theory :

A program G is said to be operator precedence, if it possesses following properties,

1) No production and right hand side is E.

2) There should not be any production rule processing two adjustment non terminal at R.H.S.

Consider a grammar for arithmetic expression.

E->EAE|(E)|FF;|id

A->+|-|*|^

This grammar is not an operator precedence grammar in production rule

E->E^E

If consecutive non terminal occur when first are null, convert it into equivalent operator precedence grammar by remaining A.

Follow the steps to parse the given string:

1. Scan the input from left to right until first .> is encountered.
2. Scan backward over until<. is encountered.
3. Handel the string between <. .>

E->E+E|E-E|E*E|E|E|E^E

E->(E)|-E|id

In operator precedence parsing, we will fist define precedence relations

<=&>, between pair of terminals. The warning of these relation is p<q.p gives more precedence than q.

p=q , p has same precedence as q

p>q , p takes precedence over q.

Table:

	Id	+	*	$
Id	Empty	GT	GT	GT
+	LT	GT	LT	GT
*	LT	GT	GT	GT
$	LT	LT	LT	Accepted

Precedence relation table

$<∙id∙>+<∙id∙>*<∙id∙.>$	Handle id is obtained between <∙> Reduce this by E->id
E+<∙id∙>*<∙id∙>$	Handle id is obtained between <∙> Reduce this by E->id
E+E*<∙id∙>$	Handle id is obtained between <∙> Reduce this by E->id
E+E*E	Remove all non terminal, insert $ at beginning at end also insert precedence operator
$<∙+∙><∙*∙>$	The * operator is surrounded by <∙>. This indicates that it becomes handle now hence we have to reduce E*E=op
$<∙>$	Now it became handle so we evaluate E∙F. Parsing is done

1. What is parsing? 

2. What is grammar?

3. What are the properties of the program to be in operator precedence?

4. What is mean by Kleen star and NULL closure?