Cámara réflex(1)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 1 de diciembre de 2014; la verificación requiere 1 edición .

SLR(1) es un algoritmo de análisis de abajo hacia arriba.

Es una extensión del algoritmo LR(0) . En algunos casos, funciona cuando no es posible construir una tabla de análisis LR(0) para una gramática determinada debido a conflictos de cambio de conversión o conversión de conversión. Por lo tanto, la clase de gramáticas analizadas según SLR(1) (cr. "SLR(1)-gramáticas") es más amplia que la clase de gramáticas LR(0).

El algoritmo de análisis en sí mismo (ejecutar el analizador de acuerdo con el flujo de entrada) es el mismo para SLR(1) y LR(0) y, más ampliamente, para LALR(1) . Solo difieren los algoritmos para construir la tabla de análisis sintáctico por gramática en el proceso de generación del analizador.

Descripción

Para cada no terminal A en la gramática, se genera un conjunto de terminales First(A), definido como sigue:

si la gramática tiene una regla con una A en el lado izquierdo y un lado derecho que comienza con una terminal, entonces esa terminal está en Primera (A)
si la gramática tiene una regla con una A en el lado izquierdo y un lado derecho que comienza con un no terminal (denotado B), entonces First(B) está estrictamente incluido en First(A)
no se incluyen otros terminales en First(A)

Los mismos conjuntos se utilizan para construir el analizador LL(1).

Además, en función de los conjuntos First(A), se generan los conjuntos Follow(A), definidos de la siguiente manera

si la gramática tiene una regla en la que una A no aparece en la última posición y va seguida de una terminal, entonces la terminal se incluye en Seguir (A).
si la gramática tiene una regla en la que A no aparece en la última posición y le sigue un no terminal (denotado por B), entonces First(B) se incluye estrictamente en Follow(A)
si la gramática tiene una regla en la que A aparece en la última posición, entonces Seguir(C) se incluye estrictamente en Seguir(A), donde C es el lado izquierdo de la regla.
no se incluyen otros terminales en Follow(A)

(es posible generalizar estas condiciones para el caso de la presencia de reglas B -> nulo)

A continuación, se genera la tabla de análisis, como para LR(0), con una diferencia cuando se ingresan las acciones de conversión. La conversión para el estado S y el símbolo de entrada C se tabula solo si hay una cadena en S que coincide con todo el lado derecho de la regla, y el no terminal N del lado izquierdo de la regla satisface la condición "C está en Seguimiento ( NORTE)".

Esto da como resultado menos intentos de SLR(1) de colocar una "conversión" en la celda de la tabla de análisis, lo que reduce el riesgo de conflictos con las conversiones, a veces eliminándolas por completo, y crea una gramática que LR(0) no analiza. ) analizable.

Aplicación práctica

Casi no tiene (a excepción de la educativa) debido a la estrecha clase de gramáticas que se analizan. Una aplicación práctica es LALR(1), que es una generalización de SLR(1).

Las expresiones aritméticas con operadores binarios y unarios y paréntesis se analizan utilizando SLR(1)

Véase también