#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

Answer 3

Let's analyze each statement in detail:

---

Statement 1:

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

Explanation:

• Operator grammar is a type of context-free grammar that satisfies certain properties required for constructing an operator precedence parser. Specifically:

  1. It does not have ε-productions (productions that derive an empty string).
  2. It does not have two nonterminals adjacent in any right-hand side of its productions.

• For constructing an operator precedence parser, we need an operator precedence table, which defines the precedence and associativity of operators. This table is based on relationships such as ⋖, ⋗, and = (less precedence, greater precedence, and equal precedence, respectively) between grammar symbols.

• If a grammar is not an operator grammar, it violates the rules necessary to define these precedence relationships. Hence, an operator precedence table cannot be constructed, and consequently, an operator precedence parser cannot exist for such grammars.

Verdict: The statement is true. If the grammar is not operator grammar, no operator precedence table or parser can be created.

---

Statement 2:

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

Explanation:

• If a grammar is an operator grammar, it satisfies all the conditions required to construct an operator precedence table, as described above. Therefore:

  • We can assign precedence relationships (⋖, ⋗, =) between terminal symbols based on the grammar's productions.
  • Using this table, we can construct an operator precedence parser.

• The key property of operator grammars is that they are unambiguous and allow for parsing based solely on precedence relationships between operators. Thus, if the grammar is operator grammar, we are guaranteed that an operator precedence parser can be built.

Verdict: The statement is true. If the grammar is an operator grammar, an operator precedence parser is guaranteed to exist.

---

Conclusion:

• Statement 1: True
• Statement 2: True