¿Qué son los casos en los que no podemos realizar el análisis de LR sin gramática aumentada?

Question

Muchos textos de diseño de compiladores estándar mencionan la construcción de la gramática aumentada como primer paso del análisis de LR.

La razón con frecuencia es

1. Se requiere en los casos en que el símbolo de inicio viene a la mano derecha de cualquier producción
2. Se requiere cuando los RHS del símbolo de inicio tienen múltiples producción.

Pensé que si en la parte de la tabla de parse es parte del primer estado de DFA, proporcionamos "éxito" bajo la entrada de '$' No requeriríamos la gramática aumentada.¿Es eso correcto o me falta algo?

Editar: Aquí es cómo creo que podemos declarar un análisis como éxito:

Considera S -> .A Después de reducir 'A' en lugar de ir a ir a ir a nuestro estado actual Un TTOP de pila, podemos simplemente mirar '$' y éxito de la producción

Answer 1

Una vez que tenemos una tabla de análisis, podemos analizar (o rechazar) cualquier oración sin ninguna referencia a la gramática. Entonces, en ese momento, el hecho de que la gramática era o no fue aumentada es esencialmente discutible. (Sería significativo si hubiera una acción semántica de usuario adjunta a la exclusiva producción de símbolos de inicio aumentada, pero eso parece imposible, ya que la producción aumentada del símbolo de inicio aumentó automáticamente, no por el usuario).

Y es, de hecho, el caso de que la mayoría de los generadores de analizadores hacen, de hecho, optimizan su tabla de análisis haciendo que la Shift del marcador final de la entrada sea la acción aceptable, en lugar de esperar el inicio aumentado La producción de símbolos se reducirá. Con esa optimización, el símbolo de inicio aumentado nunca se usa en una acción del analizador, por lo que el símbolo en sí no necesita existir. Si el generador del analizador aumentó la gramática, ese aumento se ha deshecho esencialmente, excepto por un pequeño misterio: ¿qué es este símbolo de final de entrada que se puede cambiar? No aparece en ningún lado derecho reducible.

De todos modos, el punto es que no está analizando lo que requiere una gramática aumentada; La gramática aumentada es necesaria para crear la tabla de análisis. Los casos en los que es necesario son esencialmente los casos en los que existe alguna acción de reducción no predeterminada asociada con un símbolo de entrada de fin de entrada. Esa acción de reducción solo podría haber sido agregada correctamente a la tabla de análisis a través del análisis de un estado que incluye la producción de símbolos de inicio aumentada.

(estrictamente hablando, tal como se indica anteriormente, el símbolo del final de la entrada realmente no puede existir en la tabla de análisis a menos que esté presente en algún lado derecho en la gramática, y no está presente hasta La gramática se aumenta; El aumento no solo agrega un no terminal adicional, sino que también agrega el símbolo del extremo de entrada.)