09:50

1

Temas Gramáticas libres de contexto Árbol de derivación Derivación más a la izquierda y más a la derecha

Ambigüedad Factorización a izquierda Gramáticas propias Expresiones Regulares

Objetivo Que el estudiante logre:  Conocer las distintas características de las gramáticas y aplicar los algoritmos.  Realizar Expresiones Regulares. 09:50

22

Sea G = (VN, VT , S , P) una gramática libre de contexto, un árbol es un árbol de derivación para G si:  La raíz está etiquetada con el símbolo inicial S.  Cada hoja está etiquetada con un símbolo terminal o con .  Si A es un no terminal que etiqueta a algún nodo intermedio y X1 , X2 , ... , Xk son las etiquetas de los hijos de ese nodo, de izquierda a derecha, entonces: A  X1 X2 ... Xk es una producción en P. Aquí, X1, X2,..., Xk son símbolos terminales y/o no terminales.  Si A , entonces el nodo etiquetado con A tiene sólo un hijo etiquetado con . 3

La derivación empieza con el símbolo distinguido S. A continuación se colocan tantas ramas como símbolos terminales y no terminales hayan concatenados en el lado derecho de la regla de producción. Se van sustituyendo cada no terminal por alguna de las partes derechas de una de sus reglas hasta llegar a obtener una sentencia o hilera. Ejemplo: Determinar si w = aabbaa está en L(G). G = {S,A}, {a,b}, P ,S} donde P es: S  aAS / a A  SbA / SS / ba

Para x = aabbaa se tiene: S a

A S

S b A

Propiedad: Sea G = (VN, VT, S, P) una gramática de contexto a libre. Entonces S * , si y sólo si, hay un árbol de derivación en la gramática G con resultado .

b

a a

4

 Si en cada paso de un proceso de derivación se sustituye (o se aplica) a la variable de más a la izquierda por alguna de sus partes derecha de las reglas de producción se dice que es una derivación izquierda. De una forma análoga se define la derivación derecha si las sustituciones que se van realizando en cada regla son siempre en la variable de más a la derecha.  Ambas derivaciones se indican con el símbolo de derivación directa  colocando encima una I (izquierda) o una D (derecha) según corresponda.  Se pueden tener también los cierres transitivos y reflexivos con estas nuevas derivaciones.

5

I

I

I

I

I

Ejemplo: Realizar la derivación más a la izquierda y más a la A  BF  ECF  aCF  abF  abc D D D D D derecha para w = abc. G = ({A,B,C,E,F}, {a,b,c},P,A) donde A  BF  Bc  ECc  Ebc  abc P es:

A  BF B  EC Ea

Cb Fc I

I

I

I

Ejemplo: Realizar la derivación S  aASI  aSbAS  aabAS  más a la izquierda y más a la aabbaS  aabbaa D D D D derecha para w = aabbaa. S  aAS  aAa  aSbAa  aSbbaa G = ({S,A}, {a,b},P,A) donde P es: S  aAS / a A  SbA/ SS / ba

D

 aabbaa

6

 Se dice que una gramática es ambigua si el lenguaje tiene alguna hilera que tenga más de un árbol sintáctico o más de una derivación más a la izquierda o más de una derivación más a la derecha.  Se llama ambigua a la gramática y no al lenguaje que define, puesto que frecuentemente se puede modificar la gramática para que deje de ser ambigua.  Sin embargo, hay lenguajes para los cuales existen únicamente gramáticas ambiguas, a estos lenguajes se los denomina intrínsecamente ambiguos.  La ambigüedad de una gramática es una propiedad indecidible, es decir, no existe ningún algoritmo que acepte una gramática y determine con certeza y en un tiempo finito si la gramática es ambigua o no. 7

Ejemplo Determinar si la siguiente gramática es ambigua. Sea G = ({S}, {a,+,*,(,)}, P, S} donde P es: S  a / S+S / S*S / (S) S

S S

S + S a

*

S

Hay dos árboles de derivación para la hilera a+a*a luego la gramática es ambigua. Se modifica la gramática para que deje de ser ambigua: G = ({S,T,E}, {a,+,*,(,)}, P, S}

S * S

S + S

a

a

a

a

a

SS+T/T TT*F/F F  (S) / a

8

•

•

Si A 1/2 son dos producciones de A y la entrada comienza con una cadena no vacía , no se sabe si expandir A a 1 ó a 2. Sin embargo, se puede retrasar la decisión expandiendo A a A'. Entonces, después de ver la entrada derivada de , se puede expandir A' a 1 ó a 2. Es decir, factorizadas por izquierda las producciones originales se convierten en: A  A' A'  1 / 2

