Es importante determinar cuando usar SHIFT o REDUCE en la Pila, con el algoritmo de resolución de conflictos resolveremos los conflictos de caso SHIFT/REDUCE y REDUCE/REDUCE.
Recordando:
La acción SHIFT mueve o coloca un nuevo valor terminal en la pila.
____ | XYZ => ____X | YZ
La acción REDUCE puede eliminar cero o mas símbolos en la pila (del lado derecho), o colocar un símbolo no-terminal en la pila (en el lado izquierdo de la producción).
Los conjuntos representados por expresiones regulares son llamados conjuntos regulares.
Una gramática es libre de contexto (GLC) cuando en el lado izquierdo de la gramática solo aparece símbolos terminales.
Nuevos conceptos:
Handle: es una reducción que permite hacer otras reducciones hasta llegar al símbolo inicial.
Prefijos viables: es una parte del handle que se llevara al símbolo inicia.
LWB Es un prefijo viable (Alfa, beta y omega)
LW Es un prefijo viable (tambien las derivaciones de LWB son prefijos viables)
L Es un prefijo viable
Item: es una producción con un punto "." en algun lugar del lado derecho de la produccion. Para T -> (E) los items son:
T->. ( E )
T-> (.E )
T-> ( E.)
T-> ( E ).
Nota: Los items que vayan a lambda son LR(0) y su item es
T->L => T -> . (L es Lambda)
Donde el cero de LR representa la cantidad de pasos que ha tomado.
Condiciones:
1. Se debe aplicar REDUCE solo si el resultado permite la eventual transición al símbolo inicial.
2. En un caso SHIFT/REDUCE, el handle debe estar en el tope de la pila y jamas dentro de ella. El detalle es que no existen algoritmos eficientes para detectar los handles.
3. Para cualquier gramática, el conjunto de prefijos viables es un conjunto regular.
Nota: todas las gramáticas para un compilador son SLR.
Reconocer los prefijos viables (ver laminas 9):
Para poderlos reconocer debemos crear un AFN (autómata finito no determinista), lo siguiente son las condiciones para poder construir un AFN.
- Para un estado S' -> .E (Notese el punto), la transición será S' -> E. y la llamamos transición E.
- Para cada item E -> L . XB y producción X -> Y, realizaremos una transición por cada producción de X. Se va a la transición inicial de la producción que trascendió. En ese caso E, y se coloca X.
- Un error común es que se dupliquen las mismas producciones, lo correcto es redireccionar a los estados adecuados.
- Cuando la transicion sea un simbolo terminal, la transicion llegara hasta ese simbolo.
- T-> . int*T (Transicion por int) T->int . * T (Transicion por *) T->int * . T
Una vez construido el AFN, lo que sigue es pasarlo a un autómata finito determinista (AFD). Esto se hace debido a que el AFN no es eficiente.
AFD y los posibles conflictos (ver laminas 10):
En el AFD, podemos observar que en cada estado hay conjuntos de items. Se llaman colecciones canónicas de items.
En este conjunto de items, generalmente pueden haber conflictos de tipo REDUCE/REDUCE o REDUCE/SHIFT, el siguiente es un conjunto de razonamientos para identificarlos.
Existe un conflicto REDUCE/REDUCE si en un estado existen dos items con la opcion de aplicar un REDUCE. Ejemplo:
E -> T
T -> E + T
Existe un conflicto SHIFT/REDUCE si en un estado existe un item para hacer un SHIFT, y otro para REDUCE.
Si se tiene un conflicto SHIFT/REDUCE en una producción T, se hará un FOLLOW (los siguientes de T)a la producción del estado y comparamos con el siguiente caracter al lado de la barra, si existe hacemos un movimiento REDUCE, de lo contrario SHIFT.
Ejemplo:
S' -> E (Esta producción no se toma en cuenta)
E -> T + E | T
T -> int * T | int | ( E )
Follow(T) = {"+", ")", $}
Como * no pertenece a follow de T, realizaremos un SHIFT, moviendolo al estado 11. Como no hay item al final en alguno del estado 11, no hay conflictos.
Notas:
- En el libro del dragon se usa otra forma de construcción.
- El algoritmo para resolver este problema usa SLR(0), no se puede usar LR(0).
PASO A PASO:
- Tenemos la gramatica
- Expandir gramatica (para obtener el estado inicial de AFN)
- Calcular los items de la gramatica.
- Construir el AFN con transiciones lambda.
- Transformar el AFN-L a AFD llamado R.
- Ver los posibles conflictos del AFD y calcular los follows de los no-terminales presentes en el conflicto.
- Aplicar el algoritmo para R recibiendo como entrada la pila R(stack)
Ultimos detalles
- Para la proxima clase se explicara la tabla de simbolos.
- Ll(1) - Haskell (transforma la gramatica)
- SLR - CUP
- El examen del jueves va hasta Ll(1)
