• Author / Uploaded
• Evander Flores

• Categories
• Expresión regular
• Gramática
• Comunicación humana
• Reglas
• Símbolos

Citation preview

Lenguajes Formales y de Programación Gramaticas Regulares y Expresiones Regulares Evander Flores ([email protected])

1

Objetivos  Definir que es una gramática.  Identificar los componentes de una gramática.  Determinar la estructura para la construcción de gramáticas 

  

2

regulares. Construir de árboles de derivación Identificar gramáticas ambiguas Definir Expresiones Regulares Reglas de construcción para Expresiones Regulares

Gramáticas Concepto, componentes y estructura

3

Gramática  Sirven para describir como se genera las cadenas del

lenguaje.  Se clasifican al igual que los lenguajes según la Jerarquía de Chomsky como gramáticas tipo 0, 1, 2 y 3  Están construidas a través de cuádruplas.

4

Definición de Gramática Definida por G = (N, T, P, S) donde  N Conjunto finito de símbolos no terminales (Alfabeto)  T Conjunto finito de símbolos terminales

 P es un conjunto finito de producciones  S Símbolo incial

5

Componentes de una Gramática N Conjunto de No Terminales  Son símbolos definidos que representan una expresión del

lenguaje.  Por lo general son representados por medio de letras o palabras en MAYUSCULAS.

S Símbolo Inicial  Símbolo No Terminal que representa el inicio de la gramática.  Por lo general se utiliza la letra S.

6

Componentes de una Gramática T Conjunto de Terminales  Son símbolos que representan a un token de la gramática.  Los tokens son expresiones que se definen por medio de

Expresiones Regulares  Por lo general son representados por medio de letras o palabras en minúsculas.

7

Componentes de una Gramática P Conjunto de Producciones  Es la representación de una definición de la gramática.  Utiliza en el lado izquierdo un símbolo No Terminal  El lado derecho una secuencia de símbolos terminales y no terminales; también puede ser una cadena vacía (ε)

8

GRAMÁTICA regular Estructura, Producciones, Clasificación, Árbol de Derivación, gramáticas ambiguas.

9

Gramática Regular  Generan los lenguajes regulares, reconocidos por un

autómata finito.  Son las gramáticas más restrictivas.  El lado derecho de una producción es como mínimo un símbolo TERMINAL o NO TERMINAL y del lado izquierdo como máximo uno NO TERMINAL.

10

Gramáticas Regulares

Producción  Representada generalmente

→ Lado Izquierdo

Símbolo No Terminal

11

::= -> == = 

Lado Derecho • ε (Cadena vacía) • terminal (uno o más) • No Terminal (uno o más) • Combinación de terminales y No Terminales.

Ejemplos de Producciones Correctas

Incorrectas

 Aa

 A  aεB

 B  Aa

 AB  C

 Cε

 a  DE

 D  numero  E  num . num  F  aA  G  AabcD

12

Clasificación de Gramáticas Regulares Las gramáticas regulares se dividen dependiendo de la estructura de las producciones, esto depende de la dirección hacia la que se expanden:  Lineales a la derecha  A → aB

A→a

 Lineales a la izquierda  A → Ba A→a Donde A y B son NO TERMINALES Donde a es TERMINAL

13

Gramáticas Regulares

Lineales a derecha Los símbolos No Terminales se ubican al lado derecho de la producción.  G1 = ({A, B}, {a}, P1, S1)

S1 → ε S1 → aA A → aB A→a B → aA

14

Gramáticas Regulares

Lineales a Izquierda Los símbolos No Terminales se ubican al lado izquierdo de la producción.  G2 = ({C, D}, {a}, P2, S2)

S2 → ε S2 → Ca C → Da C→a D → Ca

15

Árbol de Derivación  Consiste en la esquematización de la Gramática, a través de

una entrada determinada.  Permite identificar la secuencia por la cual una cadena es reconocida por la gramática.  También son llamados árboles sintáxis.

16

Árbol de Derivación Para ser un árbol un conjunto de nodos y arcos debe satisfacer ciertas propiedades:  hay un único nodo distinguido, llamado raíz (se dibuja en la parte superior) que no tiene arcos incidentes.  todo nodo c excepto el nodo raíz está conectado con un arco a otro nodo k, llamado el padre de c (c es el hijo de k). El padre de un nodo, se dibuja por encima del nodo.  todos los nodos están conectados al nodo raíz mediante un único camino.  los nodos que no tienen hijos se denominan hojas, el resto de los nodos se denominan nodos interiores. 17

Árbol de Derivación El árbol de derivación tiene las siguientes propiedades:  - el nodo raíz está rotulado con el símbolo distinguido de la gramática;  - cada hoja corresponde a un símbolo terminal o un símbolo no terminal;  - cada nodo interior corresponde a un símbolo no terminal.

18

Construcción  El símbolo inicial S es la raíz  Los nodos internos son símbolos NO Terminales  Las hojas son los símbolos terminales.  No son árboles binarios, cada nodo representa la secuencia de

cada producción, independientemente del número de símbolos.

19

Ejemplo Gramática S  aB B  bC Cc

Cadena abc

20

Ejemplo Gramática S  aB B  aBB |b

Cadena aabb

21

Gramáticas Ambiguas  Una gramática es ambigua si permite construir dos o más 

 

 22

árboles de derivación distintos para la misma cadena. Una gramática en la cual, para toda cadena generada w, todas las derivaciones de w tienen el mismo árbol de derivación es no ambigua Una gramática G(N,T,P,S) se considera ambigua, si existen por lo menos dos árboles de derivación que la representen. Una gramática es ambigua si por lo menos posee una producción ambigua. La ambigüedad es una propiedad indecidible

Gramáticas Ambiguas  Aquí hay un ejemplo de este tipo de gramáticas, donde se

reconoce la misma entrada a+a+a A → A +A |a

23

Expresiones Regulares

24

Expresion Regular  Constituyen un mecanismo bastante potente para realizar

manipulaciones de cadenas de texto  Representan de forma más simple un Lenguaje Regular  Representan un patrón por medio del cual se construyen palabras.  Utiliza caracteres de un alfabeto (Σ) definido, para la construcción.

25

Elementos de Definición Los elementos más comunes utilizados para definir una Expresión Regular son:

26

Símbolo

Significado

*

repetición 0 o más veces (Cerradura de Kleene)

+

Repetición 1 o más veces (Cerradura Positiva)

?

Aparece 1 vez o ninguna

()

Agrupación

|

Indica opciones (o lógico)

\

Marca de caracter especial

^

Comienzo de una linea

[]

Agrupación de conjunto de caracteres opcionales

$

Final de línea

Elementos de Definición Los elementos más comunes utilizados para definir una Expresión Regular son:

27

Símbolo

Ejemplo

Resultado

*

1*234

Vale= 1234, 234,111234

+

a+bbc

Vale= abbc, aabbc, aaabbc

?

0?11

Vale= 11, 011

()

(abc)

Genera= abc

|

(si|no|talvez)

Vale= si, no, talvez

\

\t, \n

Tabulador, fin de línea

^

^M

Lineas que comienzan con M

[]

escrib[aoe]

Vale= escriba, escribo, escribe

$

Fin$

Palabras que terminan con Fin

Elementos de Definición

Cerradura de Kleene También llamada Cerradura de Estrella se define como: A*= U n≥0 An

La cadena se forma al realizar 0 o más concatenaciones de los símbolos o caracteres que aplica.  a* = { ε , a, aa, aaa, aaaa, aaaaa }  0*21 = { 21 , 021, 0021, 00021 }

28

Elementos de Definición

Cerradura Positiva Se define como: A+ = ∪n>0 An Donde la cadena esta formada por al menos una repetición de la cadena.  a+ = { a, aa, aaa, aaaa, aaaaa}  hi+ = { hi, hii, hiii, hiiii }  mi+au+ = { miiiiau, miiiauuuuu, miau }

