parsing - positive - LR(1) Artículo DFA-Lookaheads de computación

regex positive lookahead example

Question

Tengo problemas para entender cómo calcular los lookaheads para los elementos LR (1).

Digamos que tengo esta gramática:

S -> AB
A -> aAb | a
B -> d

Un elemento LR (1) es un elemento LR (0) con un lookahead. Entonces obtendremos el siguiente elemento LR (0) para el estado 0:

S -> .AB , {lookahead} 
A -> .aAb,  {lookahead} 
A -> .a,  {lookahead}

Estado: 1

A ->  a.Ab, {lookahead} 
A ->  a. ,{lookahead} 
A -> .aAb ,{lookahead} 
A ->.a ,{lookahead}

¿Alguien puede explicar cómo calcular los lookaheads? ¿Cuál es el enfoque general?

Gracias de antemano

Answer 1

El conjunto de elementos LR (1) construido por usted debe tener dos elementos más.

I8 A -> aA.b, b desde I2

I9 A -> aAb. , b de I8

Answer 2

aquí está el autómata LR (1) para la gramática, ya que el seguimiento se ha realizado anteriormente. Creo que es mejor para la comprensión intentar dibujar el autómata y el flujo hará que la idea de las miras más claras

Answer 3

Los lookaheads utilizados en un analizador LR (1) se calculan de la siguiente manera. Primero, el estado de inicio tiene un elemento de la forma

S -> .w  ($)

para cada producción S -> w, donde S es el símbolo de inicio. Aquí, el marcador $ denota el final de la entrada.

A continuación, para cualquier estado que contenga un elemento de la forma A -> x.By (t), donde x es una cadena arbitraria de terminales y no terminales, y B es un no terminal, se agrega un elemento de la forma B -> .w (s) para cada producción B -> wy para cada terminal en el conjunto FIRST (yt). (Aquí, PRIMERO se refiere a los PRIMEROS conjuntos , que generalmente se presentan al hablar sobre los analizadores de LL. Si no los ha visto antes, me tomaría unos minutos revisar esas notas de clase).

Probemos esto en tu gramática. Comenzamos creando un conjunto de elementos que contiene

S -> .AB ($)

Luego, usando nuestra segunda regla, para cada producción de A, agregamos un nuevo ítem correspondiente a esa producción y con lookaheads de cada terminal en FIRST (B $). Como B siempre produce la cadena d, FIRST (B $) = d, entonces todas las producciones que presentamos tendrán lookahead d. Esto da

S -> .AB ($)
A -> .aAb (d)
A -> .a (d)

Ahora, construyamos el estado correspondiente a ver una ''a'' en este estado inicial. Comenzamos moviendo el punto más de un paso para cada producción que comienza con un:

A -> a.Ab (d)
A -> a. (d)

Ahora, dado que el primer elemento tiene un punto antes de un no terminal, usamos nuestra regla para agregar un ítem por cada producción de A, lo que permite que esos ítems se vean primero FIRST (bd) = b. Esto da

A -> a.Ab (d)
A -> a. (d)
A -> .aAb (b)
A -> .a (b)

Continuando con este proceso, finalmente se construirán todos los estados LR (1) para este analizador LR (1). Esto se muestra aquí:

[0]
S -> .AB  ($)
A -> .aAb (d)
A -> .a   (d)

[1]
A -> a.Ab (d)
A -> a.   (d)
A -> .aAb (b)
A -> .a   (b)

[2]
A -> a.Ab (b)
A -> a.   (b)
A -> .aAb (b)
A -> .a   (b)

[3]
A -> aA.b (d)

[4]
A -> aAb. (d)

[5]
S -> A.B  ($)
B -> .d   ($)

[6]
B -> d.   ($)

[7]
S -> AB.  ($)

[8]
A -> aA.b (b)

[9]
A -> aAb. (b)

En caso de que ayude, impartí un curso de compiladores el verano pasado y tengo todas las diapositivas de conferencias disponibles en línea . Las diapositivas en el análisis de abajo arriba deben abarcar todos los detalles del análisis de LR y la construcción de la tabla de análisis sintáctico, y espero que los encuentren útiles.

¡Espero que esto ayude!

Answer 4

También recibo 11 estados, no 8:

State 0
        S: .A B ["$"]
        A: .a A b ["d"]
        A: .a ["d"]
    Transitions
        S -> 1
        A -> 2
        a -> 5
    Reductions
        none
State 1
        S_Prime: S .$ ["$"]
    Transitions
        none
    Reductions
        none
State 2
        S: A .B ["$"]
        B: .d ["$"]
    Transitions
        B -> 3
        d -> 4
    Reductions
        none
State 3
        S: A B .["$"]
    Transitions
        none
    Reductions
        $ => S: A B .
State 4
        B: d .["$"]
    Transitions
        none
    Reductions
        $ => B: d .
State 5
        A: a .A b ["d"]
        A: .a A b ["b"]
        A: .a ["b"]
        A: a .["d"]
    Transitions
        A -> 6
        a -> 8
    Reductions
        d => A: a .
State 6
        A: a A .b ["d"]
    Transitions
        b -> 7
    Reductions
        none
State 7
        A: a A b .["d"]
    Transitions
        none
    Reductions
        d => A: a A b .
State 8
        A: a .A b ["b"]
        A: .a A b ["b"]
        A: .a ["b"]
        A: a .["b"]
    Transitions
        A -> 9
        a -> 8
    Reductions
        b => A: a .
State 9
        A: a A .b ["b"]
    Transitions
        b -> 10
    Reductions
        none
State 10
        A: a A b .["b"]
    Transitions
        none
    Reductions
        b => A: a A b .