Ejemplo Dada la siguiente gramática factorizar por izquierda. Sea G = ({P,E}, {i,t,e,a,b}, P, P} donde P es: P  iEtP / iEtPeP / a Eb La gramática resultante es: G = ({P,P´,E}, {i,t,e,a,b}, P, P} donde P es: P  iEtPP' / a P'  eP /  Eb 9

Es recursiva a izquierda si las reglas de producción son de la forma: A  A Algoritmo de supresión de la recursividad a izquierda: 1. Se toman las reglas del no terminal A que sea recursiva por izquierda de la forma: A  A 1 / A 2 / .... / A p / 1 / 2 /.../ q donde las primeras p alternativas son recursivas y las q restantes no lo son. 2. Se añade a la gramática un nuevo no terminal A' y todas las reglas A anteriores se sustituyen por las siguientes: A  i A  iA' 1iq A'  j A'  j A' 1jp Ejemplo Eliminar la recursividad a izquierda directa de la siguiente gramática: G = ({S}, {a, b}, P, S) donde P es: S  Sa / Sb / ab A  A1/A2 / 1 La gramática resultante es: G = ({S, S' }, {a, b}, P, S) donde P es: S  ab / abS' S'  a / b / aS' / bS'

10

Es recursiva a izquierda indirectamente si las reglas de producción son de la forma: A  B 1 / ... B  A 2 / … Algoritmo para suprimir la recursividad izquierda indirecta: • Se toma cada grupo de reglas de la forma: A  B 1 / B 2 / .../ B n /1 /.../ p B  A 1 / A 2 /.../A q / 1 / ... /  r • Se reemplaza A por la parte derecha de sus reglas quedando: B  B i j / k j / 1 / ... / r para cada i, j = 1, ... ,q con i = 1, ... ,n, y para cada k, j=1, ... ,q con k = 1, ... ,p • Luego se elimina la recursividad a izquierda directa.

11

Ejemplo: Eliminar la recursividad indirecta en la siguiente gramática: G = ({S, A}, {a, b, c}, P, S) donde P es: S  Aa / b A  Ac / Sb / c Se elimina la recursividad a izquierda indirecta. La gramática resultante es: G = ({S, A}, {a,b,c}, P, S) donde P es: S  Aa / b A  Ac / Aab / bb / c

Se elimina la recursividad a izquierda directa, quedando la gramática así: G = ({S, A. A' } ,{ a,b,c}, P, S) donde P es: S  Aa / b A  bb / c / bbA' / cA' A'  c / ab / cA' / abA'

12

• Es muy importante que una gramática tenga sus reglas con un formato adecuado, lo que facilitará no sólo su lectura y comprensión sino también su compilación. Se pueden tener reglas que produzcan símbolos que no se usen después, o que produzcan la hilera nula, o bien que la regla acabe produciendo o llegando a la misma metanoción en que comenzó; estos son algunos ejemplos de casos que deben evitarse. También es muy conveniente que las gramáticas que se empleen no sean ambiguas. • Toda gramática con imperfecciones se las puede transformar para convertirlas en otra gramática carente de imperfecciones. 13

Lenguaje vacío Un lenguaje vacío es aquel que no tiene hileras (ni siquiera la hilera nula), es decir, L(G) = .

Reglas unitarias Se llama regla unitaria a la que tiene el formato A  B.

14

G = ({S,A,B,C},{a,,b,c}, P, S)

Sea una gramática G = (VN, VT, S, P) , un símbolo X P es: S  aAAA A  aAb / aC es útil, si se tiene las dos cadenas de derivaciones: B  Dc /Ac Cb * * S  X  t , sino X es inútil. Donde:  y   (VN VT)*, S VN, t VT y X (VN VT)

Se deben considerar dos aspectos para determinar la utilidad de un símbolo: – Se debe poder derivar alguna hilera del símbolo X, si es así se dice que X es terminable. – X debe aparecer en alguna forma sentencial del axioma S, se le denomina entonces accesible.

15

Se llama regla lambda o borradora a una regla del tipo A . Un no terminal A se dice que es anulable si: * A  Si  pertenece a L(G), entonces no se podrá eliminar todas las reglas  de la gramática, pero si no es así se puede eliminar. Se dice que una gramática es sin reglas, si se cumple una de las dos condiciones siguientes: 1) no hay ninguna regla  en P; 2) hay sólo una regla asociada al axioma S   y además S no aparece en la parte derecha de ninguna regla de P.

Cuando una gramática no tiene ciclos, ni reglas , ni símbolos inútiles, se dice que es propia. 16

