Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Construcción eficiente de tablas de análisis sintáctico LALR

No description
by

Turko Rdgz

on 8 November 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Construcción eficiente de tablas de análisis sintáctico LALR

Crear conjunto ir_A(Goto)
Vamos a crear nuestros goto (Si,α) en donde Si es el conjunto que vamos a crear y α va ser el terminal o no terminal a donde nos moveremos, copiando sus LookaHead de la producción padre.
Construcción de la tabla
-Construir la tabla teniendo en cuenta que un estado puede ahora tener desplazamientos (D) y reducciones (R).
-El símbolo $ es un símbolo valido de lectura adelantada.
-Si es una reducción con la forma AXYZ. , incluir la regla gramatical AXYZ para todas las entradas en el Siguiente (A).
-Si es un desplazamiento, poner el estado al que transita
Transiciones según plantilla LR
Agregar a cada producción un punto del lado izquierdo de la producción y el símbolo de dolar como símbolo de pre-analisis según el método LALR
Gramática Aumentada
Sea la gramática G:
1.- S -> A
2.- S -> xb
3.- A -> aAb
4.- A -> B
5.- B -> x

Metodo LALR
1.-Construir la colección de conjuntos de elementos LR.

2.-Para cada conjunto en LR, encontrar todos los conjuntos con los mismos elementos y sustituir todos por su unión.

3.-Construir las acciones de análisis sintáctico para cada nuevo estado.
Construcción eficiente de tablas de análisis sintáctico LALR
Se aumentará de la siguiente forma:

0.- S' -> S,$
1.- S -> A
2.- S -> xb
3.- A -> aAb
4.- A -> B
5.- B -> x



0.- S' -> .S {$}
1.- S -> .A {$}
2.- S -> .xb {$}
3.- A -> .aAb {$}
4.- A -> .B {$}
5.- B -> .x {$}
0.- S' -> .S
1.- S -> .A
2.- S -> .xb
3.- A -> .aAb
4.- A -> .B
5.- B -> .x
S1:Goto(S0,S):

S' -> .S {$}

S2:Goto(S0,A):

S' -> .A {$}

S3:Goto(S0,B):

A' -> .B {$}
S4:Goto(S0,x):

S -> .xb {$}
A -> .x {$}

S5:Goto(S0,a):

A -> .aAb {$}
A -> .B {$}
B -> .x {$}
S6:Goto(S5,A):

A -> a.Ab {$}
A -> .aAb {b}
A -> .B {b}
B -> .x {b}

S7:Goto(S5,a)(S7,a):

A -> a.Ab {b}
A -> .aAb {b}
A -> .B {b}
B -> .x {b}
S8:Goto(S5,B)(S7,B):

A -> B. {$}

S9:Goto(S5,x)(S7,x):

B -> .x {$}

S10:Goto(S6,b):

S -> xb. {$}

S11:Goto(S7,A)

S -> aA-b {b}
S12:Goto(11,b):

S -> aAb. {$}

S13:Goto(S4,b)

S -> xb. {$}
Construcción eficiente de la tabla
Podemos hacer varias modificaciones al algoritmo anterior para evitar construir la colección completa de conjuntos de elementos LR(1), en el proceso de crear una tabla de análisis sintáctico LALR(1).

1. Podemos representar cualquier conjunto de elementos I mediante su corazón, es decir, mediante aquellos elementos que sean el elementos inicial , [S’->.S] o [S’, -> .S, $], o que tengan el punto en algún lugar que no sea el principio del cuerpo de la producción.
2. Podemos construir los corazones de los elementos LALR(1) a partir de los corazones de los elementos LR(0), mediante un proceso de propagación y generación espontánea de lecturas adelantadas.
3. Si tenemos los corazones LALR(1), podemos generar la tabla de análisis sintáctico LALR(1) cerrando cada corazón, usando la función CERRADURA y después calculando las entradas en la tabla, como si los conjuntos de elementos LALR(1) fueran conjuntos de elementos LR(1) canónicos.
Ejemplo
Sea la gramática

G =

S’- > S

S -> E1

S-> 2E3

S-> X3

S-> 2X1

E->4

X-> 4
Ejercicio
Resultado
Conclusiones
Es importante recalcar que lo necesario para poder construir tablas LALR es saber los algoritmos de construcción de tablas , y además, saber el algoritmo de la CERRADURA . Los autómatas LALR tienen la misma cantidad de estados que los SLR, porque son autómatas LR reducidos. Pero, el LALR a diferencia el SLR tiene un símbolo de pre-análisis lo que le permite saber a qué hacer en un caso donde un SLR tendría problemas.
Judith Andrea Quintana Meneses
Eder Uriel Rodríguez Samperio
Bibliografia
http://gabriel-a60258.comuv.com/web_documents/sem14.htm
http://cic.puj.edu.co/wiki/lib/exe/fetch.php?media=materias:compi:comp_sesion11_2008-1.pdf
www.escet.urjc.es/~ci/material/7_analisis_sintactico_LALR_1.pdf‎
Tablas de analisis sintactico y metodo LALR
Full transcript