Gramáticas ambiguas con Bison

Sesión 07: Gramáticas ambiguas con Bison

I. OBJETIVOS

- Utilizar bison para crear gramáticas ambiguas

- Mostrar las soluciones para la ambiguedad

II. TEMAS A TRATAR

● Gramáticas ambiguas

● Soluciones para la ambiguedad

III. MARCO TEORICO

Gramáticas ambiguas

Una gramática ambigua es una gramática libre de contexto, la cual presente más de una derivación por la izquierda, al contrario de una gramática no ambigua que también es una gramática libre de contexto para el que cada cadena válida tiene una única derivación a la izquierda.

Los lenguajes de programación en su mayoría admiten ambas gramática ambiguas y no ambiguas, los idiomas admiten solamente gramáticas ambiguas. Un idioma que no este vacío admite una gramática ambigua mediante la adopción de una gramática no ambigua y la introducción de una regla duplicado o sinónimo (el único idioma sin gramáticas ambiguas es el lenguaje vacío).

El lenguaje que sólo admite gramáticas ambiguas se llama un lenguaje inherentemente ambiguo, y no son inherentemente ambiguos lenguajes libres de contexto.

Para la computadora, lenguajes de programación, la gramática de referencia es a menudo ambigua, si esta presente, estas ambigüedades son generalmente resueltas mediante la adición de reglas de prioridad u otras reglas de análisis sensibles al contexto, por lo que la gramática general en la frase es inequívoca. El conjunto de todos los árboles de análisis sintáctico de una oración ambigua se llama un bosque análisis

El lenguaje trivial

El ejemplo más simple es la siguiente gramática ambigua para el lenguaje trivial, que consta sólo de la cadena vacía:

A → A | ε

Lo que significa que una producción puede ser en si de nuevo o la cadena vacía. La cadena vacía hace derivaciones más a la izquierda de longitud 1,2,3 y de hecho de cualquier longitud, dependiendo del número de veces que se utiliza la regla A → A

Este lenguaje también tiene la gramática no ambigua, consiste en una única regla de producción:

Un → ε

Esto significa que la producción única solo puede producir la cadena vacia, que es la cadena única en el lenguaje.

De la misma forma que cualquier gramática de un lenguaje no vacío puede hacerse ambigua mediante la adición de duplicados

Cadena unitaria

El lenguaje regular de cadenas unitarias de un personaje determinado, por ejemplo “a” (la expresión regular a*) tiene la gramática ambigua:

A → aA | ε

Y también tiene la gramática ambigua:

A → aA | aa | ε

Estos corresponde a la producción de un asociativo por la derecha del árbol (para la gramática no amgiua(, otra opción es la asociación a la derecha y la izquierda

Adicción y sustracción

A → A + A | A - A | A * A |a

Es ambigua ya que hay dos derivaciones por la izquierda de la cadena a + a + a:

El problema del else colgante

Un ejemplo común de ambigüedad en los lenguajes de programación es el else colgante. En muchos idiomas la “else” de un if – then, el “else” es una declaración opcional, esto genera condiciones anidadas esto tiene múltiplles formas de ser reconocido en términos de la gramática independiente de contexto.

En muchos idiomas se puede escribir condicionales en dos formas válidas, la forma “si - entonces” y la forma “si – entonces – else ”, haciendo la clausula else opcional

Por ejemplo una gramática que puede contener las reglas:

Statement → if Condition then Statement |

if Condition then Statement else Statement |

...

Condition → ...

Algunas estructuras de frases ambiguas pueden aparecer, como por ejemplo la expresión:

if a then if b then s else s2

Se puede analizar como :

if a then begin if b then s end else s2

O como:

if a then begin if b then s else s2 end

Dependiendo de si la “else” esta asociada con la primera if o con la segunda if

La resolución se da de diferentes maneras en distintos idiomas, a veces la gramática se modifica de manera que no sea ambigua, como por ejemplo, al elegir una declaración “endif” o hacer “else” obligatoria. En otros casos la gramática se deja ambigua, pero la ambigüedad es resuelta haciendo que la gramática genere una frase contextual, asociando una “else” con la más cercana “if”. En este último caso, la gramática es ambigua

Una gramática no ambigua con mútiples derivaciones

La existenciade múltiples derivaciones de la misma cadena no es suficiente para indicar que la gramática es ambigua, sólo varios más a la izquierda derivaciones (o equivalentemente, varios árboles de análisis sintáctico) indican ambigüedad:

Por ejemplo: la simple gramática

S → A + A

A → 0 | 1

Es una gramática no ambigua para el idioma {0+0, 0+1, 1+0, 1+1}. Si bien cada una de estas cuatro cadenas tiene sólo una derivación por la izquierda que tiene dos derivaciones diferentes, por ejemplo:

S ⇒ A + A ⇒ 0 + A ⇒ 0 + 0

Y

S ⇒ A + A ⇒ A + 0 ⇒ 0 + 0

Solo la primera

...