SINTAXIS

Definición de Gramáticas: Una gramática  libre de contexto G = (T,N,S,R) consiste en:

• un conjunto de terminales T
• un conjunto de no terminales N
• un símbolo de inicio S
• un conjunto de producciones R o reglas de derivación, cada una de la forma:

X ->Y1Y2 : : : Yn

Donde X € N e Yi € T U N U {€}

ejemplo:

La gramática G=(N,T,I,P) donde,

N={I,A,B}

T={x,(,),+,-,*,/}

 P={

I->I+I

I->I-I

I->A

A->A*A

A->A/A

A-> (I)

A->x

Ejemplo Propuesto

La gramática G=(A,B,C,D) donde,

A={C,F,G}

B={y,(,),+,-,*,/}

 D={

C->C+C

C->C-C
C->G

G->G*G

G->G/G

G-> (A)

G->y

Derivaciones: Tratando las reglas de producción como una regla de reescritura, en la que el no terminal del lado izquierdo es  reemplazado por la cadena del lado derecho de la  producción, se obtiene una derivación.

Derivación por la izquierda: Derivación donde solo el no terminal de más a la izquierda de cualquier forma de frase se sustituye en cada paso.

Derivación por la derecha o Derivación canónica: Derivación donde el no terminal más a la derecha se sustituye en cada paso.

Por ejemplo, una gramática para operaciones matemáticas simples puede ser (1) (que también se puede escribir con el operador |1 como en (2)):

S -> E

E -> E + E

E -> E * E         (1)

E -> (E)

E -> id

S -> E

E -> E + E

| E * E              (2)

| (E)

| id

Las expresiones gramaticales derivan en  arboles sintácticos, por ejemplo para la expresión:

id * id + id

La derivación se hace remplazando los no terminales por la regla de producción hasta “calzar" la expresión,  según el ejemplo:

S -> E -> E + E -> E * E + E -> id * E + E -> id * id + E -> id * id + id

Ejemplo Propuesto:

a/b-c

P -> F -> F - F -> F / F - F -> a / F - F -> a / b - F -> a / b - c

Esta es una derivación por la izquierda porque a cada paso remplazamos el no terminal de mas a la izquierda. 

Arboles de análisis sintáctico: Representación gráfica de una derivación, la manera en que el símbolo inicial de una gramática deriva a una cadena en el lenguaje. Tiene las siguientes propiedades:

1. La raíz se etiqueta con el símbolo inicial.
2. Cada hoja se etiqueta con un terminal, o con Є.
3. Cada nodo interior se etiqueta con un no terminal.
4. Si A es el no terminal que etiqueta a cierto nodo interior, y X1, X2,…,Xn son las etiquetas de los hijos de ese nodo de izquierda a derecha.

ejemplo:

De la derivación anterior se forma el siguiente árbol sintáctico:























Ejemplo Propuesto:

Ambigüedad:     Diremos que una gramática G es ambigua si el lenguaje definido por ella tiene alguna sentencia para la cual existe más de un árbol sintáctico. Hay que tener claro que la que es ambigua es la gramática, no el lenguaje y que con una gramática ambigua no será posible implementar un analizador. Asimismo, siempre es posible modificar las reglas de la gramática para solucionar la ambigüedad y manteniendo el mismo lenguaje.

Ejemplo.

G = { {s}, {a,+,*}, P, S }

P: S -> a

S -> S+S

S -> S*S

Si dibujamos el árbol de derivación para "a*a+a", nos puede salir de dos formas distintas:

Aquí se ve claramente que la gramática es ambigua, pues podemos aplicar indistintamente la segunda o la tercera regla.

Existen algunas soluciones para este tipo de ambigüedad sin reescribir la gramática y como un “mecanismo externo”:

a) Dar mayor prioridad al producto que a la suma.

b) En caso de igualdad en la prioridad obligar al uso de paréntesis.

-Ejemplo Propuesto.

G = { {a}, {b,/,-}, H, A }

H:         A -> b

             A -> A/A

             A -> A-A

Asociatividad de operadores: indica el orden de ejecución cuando en una expresión existen diversos operadores de igual precedencia. Puede ser de dos tipos: izquierda (→) o derecha (←) .

Por ejemplo, la suma binaria + tiene asociatividad izquierda, lo que significa que en una expresión como:

a + b + c + d;

la ejecución seguirá el orden:

(((a + b) + c) + d);

Los operadores unarios y el de asignación (=), tienen asociatividad derecha (←). Todos los demás la tienen izquierda (→). En consecuencia, si @ representa un operador binario, ante una expresión como:

a @ b @ c @ d;

el orden de evaluación es desde la izquierda hacia la derecha. Pero si la expresión es del tipo:

(...) @ (...) @ (...) @ (...);

el orden de evaluación de los paréntesis es indefinido. Aunque una vez obtenidos todos los resultados parciales, la computación sigue el orden indicado en el punto anterior.

Si existen paréntesis anidados se procede desde dentro hacia fuera:

(((.1.)@(.1.)2) @ (.2.));

- ejemplo Propuesto:
1+5+3-8;
((1+5)+(3-8))

Precedencia de operadores: indica cual es el orden de ejecución de los operadores cuando existen varios.

Por ejemplo, en la expresión:

a * b + c++;      // L.1

la precedencia determina que se ejecutará primero el operador postincremento ++ sobre c. A continuación se aplicará el operador de multiplicación * entre a y b. Finalmente se aplicará el operador suma + entre los resultados anteriores. Así pues, la expresión es equivale a:

(a * b) + (c++);  // L.2

Este orden "natural" del compilador no necesita paréntesis de forma que las sentencias L1 y L2 producen el mismo resultado. Cualquier otro debe ser forzado específicamente mediante la utilización de los paréntesis correspondientes.

Por ejemplo:

a * (b + c)++;    // L.3

- ejemplo Propuesto:

1*3+8*5-4
((1*3)+(8*5)-4)