Ejemplo, ejercicio para el metodo ll(1)

EJEMPLO DE UN ANALIZADOR SINTACTICO DESCENDENTE (METODO LL)

Análisis sintáctico descendente Las gramáticas que son susceptibles de ser analizadas sintácticamente de forma descendente mediante un análisis predictivo y consultando un únicamente un símbolo de entrada pertenecen al grupo LL(1). A partir de gramáticas LL(1) se pueden construir analizadores sintácticos descendentes predictivos(ASDP), que son ASD sin retroceso. Conjuntos de predicción •  Son conjuntos de símbolos terminales – ayudan a predecir qué regla se debe aplicar Para el no terminal que hay que derivar.  • Se construyen a partir de los símbolos de Las partes derechas de las producciones De la gramática.  • El analizador consulta el siguiente símbolo En la entrada si pertenece al conjunto de Predicción de una reglaaplica esa regla, Si no da error. Ejemplo de conjuntos de predicción Supóngase la entrada “”babxcc””, que se han leído ya los símbolos subrayados en babxcc”, y la gramática es: –AaBc|xC|B – B bA –Cc • ¿Qué producción debe tomar para seguir el análisis? –AaBc|xC|B – B  bA –Cc babxcc

La cadena de derivaciones ha sido: – A  B  bA  baBc  babAc Ahora hay que seguir desarrollando lavariable A Utilizando los conjuntos de predicción. Como la siguiente letra es una “”x”” se elige la Segunda opción (A  x C) Ejemplo de no conjuntos de predicción • La gramática 2

–AaBc|aC|B No cumple los requisitos para LL(1) porque si aparece una “a” en la entrada hay dos posibles opciones. Luego el análisis: – no puede ser predictivo y, la gramática no es LL(1). Ejemplo de una gramática pararealizar el método LL1 explicado en clase EOE’ E’barraOE’/3 OIO’ O’IO’/3 Isim / parabE parceC Cast/int/3

Calculo de los PRIMEROS o first. El primero de E será el primero de O debido a que O es un no terminal, el primero de O será el primero de I, (también en I es un no terminal) entonces el primero de E será sim y parab (la E que está en la tabla se omite debido a que esta es un no terminalmás adelante nos servirá para el conjunto de los siguientes) EOIsim/parab Así hemos empezado a realizar una simple derivación E= {sim,parab} La siguiente será E’, el primero de E’ será barra y 3 debido a que barra y épsilon son terminales. E’barra, 3 E’= {barra, 3} El primero de O será sim y parab debido a que el primero de O es el primero de I OIsim,parab O= {sim,parab} El primero de O’también será sim,parab y al tener un “or” también será épsilon. O’Isim,parab O’= {sim, parab, 3 } 3

El primero de C será ast, sum, int, 3 debido a que son terminales

Asi es como queda el conjunto de los primeros: E E’ O O’ I C {sim, parab} {barra, 3} {sim, parab} {sim, parab, 3} {sim, parab} {ast, sum, int, 3}

A continuación seguiremos con el conjunto de los SIGUIENTES o follow. Para hacereste conjunto lo primero será observar el conjunto de las producciones (marcadas en amarillo) EOE’ E’barraOE’/3 OIO’ O’IO’/3 Isim / parabE parceC Cast/int/3 Así es como buscaremos el conjunto de los siguientes: De acuerdo a las reglas, cuando iniciamos las relación SIGUIENTES, debemos ubicar al No Terminal Inicial; en este caso es E, al principio ponemos el signo $ que indica un “fin dearchivo o de cadena”. Para obtener los “siguientes” de E buscamos a E en las producciones. Isim / parab E parce C Una vez ubicado colocamos en la relación siguiente el token o el terminal a la derecha, solo eso. No te olvides de colocar $ al final de la relación. E= {parce, $} Siguiendo con el No terminal E’, lo buscamos dentro de las producciones. EOE’ 4

Una vez localizado nos damos cuenta que ala derecha no hay token ni un No terminal. Dentro de las reglas a seguir para este método nos indica que al pasar esto, tenemos que colocar los “Siguientes” de la No terminal que se ubica antes de la flecha, en este caso es E. “los siguientes de E’ son los siguientes de E” E= E’= {parce, $} {parce, $}

Para entrar los siguientes de O nos vamos a buscarlo dentro de las producciones. EOE’ Lo...