**Evaluating Expressions Based On Given Grammar-**

There are two methods for evaluating the expressions based on given grammar-

- Drawing a parse tree
- Designing the rules for operators

**Method-01:Â ****Drawing Parse Tree-**

In this method, following steps are followed-

- We draw a
**Parse Tree** for the given expression. - We evaluate the parse tree to get the required value of the expression.

**Drawback-**

- Drawing a parse tree for large expressions is cumbersome and time taking.
- So, this method becomes difficult to follow when the expression is large.

**Method-02: Designing R****ules For Operators-**

In this method, following steps are followed-

- We decide the priority and associativity of operators in the grammar.
- We parenthesize the given expression.
- We evaluate the expression to get the required value.

**Advantage-**

- This method is easy to follow whether the expression is small or large.
- So, this method is preferred.

**Rules For Deciding Priority Of Operators-**

For the given unambiguous grammar,

- The priority of operators is decided by checking the level at which the production is present.
- The higher the level of production, the lower the priority of operator contained in it.
- The lower the level of production, the higher the priority of operator contained in it.

**Also Read-** **Converting Ambiguous into Unambiguous Grammar**

**Example-**

Consider the grammar-

EÂ â†’ E x F / F + E / F

FÂ â†’ F – T / T

TÂ â†’ id

Here,

- id has the highest priority.

(since TÂ â†’ id is present at the bottom most level)

- x and + operators have the least priority.

(since EÂ â†’ E x F / F + E are present at the top most level)

- x and + operators have the same priority.

(since EÂ â†’ E x F / F + E are present at the same level)

- – operator has higher priority than x and + but lesser priority than id.

(since FÂ â†’ F – T is present at the middle level)

So, the priority order is-

**id** >Â **–** > ( **x** , **+**Â )

**Rules For Deciding Associativity Of Operators-**

For the given unambiguous grammar,

- The associativity of operators is decided by checking the
**Type Of Recursion** in the production. - If the production has left recursion, then the operator is left associative.
- If the production has right recursion, then the operator is right associative.
- If the production has both left and right recursion, then the operator is neither left associative nor right associative.

**Example-**

Consider the grammar-

EÂ â†’ E x F / F + E / F

FÂ â†’ F – F / T

TÂ â†’ id

Here,

- x operator is left associative.

(since EÂ â†’ E x F has left recursion in it)

- + operator is right associative.

(since EÂ â†’ F + E has right recursion in it)

- F – F is neither left associative nor right associative.

(since F â†’ F – F has both left and right recursion in it)

**PRACTICE PROBLEMS BASED ON EVALUATINGÂ EXPRESSIONS FOR GRAMMAR-**

**Problem-01:**

Consider the given grammar-

EÂ â†’ E + T / T

TÂ â†’ F x T / F

FÂ â†’Â id

Evaluate the following expression in accordance with the given grammar-

2 + 3 x 5 x 6 + 2

**Solution-**

**Method-01:**

- Let us draw a parse tree for the given expression.
- Evaluating the parse tree will return the required value of the expression.

The parse tree for the given expression is-

On evaluating this parse tree, we get the value = 94.

**Method-02:**

The priority order and associativity of operators on the basis of given grammar is-

**id** >Â **x**Â >Â **+**

where-

- x operator is right associative.
- + operator is left associative.

Now, we parenthesize the given expression based on the precedence and associativity of operators as-

( 2 + ( 3 x ( 5 x 6 ) ) ) + 2

Now, we evaluate the parenthesized expression as-

= ( 2 + ( 3 x **( 5 x 6 )** ) ) + 2

= ( 2 + **( 3 x 30 )** ) + 2

= **( 2 + 90 )** + 2

= **92 + 2**

= 94

**Problem-02:**

Consider the given grammar-

EÂ â†’ E + T / E – T / T

TÂ â†’ T x F / TÂ Ã· F / F

FÂ â†’ GÂ â†‘ F / G

GÂ â†’ id

Evaluate the following expression in accordance with the given grammar-

2 x 1 + 4Â â†‘ 2Â â†‘ 1 x 1 + 3

**Solution-**

**Method-01:**

- Let us draw a parse tree for the given expression.
- Evaluating the parse tree will return the required value of the expression.

The parse tree for the given expression is-

On evaluating this parse tree, we get the value = 21.

**Method-02:**

The priority order and associativity of operators on the basis of given grammar is-

**id** >Â **â†‘** > ( **x** ,Â **Ã·** ) > ( **+** , **–** )

where-

- + , – , x ,Â Ã· operators are left associative.
- â†‘ operator is right associative

Now, we parenthesize the given expression based on the precedence and associativity of operators as-

( ( 2 x 1 ) + ( ( 4Â â†‘ ( 2Â â†‘ 1 ) ) x 1 ) ) + 3

Now, we evaluate the parenthesized expression as-

= ( ( 2 x 1 ) + ( ( 4Â â†‘ **( 2Â â†‘ 1 )** ) x 1 ) ) + 3

=Â ( ( 2 x 1 ) + ( **( 4Â â†‘ 2 )** x 1 ) ) + 3

