Gestion de proyectos

ELIMINACION DE FACTORES COMUNES IZQUIERDOS
• Se trata de rescribir las producciones de la gramática con igual comienzo para retrasar la decisión hasta haber visto losuficiente de la entrada como para elegir la opción correcta
Procedimiento:
A := αβ1 |αβ2 | … | αβn | δi
A := αA’ | δi
A’ := β1 | β2 | … | βn
Marcela HernandezMarcela Hernandez
Slide 18
ELIMINACION DE RECURSIVIDAD IZQUIERDA
Tipos de recursividad
• Directa. Una gramática G es recursiva si tiene alguna regla deproducción que sea recursiva por la izquierda
• Indirecta. Si, a partir de una forma sentencial que empieza por un no terminal se puede derivar una nueva forma no sentencialdonde reaparece al principio el no terminal
A := Aα
Aα =>* Aβα
Marcela Hernandez
Slide 19
Eliminación de la recursividad
• Directa
• Indirecta
A := βA’A’ := αA’
A’ := ε
A := Aα | β
Ordenar No terminales: A1, A2, … An
For i := 1 To n Do
For j := 1 To i – 1 Do
Sustituir cada Ai := Aj β por Ai := α1 β | α2 β| αk β
donde Aj := α1 | α2 | … | αk producciones actuales de Aj
Eliminar la recursividad directa de Ai
Marcela Hernandez
Slide 20
ELIMINACION DE AMBIGÛEDADUna gramática ambigua permite más de una derivación para la misma forma sentencial por lo que también habrá más de un árbol de derivación para la misma. Por ello bastacon encontrar dos árboles derivación distintos para la misma forma sentencial para demostrar que una gramática es ambigua.
Para eliminar este tipo de ambigüedad, esnecesario, primero eliminar:
- Factores comunes izquierdos inmediatos y No-inmediatos.- Recursividad izquierda inmediata y No-inmediata.
Marcela Hernandez