parsing - son - Explicación sobre el prefijo viable

prefijos y sufijos para niños de cuarto grado (3)

En el libro de compiladores de Ullman, a la par de reducir el análisis, se proporciona la siguiente definición de prefijo viable:

"El conjunto de prefijos de formas sentenciales correctas que pueden aparecer en la pila de un analizador de reducción de desplazamiento se denominan prefijos viables. Una definición equivalente de prefijo viable es que es un prefijo de forma sentencial derecha que no continúa más allá de la derecha al final del extremo derecho de esa forma de la frase. Por esta definición, siempre es posible agregar símbolos de terminal al final de un prefijo viable para obtener una forma de la derecha. Por lo tanto, aparentemente no hay error mientras la parte de la la entrada vista a un punto dado se puede reducir a un prefijo viable ".

No puedo entender esta definición. ¿Podría alguien explicar el significado de prefijo viable con un ejemplo?
En particular, por favor explique el significado de
"Una definición equivalente de un prefijo viable es que es un prefijo de forma sentencial derecha que no continúa más allá del extremo derecho del identificador más a la derecha de esa forma sentencial"

Considere la gramática dada en el libro (lo estoy replanteando aquí)

E -> E+T | T T -> T*F | F F -> (E) | id

que se aumenta agregando E ''-> E en ella

Ahora echa un vistazo a esta derivación,

E'' -> E -> E+T -> E+T*F

Reclamar E + T * es un prefijo viable

Argumento: esta derivación es una forma sentencial derecha y E + T * es un prefijo de la misma. La manija actualmente es T * F (al reducir T * F a T podemos alcanzar el símbolo de inicio y por lo tanto un análisis exitoso)

Y por lo tanto, E + T * es un prefijo viable ya que es un prefijo de forma sentencial derecha y no se extiende más allá del identificador más a la derecha para esta forma sentencial. :)

Otra forma de definirlo es:

The prefixes of right sentential forms that can appear on the stack of a shiftreduce parser are called viable prefixes.

Me pareció útil proporcionar una definición formal de prefijos viables, por si acaso, si alguien lo encuentra más comprensible (como yo).

Dada una gramática , Nosotros decimos eso es un prefijo viable de Si existe una derivación más a la derecha.
tal que .

Fuente

EDITAR (o en realidad reescribir): ¡ La oración que pidió una aclaración es una bola de pelo importante! Necesitaba un poco de actualización sobre el lenguaje y los autómatas para separar esa bola de pelo. Encontré estas notas de la conferencia muy útiles en ese sentido.

Tampoco hace que sea más fácil que los términos se definan en términos de expansión de arriba hacia abajo, mientras que la derivación más a la derecha se usa típicamente con el análisis de abajo hacia arriba.

Usaré la siguiente gramática de expresión para ilustrar:

expr -> expr + term | term term -> term * factor | factor factor -> NUMBER | ( expr )

Una forma de la derecha es una forma de la que se puede llegar por medio de la derivación de la derecha, que es otra forma de describir la expansión repetida de solo el símbolo del no extremo del extremo derecho cuando se procede de arriba hacia abajo. Esta es una derivación más a la derecha, y todas las formas en ella son, por lo tanto, formas de sentencias correctas:

expr -> expr + term -> expr + term * factor -> expr + term * NUMBER -> expr + factor * NUMBER -> expr + NUMBER * NUMBER -> expr + term + NUMBER * NUMBER -> expr + NUMBER + NUMBER * NUMBER -> term + NUMBER + NUMBER * NUMBER -> NUMBER + NUMBER + NUMBER * NUMBER

Un prefijo de forma sentencial (ya sea correcto o no) es una secuencia de símbolos de entrada que reduce a cero o más símbolos iniciales de esa forma sentencial. La secuencia vacía es trivialmente un prefijo de cada forma sentencial, y la secuencia completa de símbolos que conforman una forma sentencial también es trivialmente un prefijo de la misma.
Una frase simple es la expansión de un solo símbolo no terminal que ocupa un lugar en forma sentencial. Por ejemplo, el term * factor es una frase simple porque es una expansión del term , y el term sí aparece en tres producciones.
El identificador de una forma sentencial es la frase más a la izquierda dentro de esa forma. (Admito que encuentro el término ''manejador'' un tanto confuso aquí). En la derivación más a la derecha, el identificador es fácil de identificar: es la secuencia de símbolos que resultó del no terminal ampliado más recientemente. Si está trabajando de abajo hacia arriba de la manera en que lo hace un analizador de reducción por desplazamiento, el identificador es la frase simple que debe reducirse a continuación . (Lea la tabla de derivación de arriba hacia abajo, mirando a qué símbolos se redujeron, para ver a qué me refiero).
Un prefijo viable de una forma de derecha es un prefijo que no se extiende más allá del identificador de esa forma; en otras palabras, ese prefijo es válido y no contiene frases simples reducibles, con la posible excepción del propio identificador si dicho prefijo se extiende a exactamente el extremo del mango.

Desde el punto de vista del analizador shift-reduce, siempre que tenga un prefijo viable en la pila, aún no ha sido forzado a reducir la frase simple (posiblemente incompleta) en la parte superior de la pila a un nuevo no terminal o fallar de analizar si no se puede reducir. Si cambiar el siguiente símbolo resultaría en algo más que un prefijo viable, en ese punto debe reducir o fallar.

Si está analizando un lenguaje libre de contexto, hay una propiedad bastante conveniente que ayuda con la construcción de un analizador de reducción de desplazamiento basado en tablas: el conjunto de todos los prefijos viables de un lenguaje libre de contexto es un lenguaje regular. Por lo tanto, puede construir un autómata finito que reconozca el lenguaje regular de los prefijos viables y utilizarlo para determinar cuándo cambiar y cuándo reducir. Esta combinación de una pila y una máquina de estados finitos es esencialmente un autómata de empuje, que es exactamente la clase de autómata necesaria para reconocer un lenguaje libre de contexto.