Boletín de ejercicios II: análisis sintáctico

EJERCICIO 1

Dada la siguiente gramática:

G=<ET, EN, S, P>
ET={0,1}
EN={S,A,B}
S=S
P={S -> 11
S -> 1B
S -> 0A
A -> 0S
A -> 1
B -> 1S0
B -> 1
}

De las siguientes palabras, ¿cuál (es) pertenecen al lenguaje generado por la gramática?: 00, 10, 11, 100, 1100, 11000

EJERCICIO 2

Dada la siguiente gramática:

G=<ET, EN, S, P>
ET={0,1}
EN={S,A,B}
S=S
P={S -> 0A
S -> 1B
A -> 0S1
A -> 0
B -> 1S0
B -> 1
}

De las siguientes palabras, ¿cuál (es) pertenecen al lenguaje generado por la gramática?: 00, 10, 11, 100, 1100, 11000

EJERCICIO 3

Escriba una gramática que defina el lenguaje de todas las cadenas no vacías del alfabeto {a, b, c, d} que no contengan a la subcadena abc.

EJERCICIO 4

Demuestre que la gramática con las siguientes producciones es ambigua. Halle una gramática equivalente que no sea ambigua.

G=<ET, EN, S, P>
ET={0,1}
EN={S,B}
S=S
P={S -> 11
S -> 1B
B -> 1S0
B -> 1
}

EJERCICIO 5

El lenguaje de programación C tienen un gran número de operadores, defina una gramática no ambigua para las expresiones de C tomando en cuenta el siguiente sub-conjunto de operadores.

Operador Descripción Asociatividad
* / Multiplicación, División Izquierda
+ - Suma, Resta Izquierda
< <= > >= = Relacional Izquierda

EJERCICIO 6

Defina, por medio de una gramática independiente del contexto un lenguaje de expresiones aritméticas que tenga las siguientes características:

El alfabeto de tokens a utilizar para definir el lenguaje es el siguiente: {NUM, +, x, (, ) }. El token NUM representa una constante númerica positiva o 0 (una cadena de dígitos). Se desea que las expresiones entre paréntesis sólamente puedan aparecer precedidas del operador de multiplicación (x).

 

 

Ejemplos de cadenas del lenguaje pedido son las siguientes:

Ejemplos de cadenas que no pertenecen al lenguaje pedido son las siguientes:

EJERCICIO 7

Para cada una de las gramáticas indicadas a continuación escriba una expresión regular que defina el mismo lenguaje que la gramática dada.

  1. G=<ET,EN,S,P>
ET={a, b}
EN={S, A, B}
S= S
P={
S -> A S, S -> A,
A -> a A, A -> b B,
B -> a B, B -> a
}

  2. G=<ET,EN,S,P>
ET={a, b, c}
EN={S, A, B, C}
S= S
P={
S -> A S, S -> b,
A -> a B, A -> b C,
B -> b B, B -> c,
C -> b C, C -> a
}

EJERCICIO 8

A continuación se presentan 7 definiciones de lenguajes (6 gramáticas y una expresión regular):

  1. Definición 1 (gramática):

    G=<ET,EN,S,P>
ET={a, b}
EN={S}
S=S
P={S -> a S a, S -> b}

  2. Definición 2 (gramática):

    G=<ET,EN,S,P>
ET={a, b}
EN={S, A, B}
S=S
P={S -> b, S -> a B, B -> ba, B -> A a, A -> a B}

  3. Definición 3 (gramática):

    G=<ET,EN,S,P>
ET={a, b}
EN={S}
S=S
P={S -> a S a, S -> b, S -> a S, S -> S a}

  4. Definición 4 (gramática):

    G=<ET,EN,S,P>
ET={a, b}
EN={S, A}
S=S
P={S -> a A, A -> ba, A -> S a}

  5. Definición 5 (gramática):

    G=<ET,EN,S,P>
ET={a, b}
EN={S, A}
S=S
P={S -> a A, A -> a A a, A -> ba}

  6. Definición 6 (gramática):

    G=<ET,EN,S,P>
ET={a, b}
EN={S}
S=S
P={S-> a S a, S -> aba}

  7. Definición 7 (expresión regular):

    a* b a*

Sin embargo, estas definiciones no definen 7 lenguajes distintos.

Indique cuantos lenguajes distintos son definidos y, para cada lenguaje, indique cual o cuáles de las definiciones dadas lo identifican.

EJERCICIO 9

Considere las siguientes gramáticas:

Gramática G1:

G1=<ET, EN, S, P}
ET= {=, *, i}
EN= {S, L, R}
S= S
P= {S -> L = R, S -> R,
L -> * R, L -> i,
R -> L}

Gramática G2:

G2=<ET, EN, S, P}
ET= {i, +, *}
EN= {E}
S= E
P= {E -> E + E, E -> E * E,
E -> i}

Gramática G3:

G3=<ET, EN, S, P}
ET= {a, b, c}
EN= {S, A}
S= S
P= {S -> a S b, S -> A,
A -> c A, A -> c}

Gramática G4:

G4=<ET, EN, S, P}
ET= {a, b, c}
EN= {S, A, B, C}
S= S
P= {S -> A a, S -> B b, S -> S a S,
    S -> a C, S -> a b, A -> c A,
    A -> c, B -> c c, C -> a C,
    C -> b}

Para cada una de estas gramáticas conteste a las siguientes preguntas:

  1. Obtenga el autómata LR(0) correspondiente a la gramática.

  2. Para cada no terminal de la gramática calcule la función SIGUIENTE.

  3. A la vista de los resultados obtenidos en los 2 apartados anteriores, indique si el analizador SLR para la gramática tiene algún conflicto. Si la respuesta es afirmativa, indique en que estados del autómata hay conflictos y de que tipo.

  4. Indique que podemos concluir acerca de si la gramática es o no ambigua. Razone la respuesta.

  5. Analice con el analizador SLR la cadena que se indica a continuación, mostrando la secuencia de pasos (desplazamiento, reducción, aceptar y error) que realizaría el analizador. En cada paso muestre el contenido de la pila de estados y la parte de la cadena pendiente de consumir.

    • Cadena para G1: **i=i

    • Cadena para G2: i*i+i

    • Cadena para G3: aaccb

    • Cadena para G4: ccaaabaa

    Nota: en el caso de que la gramática presente algún conflicto, utilizaremos los siguientes criterios para resolver los conflictos y poder realizar el análisis. En el caso de los conflictos desplazamiento-reducción optaremos por desplazar. En el caso de los conflictos reducción-reducción optaremos por reducir utilizando la regla de producción que esté definida primero en la gramática.

EJERCICIO 10

Considere la regla de producción A ->A B C que forma parte de la gramática G, donde A, B y C son símbolos no terminales. Se sabe que se asocia a los no terminales A y C un mismo interfaz, llamado AC y al no terminal B se le asocia el interfaz B.

Escriba la clase Java que correspondería a esta regla de producción como parte de las clases Java que habría que definir para representar árboles de sintaxis abstracta para G.

EJERCICIO 11

Para cada una de las siguientes expresiones regulares, escriba una gramática que defina el mismo lenguaje: