Compiler desigb

Question

consider the following grammar

$E\rightarrow int|int+E|int-E |int-(E) |int*E$

Which statement is true?

a) Grammer is left factored

b) Cant be determined

Comments

Left factoring is a grammar tranformation technique. 

Good Read: http://www.csd.uwo.ca/~moreno/CS447/Lectures/Syntax.html/node9.html

Answer 1

Left Factoring is a grammar transformation technique. It consists in "factoring out" prefixes which are common to two or more productions.

For example, going from:

A -> α β | α γ

to:

A -> α A'

A' -> β | γ

---

Answer 2

What is nondeterminism in grammar?

Also called common suffix problem. There is non-determinism in grammar when in the same production there is more than one option to proceed further on reading a particular symbol.

For example, going from:

A → α β | α γ

The compiler will be confused whether to take use first production or 2nd one.So it tires both one after the other which may lead to backtracking.

What is left factoring? 

Left Factoring is a grammar transformation technique. It consists in "factoring out" prefixes which are common to two or more productions.

For example, going from:

A → α β | α γ

to:

A → α A'

A' → β | γ

Good Read: https://cs.stackexchange.com/questions/4862/left-factoring-a-grammar-into-ll1

Source: https://stackoverflow.com/questions/15194142/difference-between-left-factoring-and-left-recursion?utm_medium=organic&utm_source=google_rich_qa&utm_campaign=google_rich_qa

Comments

From above links and as per my knowledge i got it has left factor

But the ans in booklets is given that cant be determined how?

---

Which booklet are you following?

Answer 3

At production

E -- > int + E | int - E | int * E | int - (E)

after seeing first "int" grammar might confuse what to choose next hence non determinism is there. That's why it is not left factored.

Answer 4

yes and so in this question you can make it left factoring as

E -> int-E'

E' -> E/(E)

So it is not in left factoring you can convert it.