Autómatas y análisis pushdown

El análisis se usa para derivar una cadena usando las reglas de producción de una gramática. Se utiliza para comprobar la aceptabilidad de una cadena. El compilador se utiliza para comprobar si una cadena es sintácticamente correcta o no. Un analizador toma las entradas y crea un árbol de análisis.

Un analizador puede ser de dos tipos:

  • Top-Down Parser - El análisis de arriba hacia abajo comienza desde arriba con el símbolo de inicio y deriva una cadena usando un árbol de análisis.

  • Bottom-Up Parser - El análisis de abajo hacia arriba comienza desde abajo con la cadena y llega al símbolo de inicio usando un árbol de análisis.

Diseño de analizador de arriba hacia abajo

Para el análisis de arriba hacia abajo, una PDA tiene los siguientes cuatro tipos de transiciones:

  • Haga estallar el no terminal en el lado izquierdo de la producción en la parte superior de la pila y empuje su cuerda del lado derecho.

  • Si el símbolo superior de la pila coincide con el símbolo de entrada que se está leyendo, páselo.

  • Empuje el símbolo de inicio 'S' en la pila.

  • Si la cadena de entrada se lee por completo y la pila está vacía, vaya al estado final 'F'.

Ejemplo

Diseñe un analizador de arriba hacia abajo para la expresión "x + y * z" para la gramática G con las siguientes reglas de producción:

P: S → S + X | X, X → X * Y | Y, Y → (S) | carné de identidad

Solution

Si el PDA es (Q, ∑, S, δ, q 0 , I, F), entonces el análisis sintáctico descendente es -

(x + y * z, I) ⊢ (x + y * z, SI) ⊢ (x + y * z, S + XI) ⊢ (x + y * z, X + XI)

⊢ (x + y * z, Y + XI) ⊢ (x + y * z, x + XI) ⊢ (+ y * z, + XI) ⊢ (y * z, XI)

⊢ (y * z, X * YI) ⊢ (y * z, y * YI) ⊢ (* z, * YI) ⊢ (z, YI) ⊢ (z, zI) ⊢ (ε, I)

Diseño de un analizador ascendente

Para el análisis de abajo hacia arriba, una PDA tiene los siguientes cuatro tipos de transiciones:

  • Empuje el símbolo de entrada actual en la pila.

  • Reemplace el lado derecho de una producción en la parte superior de la pila con su lado izquierdo.

  • Si la parte superior del elemento de la pila coincide con el símbolo de entrada actual, sáquelo.

  • Si la cadena de entrada se lee por completo y solo si el símbolo de inicio 'S' permanece en la pila, páselo y vaya al estado final 'F'.

Ejemplo

Diseñe un analizador de arriba hacia abajo para la expresión "x + y * z" para la gramática G con las siguientes reglas de producción:

P: S → S + X | X, X → X * Y | Y, Y → (S) | carné de identidad

Solution

Si el PDA es (Q, ∑, S, δ, q 0 , I, F), entonces el análisis sintáctico ascendente es -

(x + y * z, I) ⊢ (+ y * z, xI) ⊢ (+ y * z, YI) ⊢ (+ y * z, XI) ⊢ (+ y * z, SI)

⊢ (y * z, + SI) ⊢ (* z, y + SI) ⊢ (* z, Y + SI) ⊢ (* z, X + SI) ⊢ (z, * X + SI)

⊢ (ε, z * X + SI) ⊢ (ε, Y * X + SI) ⊢ (ε, X + SI) ⊢ (ε, SI)