Story Transcript
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Compiladores: Parsing ascendente Francisco J Ballesteros LSUB, URJC
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 1 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing ascendente Normalmente utilizaremos parsers descendentes para problemas pequeños cuando podemos escribir uno predictivo fácilmente En otro caso se suelen utilizar parsers ascendentes trabajan desde las hojas a la raíz del árbol sintáctico intentan reducir los terminales al símbolo inicial de la gramática
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 2 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing ascendente Por ejemplo, para esta gramática EXPR ::= EXPR + TERM | TERM TERM ::= TERM * FACT | FACT FACT ::= ( EXPR ) | num
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 3 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing ascendente EXPR ::= EXPR + TERM | TERM TERM ::= TERM * FACT | FACT FACT ::= ( EXPR ) | num
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 4 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing ascendente EXPR ::= EXPR + TERM | TERM TERM ::= TERM * FACT | FACT FACT ::= ( EXPR ) | num
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 5 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing ascendente EXPR ::= EXPR + TERM | TERM TERM ::= TERM * FACT | FACT FACT ::= ( EXPR ) | num
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 6 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing ascendente EXPR ::= EXPR + TERM | TERM TERM ::= TERM * FACT | FACT FACT ::= ( EXPR ) | num
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 7 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing ascendente EXPR ::= EXPR + TERM | TERM TERM ::= TERM * FACT | FACT FACT ::= ( EXPR ) | num
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 8 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing ascendente EXPR ::= EXPR + TERM | TERM TERM ::= TERM * FACT | FACT FACT ::= ( EXPR ) | num
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 9 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing ascendente EXPR ::= EXPR + TERM | TERM TERM ::= TERM * FACT | FACT FACT ::= ( EXPR ) | num
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 10 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing ascendente EXPR ::= EXPR + TERM | TERM TERM ::= TERM * FACT | FACT FACT ::= ( EXPR ) | num
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 11 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing ascendente EXPR ::= EXPR + TERM | TERM TERM ::= TERM * FACT | FACT FACT ::= ( EXPR ) | num
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 12 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing ascendente EXPR ::= EXPR + TERM | TERM TERM ::= TERM * FACT | FACT FACT ::= ( EXPR ) | num
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 13 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing ascendente
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 14 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing ascendente Se intenta todo el tiempo reducir la entrada Mirando qué producciones podemos aplicar Y si hay que mirar más terminales de la entrada o hay que aplicar una producción y reducir
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 15 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing ascendente Esto es, dada EXPR ::= EXPR + TERM | TERM TERM ::= TERM * FACT | FACT FACT ::= ( EXPR ) | num
derivamos del final al principio... ->EXPR ->TERM ->TERM * ->TERM * ->FACT * ->( EXPR ->( EXPR ->( EXPR ->( EXPR ->( TERM ->( FACT ->( 3
FACT 8 8 ) * 8 + TERM + FACT + 5 + 5 + 5 + 5
) ) ) ) ) )
* * * * * *
8 8 8 8 8 8
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 16 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing ascendente El parsing ascendente construye una derivación right-most a la inversa (del final al principio) ->( 3 ->( FACT ->( TERM ->( EXPR ->( EXPR ->( EXPR ->( EXPR ->FACT * ->TERM * ->TERM * ->TERM ->EXPR
+ 5 + 5 + 5 + 5 + FACT + TERM ) * 8 8 8 FACT
) ) ) ) ) )
* * * * * *
8 8 8 8 8 8
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 17 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Gramáticas para parsing ascendente Naturalmente, que no sean ambiguas salvo por ambigüedades resolubles por precedencia de operadores Tampoco recursivas por la derecha igual que bottom-up no tolera las recursivas por la izquierda puesto que crearíamos infinitas reducciones
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 18 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Handle Un handle es un substring (de terminales y no terminales) que encaja con el cuerpo de una producción que si reducimos permite llegar al símbolo inicial
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 19 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Handle: ejemplos en ->( 3
+ 5
) * 8
tenemos el handle 3
por la producción FACT ::= num
para dar... ->( FACT + 5
) * 8
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 20 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Handle: ejemplos en ->( EXPR + TERM ) * 8
tenemos el handle EXPR + TERM
por la producción EXPR ::= EXPR + TERM
y al reducir ->( EXPR ) * 8
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 21 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Handle: ejemplos en ->( EXPR ) * 8
tenemos el handle ( EXPR )
por la producción FACT ::= ( EXPR )
y al reducir ->FACT * 8
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 22 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing ascendente El proceso de parsing ascendente: Se parte de la cadena (de tokens) a la entrada Se localiza un handle Se reduce Se localiza otro Se reduce ...
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 23 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing ascendente con shift y reduce El proceso de parsing ascendente: mantiene una pila de símbolos (terminales y no terminales) si no tenemos un handle: metemos más terminales en la pila si tenemos un handle en la cima de la pila, lo reducimos Tenemos dos operaciones: shift: meter terminales en la pila reduce: cambiar N simbolos de la cima (handle) por parte izqda.
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 24 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Ejemplo de parsing ascendente Repitamos otra vez: Pila: $
Entrada: . ( 3 + 5 ) * 8
donde... $ marca el fondo de la pila: pila vacía . marca por dónde vamos en la entrada
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 25 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Ejemplo de parsing ascendente $ . ( 3 + 5 ) * 8
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 26 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Ejemplo de parsing ascendente $ . ( 3 + 5 ) * 8
shift $ ( ( . 3 + 5 ) * 8
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 27 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Ejemplo de parsing ascendente $ ( ( . 3 + 5 ) * 8
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 28 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Ejemplo de parsing ascendente $ ( ( . 3 + 5 ) * 8
shift $ ( 3 ( 3 . + 5 ) * 8
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 29 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Ejemplo de parsing ascendente $ ( 3 ( 3 . + 5 ) * 8
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 30 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Ejemplo de parsing ascendente $ ( 3 ( 3 . + 5 ) * 8
reduce $ ( FACT ( 3 . + 5 ) * 8
con handle 3 FACT ::= num
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 31 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Ejemplo de parsing ascendente $ ( FACT ( 3 . + 5 ) * 8
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 32 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Ejemplo de parsing ascendente $ ( FACT ( 3 . + 5 ) * 8
reduce $ ( TERM ( 3 . + 5 ) * 8
con handle FACT TERM ::= FACT
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 33 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Ejemplo de parsing ascendente $ ( TERM ( 3 . + 5 ) * 8
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 34 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Ejemplo de parsing ascendente $ ( TERM ( 3 . + 5 ) * 8
reduce $ ( EXPR + ( 3 . + 5 ) * 8
con handle TERM EXPR ::= TERM
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 35 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Ejemplo de parsing ascendente $ ( EXPR ( 3 . + 5 ) * 8
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 36 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Ejemplo de parsing ascendente $ ( EXPR ( 3 . + 5 ) * 8
shift $ ( EXPR + ( 3 + . 5 ) * 8
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 37 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Ejemplo de parsing ascendente $ ( EXPR + ( 3 + . 5 ) * 8
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 38 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Ejemplo de parsing ascendente $ ( EXPR + ( 3 + . 5 ) * 8
shift $ ( EXPR + 5 ( 3 + 5 . ) * 8
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 39 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Ejemplo de parsing ascendente En conclusión: stack . input $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $
and then...
. ( 3 + 5 ) * 8 shift ( . 3 + 5 ) * 8 shift ( 3 . + 5 ) * 8 reduce ( FACT . + 5 ) * 8 reduce ( TERM . + 5 ) * 8 reduce ( EXPR . + 5 ) * 8 shift ( EXPR + . 5 ) * 8 shift ( EXPR + 5 . ) * 8 reduce ( EXPR + FACT . ) * 8 reduce ( EXPR + TERM . ) * 8 reduce ( EXPR . ) * 8 shift ( EXPR ) . * 8 reduce FACT . * 8 reduce TERM . * 8 shift TERM * . 8 shift TERM * 8 . reduce TERM * FACT . reduce TERM . reduce EXPR .
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 40 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Conflictos Si hay varias reducciones de handles posibles tenemos un conflicto reduce/reduce Si no se sabe si mirar más símbolos o reducir tememos un conflicto shift/reduce
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 41 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Handles A cada string como ( FACT . + 5 ) * 8
la llamamos forma sentencial. A la derecha del handle sólo hay terminales ... $ ( $ ( $ ( $ ( ...
. 3 + 5 ) * 8 3 . + 5 ) * 8 FACT . + 5 ) * 8 TERM . + 5 ) * 8
shift reduce reduce reduce
NB: por que la derivación es right-most
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 42 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Handles El handle está siempre en la cima de la pila ... $ ( $ ( $ ( $ ( ...
. 3 + 5 ) * 8 3 . + 5 ) * 8 FACT . + 5 ) * 8 TERM . + 5 ) * 8
shift reduce reduce reduce
Y por eso podemos utilizar una pila
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 43 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Handles A lo mejor se pueden aplicar varias producciones pero un handle sólo lo es si nos deja derivar hasta el símbolo de inicio El parsing bottom-up radica en identificar handles no hay algoritmo capaz de hacerlo en general para ciertas gramáticas, ciertas heurísticas funcionan Esas gramáticas son las que debemos utilizar ( SLR , LALR )
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 44 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Identificación de Handles Mantenemos en la cima de la pila un prefijo de un handle Hasta que tenemos el handle (y lo reducimos) El conjunto de prefijos es un lenguaje regular Un AFND puede reconocer los handles
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 45 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsers bottom-up, autómatas e Items Escribimos la gramática Utilizamos herramientas para construir el AFND que reconoce los handles El código que ejecuta el autómata es el parser
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 46 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsers bottom-up, autómatas e Items El autómata intenta reducir los handles En un instante, tiene múltiples estados activos (es ND) Cada estado es un punto en un proceso de reducir un handle
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 47 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsers bottom-up, autómatas e Items Por ejemplo, para FACT ::= ( EXPR )
el autómata intenta avanzar según FACT FACT FACT FACT
::= . ( EXPR ) ::= ( . EXPR ) ::= ( EXPR . ) ::= ( EXPR ) .
Y lo mismo para el resto de reducciones posibles A estas producciones con el . indicado las llamamos items LR(0), o items
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 48 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsers bottom-up, autómatas e Items Si tenemos en la pila y entrada $ ... ( EXPR
) ...
Entonces FACT ::= ( EXPR . )
indica que ( EXPR .
es un prefijo del cuerpo de una producción reducible
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 49 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsers bottom-up, autómatas e Items En cada estado el autómata mantiene el conjunto de items que indican que hemos visto hasta ahora para poder reducir usando una producción
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 50 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsers bottom-up, autómatas e Items Herramientas como yacc toman la gramática generan un AFND para reconocer los handles lo convierten an un AFD cuyos estados son conjuntos de items Las gramáticas aceptables son aquellas no ambiguas en las que las heurísticas de selección de items funcionan esto es, en las que los items son viables para la derivación esto es, en las que lo que reducimos son handles
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 51 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Tipos de gramáticas LR: miran la entrada left-right SLR: simple LR LALR: LR con look-ahead Dicho de otro modo... aquellas para las que las herramientas funcionan (SLR, LALR) pero no hay algoritmo para todas las gramáticas libres de contexto
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 52 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing SLR Si en la pila y entrada tenemos $ ... a b c
x ...
Reducir si d ::= a b c .
es un item en el estado actual y x puede seguir a d según la gramática si x pertenece a follow(d), como veremos...
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 53 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing SLR Si en la pila y entrada tenemos $ ... a b c
x ...
Desplazar si d ::= a b c . x ...
es un item en el estado actual
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 54 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing SLR Y si con estas reglas no se puede (hay conflictos) Decimos que la gramática no es SLR! Pero normalmente incluirmos información de precedencia para resolver algunos conflictos
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 55 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing LR Y ahora un ejemplo de un trozo de un AFD para un SLR
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 56 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing LR
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 57 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing LR(1) Es como el SLR Pero utiliza un token de look ahead. Se le llama LR(1), o LALR (look-ahead LR) Los items LR(1) son: FACT ::= . num, x
Que quieren decir intentando reducir con esta producción en este punto para reducir sólo si el siguiente símbolos es x
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 58 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing LALR El token de look-ahead hace que más gramáticas funcionen que identifiquen handles al reducir y no partes derechas de producciones cualesquiera Luego las LALR contienen a las SLR
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 59 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Parsing LALR y yacc Yacc es una herramienta que genera el parser
dada la gramática El parser es un programa para el autómata (librería) Mas tablas generadas por yacc para describir las transiciones (goto) para describir acciones (action) Las acciones son como no-terminales encajan con la cadena vacía se ejecutan cuando se reducen
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 60 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
First y Follow first (X) Es el conjunto de los símbolos terminales que para las producciones X ::= ...
pueden aparecer como primer terminal a la derecha ej. A ::= x B | C C ::= y ... first(A) = { x, y }
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 61 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
First y Follow follow (X) Es el conjunto de los símbolos terminales que pueden aparecer como primer terminal a la derecha de X en una forma sentencial aceptable ej. A ::= x B C y C ::= z | ... follow(B) = { z, y }
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 62 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
First y Follow Cuando tengamos conflictos o escribamos la gramática es útil pensar en first y follow Intuitivamente, queremos una gramática lo más rígida posible como hacíamos con parsing predictivo. Si tenemos problemas, podemos aderezar con más puntuación! ej: if condicion sentencia
vs if condicion { sentencia }
o if (condicion) { sentencia }
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 63 of 64
Compiladores: Parsing ascendente - (c)2014 LSUB
1/25/16, 2:48 PM
Questions? Francisco J Ballesteros LSUB, URJC http://lsub.org (http://lsub.org)
http://127.0.0.1:3999/s06.bottomup.slide#1
Page 64 of 64