Compiladores

Proceso de parseo Tema 23
Parseo Top-down Dr. Luis A. Pineda ISBN: 970-32-2972-7 Del Latin: Partes del habla o categorías gramáticales Si G en una CFG sober Σ & x ∈ Σ *, parsear x consiste en encontrar una derivación para x en G o determinar que ésta no existe (i.e. por lo que x no está en el lenguaje de G).

Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

Proceso de parseoAntecedentes: simulación de derivaciones en G por un a PDA: – Top-down (derivaciones más izquierdas) – Bottom-up (derivaciones más derechas) Pero, estos procesos son no determinísticos y no proveén de un algoritmo directamente!

Algoritmos de parseo
Algoritmo trivial: explorar todas las trayectorias (en el espacion no determinístico) en cierto orden (i.e. depth first o breath first) & ver si algunatrayectoria termina exitosamente – Muy costoso: búsqueda exponencial!

Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

Algoritmos de parseo
Enfrentar el no-determinismo directamente: – Utilizar toda la información disponible en cada paso de la computación (local) y seleccionar la mejor alternativa (en algunos casosdeterminísticamente) – Capitalizar la forma de la gramática: Para seleccionar la siguiente movida considerar no sólo el símbolo hasta arriba del stack, sino también uno o más de los símbolos que siguen en la cinta!
Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

Top-down Lookahead Parser TopMovida 1:
– Si el símbolo hasta arriba del stack es una

variable en el lado izquierdo de unaproducción, reemplazar dicha variable por el lado derecho de la producción – Inspeccionar el símbolo actual (i.e. consumir) y escoger sólo producciones que tengan a dicho símbolo como el más izquierdo del lado derecho! – Usar no-determinismo sólo si no hay opción!
Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

1

Top-down Lookahead Parser TopMovida 2: – Si el símbolo de entradacorresponde con el símbolo hasta arriba del stack, consumir el símbolo y pop.
[ ] $

Simulación top-down topL = El lenguaje de los paréntesis balanceados
Cadena de entrada Control de edos. finitos

S → T$ T → [T]T T→Λ

Una gramática no-ambigua

La lógica de la máquina: Cancelar “[” en la cinta con “[” en el lado derecho de una producción; igual para “]”

Z0

Dr. Luis A. Pineda,IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

AP no determinístico
Id 1 2 3 4 5 6 7 estado q0 q1 q1 q1 q1 q1 q1 entrad Λ Λ Λ [ ] $ Λ top del stack Z0 S T [ ] $ Z0 Movida(s) (q1, SZ0) (q1, TZ0 ) (q1, [T]T), (q1, Λ) (q1, Λ) (q1, Λ) (q1, Λ) (q2, Z0 ) ninguna

Simulación top-down top-

S → T$ T → [T]T T→Λ

[ ] $

Control de edos. finitosMovida 0:

S Z0

S

Otras combinaciones

Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

Simulación top-down top-

S → T$ T → [T]T T→Λ [ ] $

Simulación top-down top-

S → T$ T → [T]T T→Λ

[ ] $

Control de edos. finitos

Control de edos. finitos

Movida 1:

T $ Z0

S ⇒ T$

La decisión esno-determinística cuando T está hasta arriba del stack: podemos escoger [T]T o Λ

T $ Z0

S ⇒ T$

Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

2

Simulación top-down topClaramente, escoger Λ no es una idea muy buena! [ ] $
Control de edos. finitos

S → T$ T → [T]T T→Λ

Ver hacia adelande: Lookahead adelande:Lookahead
Podemos ver el símbolo actual en la cinta (i.e. consumiendo el símbolo!) [ ] $
Contro de edos. finitos

S → T$ T → [T]T T→Λ

T $ Z0

Una producción es útil si su símbolo más izquierdo del lado derecho es el mismo que el símbolo actual en la cinta de entrada

T $ Z0

Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN:...