TEORA DE LA COMPUTACIN

Febrero 2011
5/23/12

Haga clic para modificar el estilo de subttulo del patrn

22

Lenguajes y gramticas
Una gramtica describe un lenguaje. Dada una sentencia y usando la gramtica podemos saber si pertenece al lenguaje. Una gramtica est formada por: G={VT,VN,S,P} donde:

VT=Vocabulario Terminal. Smbolos que forman las sentencias del lenguaje. VN=Vocabulario no terminal. Smbolos auxiliares que se usan en las producciones.
5/23/12

33

Definiciones
S=Smbolo inicial. Smbolo del VN a partir del cual obtenemos todas las sentencias del lenguaje. P=Conjunto de producciones. Transformaciones que convierten smbolos en un resultado.

5/23/12

44

Definiciones
Un lenguaje es el conjunto de todas las sentencias que pueden generarse a partir de una gramtica. Se dice que una sentencia pertenece al lenguaje si:
1. 2.

Est formada por el primer smbolo VT Partiendo del smbolo inicial S y aplicando transformaciones podemos llegar a dicha sentencia.

5/23/12

55

Definiciones
Ejemplo: G=({a,b},{S,A},S,{P}) P=S Aa, A bA | bba pertenece al lenguaje porque

5/23/12

S Aa bAa bbAa bba

5/23/12

77

bbbbaa

Est en el lenguaje?

P=S Aa, A bA | | aA

5/23/12

S Aa bAa bbAa bbbAa bbbbAa bbbbaAa bbbbaa Si est en el lenguaje

5/23/12

99

Definir la gramtica para el lenguaje conformado por (00100)* 001000010000100 G={ {0,1},{S,A,B },{S,P} } P= S A, A 001B | , B 00A

5/23/12

S 001B 00100A 00100001B 0010000100A 0010000100

5/23/12

Definiciones
11 11

Gramticas Aho, Ullman Una gramtica libre de contexto tiene cuatro componentes:
1.- Un conjunto de smbolos terminales, a los que algunas veces se les conoce como tokens. Los terminales son los smbolos elementales del lenguaje definido por la gramtica.

MC. Salvador Contreras H.

5/23/12

Gramticas Aho, Ullman

12 12

2.- Un conjunto de no-terminales, a los que algunas veces se les conoce como variables sintcticas. Cada no-terminal representa un conjunto de cadenas o terminales. 3.- Un conjunto de producciones, en donde cada produccin consiste en un no-terminal, llamada encabezado o lado izquierdo de la produccin, una flecha y una secuencia de terminales y no terminales llamada cuerpo o lado derecho de la produccin.
5/23/12

MC. Salvador Contreras H.

Gramticas Aho, Ullman

13 13

(Continuacin) La intencin intuitiva de la produccin es especificar una de las formas escritas de una instruccin; si el no terminal del encabezado representa una instruccin entonces el cuerpo representa una forma escrita de dicha instruccin. 4.- Una designacin de uno de los no terminales como smbolo inicial.

MC. Salvador Contreras H.

5/23/12

14 14

Ejemplo: lista->lista + dgito lista->lista dgito lista->dgito digito->0|1|2|3|4|5|6|7|8|9

MC. Salvador Contreras H.

5/23/12

15 15

Tambin puede representarse de la siguiente forma: lista->lista + digito | lista-dgito | digito

MC. Salvador Contreras H.

5/23/12

Derivaciones
16 16

Una gramtica deriva cadenas empezando con el smbolo inicial y sustituyendo en forma repetida un no terminal, mediante el cuerpo de una produccin para ese no terminal. Las cadenas de terminales que pueden derivarse del smbolo inicial del lenguaje definido por la gramtica.

MC. Salvador Contreras H.

5/23/12

17 17

rboles de anlisis sintctico

Muestra en forma grfica la manera en que el smbolo inicial de una gramtica deriva a una cadena en el lenguaje. Si el no terminal A tiene una produccin A->XYZ, entonces un rbol de anlisis sintctico podra tener un nodo interior etiquetado como A, con tres hijos llamados X,Y y Z de izquierda a derecha.

MC. Salvador Contreras H.

5/23/12

18 18

rboles de anlisis sintctico

A

La raz se etiqueta con el smbolo inicial. Cada hoja se etiqueta con un terminal o con
MC. Salvador Contreras se etiqueta con un no 5/23/12 Cada nodo interior H. terminal

19 19

rboles de anlisis sintctico

4. Si A es un 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, entonces debe existir una produccin. A->X1X2Xn Aqu cada una de las etiquetas A->X1X2Xn representa a un smbolo que puede ser un terminal o no terminal.

MC. Salvador Contreras H.

5/23/12

20 20

Ejemplo: 9-5+2
lista lista digito

lista

digito

digito

2
5/23/12

MC. Salvador Contreras H.

Ejercicios
21 21

Considere la siguiente gramtica libre de contexto. S->SS+|SS*|a a) Muestre como puede generarse la cadena aa+a* mediante esta gramtica. b) Qu lenguaje genera esta gramtica? Justifique su respuesta.

MC. Salvador Contreras H.

5/23/12

Ejercicios
22 22

Qu lenguajes se generan mediante las siguientes gramticas? En cada caso justifique su respuesta. A) S->0S1|01 B) S->+SS|-SS|a C) S-> S(S)S| D) S->aSbS|bSaS| E) S->a|S+S|SS|S*|(S)

MC. Salvador Contreras H.