Característica de las gramáticas regulares • Se denomina operaciones regulares a la unión, concatenación y clausura de la iteración. • Existe una interesante propiedad para los lenguajes de estructura de frase que se la puede expresar de la siguiente manera: toda clase de lenguaje Li (i=0,1,2,3) es cerrada sobre las operaciones regulares. • Los lenguajes de tipo 3, generados por gramáticas regulares, tienen otra caracterización importante: se puede definir un lenguaje comenzando con un número finito de palabras y aplicando operaciones regulares sobre ellas. Este método se conoce como expresiones regulares. 17

Una ER se construye a partir de ER más simples utilizando un conjunto de reglas definitorias. Cada ER r representa un lenguaje L(r). Las reglas de definición especifican cómo se forma L(r) combinando de varias maneras los lenguajes representados por las subexpresiones de r. Reglas que definen las ERs sobre un alfabeto finito V . 1)  es una ER que designa {}; es decir, el conjunto que contiene la cadena vacía. 2) Si a es un símbolo de V, entonces a es una ER que designa {a}; por ejemplo, el conjunto que contiene la cadena a. 3) Suponiendo que r y s sean ERs que representan los lenguajes L(r) y L(s), entonces, ( r ) / ( s ) es una ER que representa L( r ) U L( s ) ( r) ( s ) es una ER que representa L( r ) L( s ). ( r )* es una ER que representa (L( r ))*. 18

Ejemplos de expresiones regulares Las siguientes son expresiones regulares sobre el vocabulario V = {a,b}:  ER = a/b  {a,b}  ER= (a/b)(a/b)  {aa,ab,ba.bb}  ER= aa/ab/ba/bb  {aa,ab,ba.bb}  ER= a*  { , a, aa, aaa, .... }.  ER= (a/b)*  conjunto de todas las cadenas que contienen cero o más casos de una a o b, es decir, el conjunto de todas las cadenas de a y b.  ER= a/a*b  conjunto que contiene la cadena de a y todas las que se componen de cero o más a seguidas de una b. 19

Se pueden evitar los paréntesis innecesarios en las expresiones regulares si se adoptan las convenciones:

a) Es opcional el uso de "." para denotar la concatenación. b) * tiene precedencia más alta que la concatenación (.) y que la unión (/) y es asociativa a izquierda. c) la concatenación tiene precedencia más alta que (/) y es asociativa a izquierda. d) la unión tiene menor precedencia y es asociativa a izquierda. Ejemplo: ((0(1*))/0) se puede escribir como: 01*/0

20

ABREVIATURAS EN LA NOTACIÓN 1- Uno o más casos: El operador unitario postfijo + significa "uno o más casos de". Si r es una ER que designa al lenguaje L(r), entonces (r)+ es una ER que designa al lenguaje (L(r))+ . r* = r+ /  y r+ = rr* son dos identidades algebraicas. 2- Cero o un caso: El operador unitario postfijo ? significa "cero o un caso de" . La notación r? es una abreviatura de r /  . Si r es una ER, entonces (r)? es una ER que designa el lenguaje L(r) U {}. 3- Clases de caracteres: La notación [abc], donde a, b y c son símbolos del vocabulario, designa la ER a/b/c . Una clase abreviada de carácter como [a-z] designa la ER a/b/ ... /z. Ejemplo: la ER que designa un identificador, que está formado por una letra seguido de cero o más letras o dígitos es el siguiente: [a-zA-Z][a-zA-Z0-9]*

21

PROPIEDADES Y EQUIVALENCIAS Si dos ER r y s representan al mismo lenguaje, se dice que r y s son equivalentes y se escribe r = s. Por ejemplo, (a/b) = (b/a). AXIOMA

DESCRIPCIÓN

r/s = s/r

La unión ( / ) es conmutativa

r/(s/t) = (r/s)/t

La unión ( / ) es asociativa

(rs)t = r(st)

La concatenación es asociativa

r(s/t) = rs / rt (s/t)r = sr / tr

La concatenación distribuye sobre la unión ( / )

r=r r=r

 es el elemento identidad para la concatenación

r* = (r /  )*

Relación entre * y 

r** = r*

* es idempotente

/r=r r/=r

 es el elemento identidad para la unión ( / ) 22

Árbol de Derivación Derivación más a la izquierda y más a la derecha Gramáticas libres de contexto

Recursividad a izquierda directa e indirecta Factorización a izquierda Ambigüedad Gramáticas Propias

Importancia Práctica: para algunos Analizadores Sintácticos se necesitan que las GLC no presenten recursividad a izquierda o estén factorizadas y sin imperfecciones.. Gramáticas Regulares

Expresiones Regulares

Importancia Práctica: se usan para el Analizador Lexicográfico, para reconocimiento de patrones.

23