= ( **( 2 x 1 )** + ( 16 x 1 ) ) + 3

= ( 2 + **( 16 x 1 )** ) + 3

=Â **( 2 + 16 )** + 3

= **18 + 3**

= 21

**Problem-03:**

Consider the given grammar-

EÂ â†’ E + T / E – T / T

TÂ â†’ T x F / TÂ Ã· F / F

FÂ â†’ F â†‘ G / G

GÂ â†’ id

Evaluate the following expression in accordance with the given grammar-

2 â†‘ 1 â†‘ 4 + 3 x 5 x 6 â†‘ 1 + 2 â†‘ 3

**Solution-**

The priority order and associativity of operators on the basis of given grammar is-

**id** >Â **â†‘** > ( **x** ,Â **Ã·** ) > ( **+** , **–** )

where + , – , x ,Â Ã·,Â â†‘ operators are left associative.

Now, we parenthesize the given expression based on the precedence and associativity of operators as-

( ( ( 2 â†‘ 1 ) â†‘ 4 ) + ( ( 3 x 5 ) x ( 6 â†‘ 1 ) ) ) + ( 2 â†‘ 3 )

Now, we evaluate the parenthesized expression as-

= ( ( ( **2 â†‘ 1** ) â†‘ 4 ) + ( ( 3 x 5 ) x ( 6 â†‘ 1 ) ) ) + ( 2 â†‘ 3 )

= ( **( 2 â†‘ 4 )** + ( ( 3 x 5 ) x ( 6 â†‘ 1 ) ) ) + ( 2 â†‘ 3 )

= ( 16 + ( ( 3 x 5 ) x ( **6 â†‘ 1** ) ) ) + ( 2 â†‘ 3 )

= ( 16 + ( ( 3 x 5 ) x 6 ) ) + **( 2 â†‘ 3 )**

= ( 16 + ( **( 3 x 5 )** x 6 ) ) + 8

= ( 16 + **( 15 x 6 )** ) + 8

=Â **( 16 + 90 )** + 8

= **106 + 8**

= 114

**Problem-04:**

Consider the given grammar-

EÂ â†’ E â†‘ T / T

TÂ â†’ T + F / F

FÂ â†’ G – F / G

GÂ â†’ id

Evaluate the following expression in accordance with the given grammar-

2 â†‘ 1 â†‘ 3 + 5 – 6 – 8 – 5 + 10 + 11 â†‘ 2

**Solution-**

The priority order and associativity of operators on the basis of given grammar is-

**id** > **–**Â > **+**Â > **â†‘**

where-

- + , â†‘ operators are left associative.
- – is right associative.

Now, we parenthesize the given expression based on the precedence and associativity of operators as-

( ( 2 â†‘ 1 ) â†‘ ( ( ( 3 + ( 5 – ( 6 – ( 8 – 5 ) ) ) ) + 10 ) + 11 ) ) â†‘ 2

Now, we evaluate the parenthesized expression as-

= ( ( 2 â†‘ 1 ) â†‘ ( ( ( 3 + ( 5 – ( 6 – **( 8 – 5 )** ) ) ) + 10 ) + 11 ) ) â†‘ 2

= ( ( 2 â†‘ 1 ) â†‘ ( ( ( 3 + ( 5 – **( 6 – 3 )** ) ) + 10 ) + 11 ) ) â†‘ 2

= ( ( 2 â†‘ 1 ) â†‘ ( ( ( 3 + **( 5 – 3 )** ) + 10 ) + 11 ) ) â†‘ 2

= ( ( 2 â†‘ 1 ) â†‘ ( ( **( 3 + 2 )** + 10 ) + 11 ) ) â†‘ 2

= ( ( 2 â†‘ 1 ) â†‘ ( **( 5 + 10 )** + 11 ) ) â†‘ 2

= ( ( 2 â†‘ 1 ) â†‘ **( 15 + 11 )** ) â†‘ 2

= ( **( 2 â†‘ 1 )** â†‘ 26 ) â†‘ 2

= **( 2 â†‘ 26 )** â†‘ 2

= **(2**^{26})Â â†‘ 2

= (2^{26})^{2}

**Problem-05:**

Consider the given priority order of operators-

**id** >Â ( **x** ,Â **Ã·** ) > ( **+** , **–** )

Given all the operators are left associative, construct the corresponding grammar.

**Solution-**

We apply the rules learnt above in reverse direction to obtain the required grammar.

The corresponding grammar is-

EÂ â†’ E + T / E – T / T

TÂ â†’ T x F / T Ã· F / F

FÂ â†’ id

**Problem-06:**

Consider the given priority order of operators-

**id** >Â **â†‘** > ( **x** ,Â **Ã·** ) > ( **+** , **–** )

Given all the operators are left associative, construct the corresponding grammar.

**Solution-**

The corresponding grammar is-

EÂ â†’ E + T / E – T / T

TÂ â†’ T x F / T Ã· F / F

F â†’ G â†‘ F / G

G â†’ id

**Next Article-** **Important Points For Exams**

Get more notes and other study material of **Theory of Automata and Computation**.

Watch video lectures by visiting our YouTube channel **LearnVidFun.**