Resumen: Semana del 12 al 19 de junio

(1/8)

Introducción al LALR

• El Look-Ahead LR (o LALR) es un método simplificado para implementar gramáticas LR, basada en la LR(0)
• Como la SLR, tiene la ventaja de requerir menos estados que el método básico LR
• Igual que en la LR(0) y la SLR, cada objeto incluye un símbolo (usualmente un punto) para determinar dónde se encuentra la hilera (p. ej. A → B·CD)
• Al igual que con otras gramáticas LR, usa la producción inicial S' → S

(2/8)

Lookahead en la gramática LALR

• La producción LALR incluye además un símbolo de lookahead (que se usa para determinar por adelantado qué elemento sigue para proseguir con la gramática)
• Una producción así tendría la forma A → B·CD, e (donde e es el símbolo de lookahead)
  • El símbolo de lookahead corresponde al Primero(βa) (es decir, el Primero de lo que quede después de avanzar el punto a través de un no-terminal)
  • El lookahead también aparece, de una forma u otra, en los LR(n) tales que n > 0

(3/8)

Operaciones en la gramática LALR

• Igual que con la SLR y la LR(0), la gramática LALR implementa dos operaciones: clausura y desplazamiento
  • Estas no presentan mayores variaciones con respecto a la SLR y LR(0), salvo por el agregado del lookahead y el corazón, que se verá más adelante

(4/8)

Clausura en la gramática LALR

• La clausura se calcula a partir de un estado con el juego de producciones I (usualmente S' → ·S, $):
  • Se agregan todas las producciones de I a la clausura de I
    • Si hay un A→α·Bβ, a (es decir, si sigue un no-terminal después elemento después del punto) se agrega B→·γ, b (es decir, las transiciones iniciales que comienzan con ese no-terminal, calculando el lookahead en ese momento)

(5/8)

Desplazamiento en la gramática LALR

• El desplazamiento (ir a) se calcula para todo estado I tal que contenga un A→α·Xβ, a
  • En ese caso, ir a(I, X) = A→αB·β, a (es decir, avanza el punto)
• Este desplazamiento indica a qué estado se debe ir a partir de I, cuando se avanza el punto a través de X

(6/8)

Corazón (core) en la gramática LALR

• El corazón de una producción LALR incluye solamente los elementos a la izquierda, ignorando el de lookahead (en forma A → B·CD)
• Se usa para determinar cuáles elementos tienen una forma común y agruparlos, para disminuir la cantidad de estados
• Si para un par de conjuntos de producciones A y B, a todos los elementos de A corresponden elementos de B que comparten el mismo corazón y viceversa, y además estas no causan conflicto entre sí, se pueden combinar
  • Por ejemplo, para para I = X → α·, a/; J = X → α·, a/b, la versión fusionada sería X → α·, a/b, y no hay conflictos
• Sin embargo, si cuando la combinación causa que las
  • Pero si I = X → α·, a y Y → β·, b; J = X → α·, b y Y → β·, a, la versión fusionada sería también X → α·, a/b y Y → β·, a/b, pero causaría un conflicto

(7/8)

Otros detalles gramáticos en LALR

• La tabla gramática LALR se maneja en forma idéntica a cualquier otra tabla LR, tanto para desplazamientos como para reducciones
• La generación de la colección canónica es idéntica a la de otros métodos LR, ya que el símbolo de lookahead no es utilizado
  • Para esos dos, véanse las anteriores filminas
• La validez de un elemento varía ligeramente: A→α·aβ, a es válida para un prefijo viable γ si hay una derivación S'⇒δAw⇒δαβw tal que γ = δα (es decir, S'⇒γβw) y se cumpla que a sea el primer símbolo de w, o sino, que w = ϵ y a = $

(8/8)

Generación simplificada de tabla gramática en la gramática LALR

• La generación de la tabla gramática es idéntica para la SLR, la LR(0) y la LALR, con varias excepciones:
  • Se genera la colección C, iniciando desde S' → ·S
• Se buscan qué elementos comparten corazones (cores) en la colección, y se reemplazan por su unión si no causan conflicto
• Para cada estado i:
  • Si hay un estado A→α·aβ, a, una transición para "ir a(I[i], a)" que vaya a un I[j], y a es terminal, entonces la acción para (i, a) es desplazar a j.
  • Si hay un estado A→α·, a, entonces la acción para a es reducir A→α (salvo si A es S')
    • Si hay un estado S' → S·, $ se acepta la hilera
• Para todos los no terminales A, si hay un "ir a(I[i], a) = I[j]" entonces "ir a[i, A] = j"
  • Si I[j] forma parte de un conjunto de producciones k que compartan el corazón, entonces "ir a[i, A] = k"
• Cualquier entrada vacía es un espacio de error