5/23/12

Analizador Lxico
23 23

Analizador lxico (scanner): lee la secuencia de caracteres del programa fuente, caracter a caracter, y los agrupa para formar unidades con signifcado propio, los componentes lxicos (tokens en ingls).

MC. Salvador Contreras H.

5/23/12

24 24

Estos componentes lxicos representan: palabras reservadas: if, while, do, . . . identifcadores: asociados a variables, nombres de funciones, tipos defnidos por el usuario, etiquetas,... Por ejemplo: posicin, velocidad, tiempo, . . .

MC. Salvador Contreras H.

5/23/12

25 25

operadores: = * + - / == > < & ! = . . . smbolos especiales: ; ( ) [ ] f g ... constantes numricas: literales que representan valores enteros, en coma fotante, etc, 982, 0xF678, -83.2E+2,... constantes de caracteres: literales que representan cadenas concretas de caracteres, \hola mundo",...

MC. Salvador Contreras H.

5/23/12

26 26

El analizador lxico opera bajo peticin del analizador sintctico devolviendo un componente lxico conforme el analizador sintctico lo va necesitando para avanzar en la gramtica.

MC. Salvador Contreras H.

5/23/12

27 27

Los componentes lxicos son los smbolos terminales de la gramtica. Suele implementarse como una subrutina del analizador sintctico.

MC. Salvador Contreras H.

5/23/12

28 28

Cuando recibe la orden obtn el siguiente componente lxico, el analizador lxico lee los caracteres de entrada hasta identificar el siguiente componente lxico.

MC. Salvador Contreras H.

5/23/12

29 29

MC. Salvador Contreras H.

5/23/12

30 30

Otras funciones secundarias: Manejo del archivo de entrada del programa fuente: abrirlo, leer sus caracteres, cerrarlo y gestionar posibles errores de lectura. Eliminar comentarios, espacios en blanco, tabuladores y saltos

MC. Salvador Contreras H.

5/23/12

31 31

Inclusin de archivos: # include ... La expansin de macros y funciones inline: # define ... Contabilizar el nmero de lneas y columnas para emitir mensajes de error.

MC. Salvador Contreras H.

5/23/12

32 32

Patrn: es una regla que genera la secuencia de caracteres que puede representar a un determinado componente lxico (una expresin regular).

MC. Salvador Contreras H.

5/23/12

33 33

Lexema: cadena de caracteres que concuerda con un patrn que describe un componente lxico. Un componente lxico puede tener uno o infinitos lexemas. Por ejemplo: palabras reservadas tienen un nico lexema. Los nmeros y los identificadores tienen infinitos lexemas.

MC. Salvador Contreras H.

5/23/12

34 34

MC. Salvador Contreras H.

5/23/12

Jerarqua de Chomsky
La jerarqua de Chomsky es una clasificacin de tipos de gramticas que generan lenguajes formales. Consta de cuatro niveles: 1. Gramticas de tipo 0, o sin restricciones, que incluyen a todas las gramticas formales.

5/23/12

Estas gramticas generan todos los lenguajes capaces de ser reconocidos por una mquina de Turing. Estos lenguajes son conocidos como lenguajes recursivamente enumerables.

5/23/12

Gramticas de tipo 1. Estas gramticas tambin se suelen llamar sensibles al contexto, y generan los lenguajes sensibles al contexto. Estas gramticas tienen reglas de la forma A ,, con A un no terminal y , y cadenas de terminales y no terminales.

5/23/12

 y pueden ser cadenas vacas, pero no puede serlo. La regla est permitida si S no aparece en la parte derecha de ninguna regla. Los lenguajes descritos por estas gramticas son exactamente todos aquellos lenguajes reconocidos por una mquinas de Tuirnig no determinista cuya cinta de memoria est acotada por un cierto nmero entero de veces sobre la longitud de entrada.
5/23/12

Gramticas de tipo 2, tambin llamadas libres de contexto, generan lenguajes independientes del contexto. Las reglas son de la forma A con A un no terminal y una cadena de terminales y no terminales. Estos lenguajes son aquellos que pueden ser reconocidos por un autmata de pila.

5/23/12

En lingistica e informtica, una gramtica libre de contexto es una gramtica formal en la que cada regla de produccin es de la forma: V w Donde V es un smbolo no terminal y w es una cadena de terminales y/o no terminales. La expresin libre de contexto se refiere al hecho de que el no terminal V puede siempre ser sustituido por w sin tener en cuenta el contexto en el que ocurra. De esta manera, un lenguaje formal es libre de contexto si hay una gramtica libre de contexto que lo genera.
5/23/12

Las gramticas libres de contexto permiten describir la mayora de los lenguajes de programacin. La sintaxis de la mayora de lenguajes de programacin est definida mediante gramticas libres de contexto.

5/23/12

Actividad de aprendizaje: Investigacin

Equipo 1. Describir la jerarqua de Chomsky. Incluir la explicacin para cada una de las gramticas. Equipo 2. Mquinas de Mealy. Describir su funcionamiento. Explicar un ejemplo. Equipo 3. Autmatas de pila. Describir la base terica. Explicar un ejemplo.
5/23/12

Actividad de aprendizaje
Criterios de aprendizaje: La investigacin podr realizarse en Internet. Cada quipo deber realizar una presentacin en Power Point. Explicar el tema ante el grupo. Tiempo: 60 min. Para la investigacin, 10 min. para la presentacin.

5/23/12