29

Elementos de Definición

Aparición Utiliza el símbolo ? para indicar si el carácter que lo precede puede aparecer o no dentro de la cadena.  a? = { ε , a }  (sub)?marino = { submarino, marino}

30

Elementos de Definición

Agrupación Se utilizan los paréntesis para agrupar los caracteres del alfabeto que se utilizan.Y la precedencia de los operadores que se utilizan.  (bis|tatar)?abuel(o|a) = { abuelo, bisabuelo, tatarabuelo, bisabuela }  (0|1)0 = {10 , 00 }

31

Elementos de Definición

Alternativa Utiliza la barra “ | ” para indicar que puede existir alguna alternativa dentro de los símbolos o caracteres.  blanco|negro = { blanco , negro }  norte|sur|este|oeste = { sur, este, norte}  (m|p)adre = { madre, padre }

32

Elementos de Definición

Caracter Especial Se utiliza la barra invertida \ para denotar un caracter especial  \t describe espacios tabuladores  \” describe una comilla  \n indica el fin de una línea  \f indica un salto de pagina

33

Elementos de Definición

Agrupación de Caracteres Se utilizan los corchetes [ ] para agrupar clases de caracteres, así se define una gama de símbolos relacionados entre sí. Utilizando solo uno de ellos.  [A-Z] = { A, B, D,Y, M, O, P }  [0-9] = dígito del 0 al 9  [0-9]+.[0-9] = números con un decimal.

34

Elementos de Definición

Comienzo de línea El caracter ^ es utilizado para describir una cadena específica la cual se encontrara en cada inicio de línea  ^usac describe todas las líneas que inician con la palabra usac  ^Numero:[0-9]+ líneas que comienzan con la palabra Numero seguida de dos puntos y cualquier grupo de dígitos

35

Elementos de Definición

Fin de palabra El caracter $ es utilizado para indicar el fin de una palabra en cualquier cadena  z$ palabras que terminan con la letra z  [aeiou]$ palabras que terminan en vocal

36

Precedencia  El orden de precedencia para los operadores es:  Paréntesis ()  Cerraduras  Concatenación .

37

Ejemplo: Generación de Palabras  Sea ER = (ab*) | (abc*) las palabras que genera son:  Sea ER = z?x+(z*o)+ las palabras que genera son:

38

Ejemplo: Generación de Palabras Las palabras más cortas que se obtienen de  (01+0*) | (10?1)  01 , 11  a(b+c)*(ab)

 aab

 ((ab+ba)|baab)*

39

 abba , baab, ε

Ejemplo: Construcción ER Expresar, mediante una expresión regular, el lenguaje formado por el alfabeto S = {a, b}, donde las palabras inician con a y finalizan siembre con bb

40

Ejemplo: Construcción ER Expresar, mediante una expresión regular, el lenguaje formado por el alfabeto S = {a, b,c}, donde todas las cadenas no tiene ninguna subcadena ac se denota mediante la expresión regular:

41

GRAMÁTICAS y Expresiones regular Relación entre GR y ER

42

Relación ER-LR

43

Expresión Regular

Lenguaje

ε

{ε}

0

{0}

abc

{abc}

0|1

{0,1}

(1|ε)001

{1,e}{001}={1001,001}

(1|0)*(0|1)

{1|0}*{0,1}={1110,000,….}

Equivalencia ER  Dos o más expresiones regulares son equivalentes, si se

refieren al mismo lenguaje. ER

011* 01+

44

Equivalente

LR

01, 011,0111 0111, 01

Ejercicio  Escriba una expresión regular para el lenguaje denotado

por el alfabeto S={x, y, z} que reconozca cadenas que empiecen con x y terminen con z pero que no tengan dos y consecutivas: RESPUESTA(una de tantas posibles): x ( y? ( x | z )+ )* y? z

45