El analizador LR se puede utilizar para analizar gramáticas ambiguas. El analizador LR resuelve los conflictos (cambiar/reducir o reducir/reducir) en la tabla de análisis de gramáticas ambiguas en función de ciertas reglas (precedencia y/o asociatividad de operadores) de la gramática.
Ejemplo:
Tomemos la siguiente gramática ambigua:
E -> E+E E -> E*E E -> id
Supongamos que la precedencia y la asociatividad de los operadores (+ y *) de la gramática son las siguientes:
- «+» y «*» ambos son asociativos a la izquierda,
- La precedencia de «*» es mayor que la precedencia de «+».
Si usamos el analizador LALR(1), el DFA del elemento LR(1) será:
Desde el elemento DFA de LR(1) podemos ver que hay conflictos de cambio/reducción en el estado I 5 e I 6 . Así que la tabla de análisis es la siguiente:
Hay movimientos tanto de desplazamiento como de reducción en I 5 e I 6 en “+ y “*”. Para resolver este conflicto, es decir, determinar qué movimiento mantener y cuál descartar de la tabla, utilizaremos la precedencia y la asociatividad de los operadores.
Considere la string de entrada:
id + id + id
Veamos los movimientos del analizador hasta el estado de conflicto de acuerdo con la tabla de análisis anterior.
- Si tomamos el movimiento de reducción del estado I 5 en el símbolo «+» como en el analizador 1, entonces el «+» izquierdo de la string de entrada se reduce antes que el «+» derecho, lo que hace que «+» sea asociativo a la izquierda.
- Si tomamos el movimiento de desplazamiento del estado I 5 en el símbolo «+» como en el analizador 2, entonces el «+» derecho de la string de entrada se reduce antes que el «+» izquierdo, lo que hace que «+» sea asociativo a la derecha.
De manera similar, tomar un movimiento de turno del estado I 5 en el símbolo «*» le dará a «*» una mayor prioridad sobre «+», ya que «*» se reducirá antes que «+». Tomar el movimiento de reducción del estado I 5 en el símbolo «*» le dará a «+» una mayor prioridad sobre «*», ya que «+» se reducirá antes que «*». Similar a I 5 , los conflictos de I 6 también se pueden resolver.
De acuerdo con la precedencia y asociatividad de nuestro ejemplo, el conflicto se resuelve de la siguiente manera,
- El conflicto de cambio/reducción en I 5 en “+” se resuelve manteniendo el movimiento de reducción y descartando el movimiento de cambio, lo que hace que “+” sea asociativo a la izquierda.
- El conflicto de cambio/reducción en I 5 en “*” se resuelve manteniendo el movimiento de cambio y descartando el movimiento de reducción, lo que le dará a “*” mayor precedencia sobre “+”.
- El conflicto de cambio/reducción en I 6 en “+” se resuelve manteniendo el movimiento de reducción y descartando el movimiento de cambio, lo que le dará a “*” mayor precedencia sobre “+”.
- El conflicto de cambio/reducción en I 6 en “*” se resuelve manteniendo el movimiento de reducción y descartando el movimiento de cambio, lo que hace que “*” sea asociativo a la izquierda.
En general, la herramienta generadora de analizadores YAAC resuelve los conflictos debido a gramáticas ambiguas de la siguiente manera:
- El conflicto de desplazamiento/reducción en la tabla de análisis se resuelve dando prioridad al movimiento de desplazamiento sobre el movimiento de reducción. Si la string se acepta para el movimiento de cambio, se elimina el movimiento de reducción; de lo contrario, se elimina el movimiento de cambio.
- El conflicto de reducción/reducción en la tabla de análisis se resuelve dando prioridad al primer movimiento de reducción sobre el segundo movimiento de reducción. Si la string se acepta para el primer movimiento de reducción, se elimina el segundo movimiento de reducción; de lo contrario, se elimina el primer movimiento de reducción.
Preguntas GATE relacionadas:
Publicación traducida automáticamente
Artículo escrito por SreejitBose y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA