PUERTA | PUERTA CS 2008 | Pregunta 10

¿Cuál de los siguientes describe un identificador (según corresponda al análisis LR) de manera adecuada?
(A) Es la posición en forma de oración donde ocurrirá la siguiente operación de cambio o reducción

(B) Es una producción no terminal cuya producción se usará para la reducción en el siguiente paso
(C) Es una producción que se puede usar para la reducción en un paso futuro junto con una posición en la forma oracional donde el siguiente cambio o reducción ocurrirá la operación
(D) Es la producción p que se usará para la reducción en el siguiente paso junto con una posición en la forma oracional donde se puede encontrar el lado derecho de la producción

Respuesta: (D)
Explicación: Primero entendamos la terminología utilizada aquí.

Análisis LR : aquí ‘L’ significa proyección de izquierda a derecha de la string de entrada, y ‘R’ significa Derivación más a la derecha en reversa (porque se trata de un análisis de abajo hacia arriba).

Forma Oracional – Supongamos que para una Gramática Libre de Contexto dada G, tenemos un símbolo de inicio S, luego para definir el Lenguaje generado por la Gramática G, es decir, L(G), comenzamos la derivación comenzando desde S usando las reglas de producción de la gramática. Después de una derivación completa, obtenemos una string w que consta solo de símbolos terminales, es decir, w pertenece a L(G). Entonces podemos decir que w es una oración de la Gramática G. Ahora, durante el proceso de derivación, si obtiene alguna forma q, donde q puede contener algún No terminal, entonces decimos que q es una forma oracional de la Gramática G. Incluso el símbolo inicial S es también la forma oracional de la Gramática G (porque también contiene S no terminal).

For Ex :

Grammar is :

S-> aAcBe

A->Ab|b

B->d

Input string : abbcde

Derivation : ( Top-Down, Right Most Derivation)

S->aAcBe
->aAcde
->aAbcde
->abbcde 

Aquí { abbcde } es la oración de la Gramática (porque contiene solo símbolos terminales), y { S, aAcBe, aAcde, aAbcde } son las formas oracionales de G (porque estas formas contienen no terminales durante el proceso de derivación)

Ahora, veamos la pregunta.

La pregunta está relacionada con el análisis de LR, que es un análisis de abajo hacia arriba.

Tomemos la misma gramática anterior, ya que es un análisis de abajo hacia arriba, debemos comenzar desde la string «abbcde» e intentar obtener S usando las reglas de producción.

: abbcde

->aAbcde ( using A-> b )

->aAcde ( using A-> Ab )

->aAcBe ( using B -> d )

->S ( using S-> aAcBe ) 

El proceso anterior se llama reducción.

El RHS de la Producción que está siendo reemplazado por su LHS se llama Handle, Entonces, {b, Ab, d, aAcBe} son handles, y reemplazarlo con su LHS se llama Handle-Pruning.

Por lo tanto, la opción D se adapta mejor.

Cuestionario de esta pregunta