PUERTA | GATE-CS-2017 (Conjunto 2) | Pregunta 40

Considere la siguiente gramática de expresión G.

E -> E - T | T
T -> T + F | F
F -> (E) | id

¿Cuáles de las siguientes gramáticas no son recursivas, sino equivalentes a G.

A)
E -> E - T | T
T -> T + F | F
F -> (E) | id

B)
E -> TE'
E' -> -TE' | ε
T -> T + F | F
F -> (E) | id

C)
E -> TX
X -> -TX | ε
T -> FY
Y -> +FY | ε
F -> (E) | id

D)
E -> TX | (TX)
X -> -TX | +TX | ε
T -> id

(A) A
(B) B
(C) C
(D) D

Respuesta: (C)
Explicación: Sabemos que para la recursión por la izquierda: A -> Aα/β
Después de eliminar la recursión por la izquierda, se puede escribir como

A->βA’
A’->αA’/ε

Así para : E->E- T/T
α= -T , β= T . por lo tanto, la nueva producción después de eliminar la recursividad izquierda
es E->TE’ y E’->- TE’/ ε

T->FT’ y T’->+FT’/ ε

F->(E)/id.

Cuestionario de esta pregunta