Prefijo viable en análisis ascendente

Prefijo viable es un prefijo de una forma oracional derecha que no continúa más allá del extremo derecho del identificador más a la derecha de esa forma oracional.

Esto significa claramente que un prefijo viable tiene un identificador en su extremo derecho. No todos los prefijos de forma oracional derecha pueden aparecer en la pila de un analizador shift reduce .

Esto se puede mostrar con la ayuda del siguiente ejemplo.

Ejemplo –

A=>B+id=>(E)+id  
(rightmost derivation, sentential form) 

El analizador de abajo hacia arriba proporciona una derivación inversa a la derecha, por lo que en el ejemplo anterior, si obtenemos la string (E) + id durante la derivación inversa a la derecha, se realizan las siguientes operaciones:

Operación realizada	Pila	Comentarios
(.E)+id	(	cambio (
(E.)+id	( mi	cambio mi
(E).+id	( mi )	cambio )
B.+id	B	reducir (E) a B
B+.id	B +	cambio +
B+id.	B + identificación	identificación de turno
A	A	reducir B + id a A

Como podemos ver en la tabla anterior, antes de cambiar + a la pila, hemos reducido (E) a B. Entonces, solo podemos tener (, (E, (E)) en la pila, pero no podemos tener (E)+ en la pila porque ( E) es un identificador y los elementos en la pila no pueden exceder más allá del identificador. Así que aquí (, (E, (E)) son todos los prefijos viables para el identificador (E) y solo estos prefijos están presentes en la pila de shift reduce parser.

Así que seguimos cambiando los elementos hasta que llegamos al mango o se produce un error. Una vez alcanzado un mango lo reducimos con un no terminal utilizando la producción adecuada. Por lo tanto, los prefijos viables ayudan a tomar decisiones apropiadas de reducción de desplazamiento. Mientras la pila contenga estos prefijos, no puede haber ningún error.

Todos los prefijos viables pueden ser reconocidos por el autómata LR(0). Por lo tanto, el conjunto de prefijos viables para un analizador SLR(1) dado es un lenguaje normal. Esta combinación de pila con máquina de estados finitos es, de hecho, un autómata push-down que en realidad se usa para reconocer un lenguaje libre de contexto.

El siguiente ejemplo ilustra todos los prefijos viables para la gramática dada.

Ejemplo –
Gramática dada:

S -> AA
A -> bA | a 

String dada –

bbbaa 

Solución:
como sabemos, el análisis de abajo hacia arriba es el reverso de la derivación más a la derecha de una string para una gramática dada. Por lo tanto, usamos la derivación inversa a la derecha de la string para demostrar este ejemplo.

S. No.	Derivación inversa más a la derecha con manijas	Prefijo viable	Comentarios
1.	S -> bbb a a	b, bb, bb, bbba	Aquí, a es el identificador, por lo que el prefijo viable no puede exceder más allá de a.
2.	S -> bb bA a	b, bb, bbb, bbbA	Aquí, bA es el identificador, por lo que el prefijo viable no puede exceder más allá de bA.
3.	S -> b bA a	b, bb, bbA	Aquí también, bA es el identificador, por lo que el prefijo viable no puede exceder más allá de bA.
4.	S -> bA a	b, bA	Aquí también, bA es el identificador, por lo que el prefijo viable no puede exceder más allá de bA.
5.	S -> A a	una, una	Aquí, a es el identificador, por lo que el prefijo viable no puede exceder más allá de a.
6.	S -> AA	A, AA	Aquí, AA es el identificador, por lo que el prefijo viable no puede exceder más allá de AA.