#compiler-design

Question

Which of the following statements are true. Please give a detailed explanation.

1)  If the given grammar is not operator grammar then we can’t design an operator precedence table and there doesn’t exist an operator precedence parser.

2) If the given grammar is operator grammar then it is guaranteed that there exists an operator precedence parser.

Answer 1

@Crackca

 

A grammar that is used to define mathematical operators is called an operator grammar or operator precedence grammar.

Such grammars have the restriction that no production has either an empty right-hand side (null productions) or two adjacent non-terminals in its right-hand side...

Operator precedence parser –

An operator precedence parser is a bottom-up parser that interprets an operator grammar. This parser is only used for operator grammars.

Ambiguous grammars are not allowed in any parser except operator precedence parser.

There are two methods for determining what precedence relations should hold between a pair of terminals:

1. Use the conventional associativity and precedence of operator. 

2. The second method of selecting operator-precedence relations is first to construct an unambiguous grammar for the language, a grammar that reflects the correct associativity and precedence in its parse trees.

This parser relies on the following three precedence relations: ⋖, ≐, ⋗

## a ⋖ b

This means a “yields precedence to” b….

## a ⋗ b

This means a “takes precedence over”

b. ## a ≐ b

This means a “has same precedence as” b.

There is not given any relation between id and id as id will not be compared and two variables can not come side by side.

There is also a disadvantage of this table –

if we have n operators then size of table will be n*n and complexity will be 0(n2).

In order to decrease the size of table, we use operator function table. Operator precedence parsers usually do not store the precedence table with the relations; rather they are implemented in a special way.

Operator precedence parsers use precedence functions that map terminal symbols to integers, and the precedence relations between the symbols are implemented by numerical comparison.

The parsing table can be encoded by two precedence functions f and g that map terminal symbols to integers.

We select f and g such that:

a. f(a) < g(b) whenever a yields precedence to b

b. f(a) = g(b) whenever a and b have the same precedence

c. f(a) > g(b) whenever a takes precedence over b ….

 

1. https://gatecse.in/lr-parsing-part-2-language-of-ll-and-lr-grammars 

 

2. https://www.math.uni.lodz.pl/~robpleb/Wyklad_9_ang.pdf 

 

3. https://en.wikipedia.org/wiki/Operator-precedence_grammar

 

Comments

But what's the answer???

---

@chirag_soni_07

1) True ..

2) True ..

Answer 2

Answer should be TRUE and TRUE