Sintaxis y Parsers LL1

Temas:

  1. Gramáticas
  2. Gramáticas LL1
  3. Ejercicio interactivo gramáticas LL1
  4. Parser LL1
  5. Ejercicio interactivo parsing LL1

Bibliografía:

  1. Louden 4.2, 3.2.
  2. Ullman 4.2.1.
  3. Apuntes de la teórica.

Qué es una Gramática

$G=(V,T,P,S)$

  • Conjunto de símbolos terminales $T$ (if, int, { ... )
  • Conjunto de símbolos no terminales $V$ (IfStmt, VarDecl, BlockExpr)
  • Conjunto de producciones $P$ (BlockExpr -> { CompoundStmt })
  • Un símbolo inicial $S$

Referencia de tokens no terminales de C.

Cómo escribimos una gramática

  • <simbolo_no_terminal>
  • simbolo_terminal
  • Producción: <un_no_terminal> ::= <simbolos> generados

Derivación: aplicar producciones sucesivamente

Gramática de Familang


                    <r> ::= <r> hijo_de <r>
                    <r> ::= <r> hermano_de <r>
                    <r> ::= nombre

Ejemplo 1


                        Bart hijo_de Homero hermano_de Lisa
Estado Producción ¿Cuál? 
<r>
 
<r> ::= <r> hijo_de <r>
 1 
<r> hijo_de <r>
 
<r> ::= <r> hermano_de <r>
 2 
<r> hijo_de <r> hermano_de <r>
 
<r> ::= nombre
 1 
nombre hijo_de <r> hermano_de <r>
 
<r> ::= nombre
 1 
nombre hijo_de nombre hermano_de <r>
 
<r> ::= nombre
 1 
nombre hijo_de nombre hermano_de nombre

Ejemplo 2


                        Bart hijo_de Homero hermano_de Lisa
Estado Producción ¿Cuál? 
<r>
 
<r> ::= <r> hermano_de <r>
 1 
<r> hermano_de <r>
 
<r> ::= <r> hijo_de <r>
 1 
<r> hijo_de <r> hermano_de <r>
 
<r> ::= nombre
 1 
nombre hijo_de <r> hermano_de <r>
 
<r> ::= nombre
 1 
nombre hijo_de nombre hermano_de <r>
 
<r> ::= nombre
 1 
nombre hijo_de nombre hermano_de nombre

Gramáticas LL1

  • No recursivas por izquierda
  • No ambíguas

familang original

<r> ::= <r> hijo_de <r>
<r> ::= <r> hermano_de <r>
<r> ::= nombre

No ambígua:

<r> ::= nombre hijo_de <r>
<r> ::= <r> hermano_de nombre
<r> ::= nombre

LL1 (no recursiva por izquierda):

<r> ::= nombre <r0>
<r0> ::= 
<r0> ::= hijo_de <r> 
<r0> ::= hermano_de <r>

Ejercicio interactivo familang v2


                    <r> ::= nombre <r0>
                    <r0> ::= 
                    <r0> ::= hijo_de <r> 
                    <r0> ::= hermano_de <r>
  1. Ejemplo: Maggie hermano_de : Lisa hijo_de : Homero y_de Marge y_de Bart hermano_de Maggie
  2. Maggie hermano_de Lisa hermano_de Bart hijo_de: Homero hijo_de Abraham y_de Marge hermano_de Patty
  3. Maggie hijo_de : Homero hijo de Abraham y_de Marge hermano_de : Patty y_de Selma
  4. Luke hermano_de : Alex y_de Haley hijo_de : Phil hijo_de Frank y_de Claire hermano_de Mitchell hijo_de : Dede y_de Jay

¿Qué es un parser LL1?

Parser descendiente recursivo con stack explícito.

Desc rec LL1
Funciones Derivaciones
cola de tokens cola de tokens
callstack Stack de estado
if ó switch Tabla M $M \in V \times T \rightarrow P$ 

                            stack_estado=[símbolo_inicial]
                            cola=listado_de_tokens
                            while len(cola) > 0:
                                if cola[0]==stack_estado[0]:
                                    cola.pop()
                                    stack_estado.pop()
                                else:
                                    produccion = M[
                                        stack_estado[0],
                                        cola[0]
                                    ]
                                    stack_estado.push(
                                        *produccion.lado_derecho
                                    )
                        

                            stack_estado=[símbolo_inicial]
                            cola=listado_de_tokens
                            def match():
                                cola.pop()
                                stack_estado.pop()
                            def apply(produccion):
                                stack_estado.push(
                                    *produccion.lado_derecho
                                )

                            while len(cola) > 0:
                                if cola[0]==stack_estado[0]:
                                    cola.pop()
                                    stack_estado.pop()
                                else:
                                    produccion = M[
                                        stack_estado[0],
                                        cola[0]
                                    ]
                                    stack_estado.push(
                                        *produccion.lado_derecho
                                    )
                        

                            stack_estado=[símbolo_inicial]
                            cola=listado_de_tokens
                            def match():
                                cola.pop()
                                stack_estado.pop()
                            def apply(produccion):
                                stack_estado.push(
                                    *produccion.lado_derecho
                                )

                            while len(cola) > 0:
                                if cola[0]==stack_estado[0]:
                                    match()
                                else:
                                    apply(M[
                                        stack_estado[0],
                                        cola[0]
                                    ])

Ejercicio de parsing interactivo familang v2


                    <r> ::= nombre <r0>
                    <r0> ::= 
                    <r0> ::= hijo_de <r> 
                    <r0> ::= hermano_de <r>
  1. Ejemplo: Maggie hermano_de : Lisa hijo_de : Homero y_de Marge y_de Bart hermano_de Maggie
  2. Maggie hermano_de Lisa hermano_de Bart hijo_de: Homero hijo_de Abraham y_de Marge hermano_de Patty
  3. Maggie hijo_de : Homero hijo de Abraham y_de Marge hermano_de : Patty y_de Selma
  4. Luke hermano_de : Alex y_de Haley hijo_de : Phil hijo_de Frank y_de Claire hermano_de Mitchell hijo_de : Dede y_de Jay

¿Preguntas?

A continuación, intervalo y laboratorio.