Autómatas y lexers

orden del día:

  1. Repaso de DFA
  2. DFA de ejemplo
  3. Ejercicio de DFA de ejemplo #1
  4. Ejercicio de DFA de ejemplo #2
  5. Ejercicio interactivo de DFA #1
  6. Ejercicio interactivo de DFA #2
  7. Intervalo
  8. Lexers
  9. Ejemplo de lexers
  10. Generador de lexers: flex
## Breve repaso de DFA Composición de un DFA: - Alfabeto $\Sigma$ - Conjunto de estados $D$ - Función de transición $T:D\times\Sigma\rightarrow D$ - Estado inicial $S_0 \in D$ - Estados de aceptación $A \subset D$ Un DFA es una tupla $(\Sigma,D,T,S_0,A)$.

Cómo visualizar un DFA

$(\Sigma,D,T,S_0,A)$

El siguiente DFA detecta un número impar de letras a.

A continuación se describe el mismo DFA sin un diagrama.

  • Alfabeto $\Sigma=\{a,b\}$
  • Conjunto de estados $D=\{pares, impares\}$
  • Estado inicial $S_0 = pares$
  • Estados de aceptación $A={impares}$
  • Función de transición $T:D\times\Sigma\rightarrow D$: tabla a continuación
estado letra nuevo estado
$pares$ $a$ $impares$
$pares$ $b$ $pares$
$impares$ $a$ $pares$
$impares$ $b$ $impares$
## Ejercicio ejemplo 0 Dado $\Sigma = \{a,b\}$ , autómata que acepte todas las palabras que tienen menos de 2 `b`. Casos de prueba: - `aab` - `aabaa` - `aabaab` - `b` - `bbaaba` --- ## Ejercicio ejemplo 1 Dado $\Sigma = \{a,b,c,d\}$, autómata que acepte todas las palabras que contienen `abc`, y no tengan ninguna `d`. Casos de prueba: - `aab` - `aabd` - `aabca` - `aabcad` - `ccca` - `ccdca` --- ## Ejercicio interactivo 1 Dado $\Sigma = \{a,b\}$, autómata que acepte todas las palabras que contienen un número par de `a` y una `b`. Casos de prueba: - `aab` - `baa` - `aaba` - `bbb` --- ## Ejercicio interactivo 2 Dado $\Sigma = \{a,b,c\}$, autómata que acepte únicamente las palabras `b`, `ab`, `aba`. Todo lo demás es inválido. Casos de prueba: - `bb` - `abb` - `abba` - `aba` - `ababab`
Intervalo 10'

Lexers

## Qué es un lexer ```c float matchO(char *s) { /* find a zero */ if (!strncmp(s, "0.0", 3)) return 0.; } ``` ```python [ (KEYWORD_FLOAT), (ID,"match0"), (LEFT_PAREN), (KEYWORD_CHAR), (STAR), (ID,"s"),(RIGHT_PAREN), (LEFT_BRACE), (KEYWORD_IF),(LEFT_PAREN),(BANG),(ID,"strcmp"),(LEFT_PAREN),(ID,"s"),(COMMA),(STRING,"0.0"),(COMMA),(NUM,"3"),(RIGHT_PAREN),(RIGHT_PAREN), (KEYWORD_RETURN),(REAL,"0."),(SEMICOLON), (RIGHT_BRACE), (EOF), ] ``` _Listado priorizado de expresiones regulares (siempre gana el match más largo)_
## Ejemplo: Lenguaje 4++ Se permite separar con `_` | Expresión regular | tipo de token | | ----------------- | ------------- | | `40` | `CUARENTA` | | `4+` | `CUATROS` | | `\+\+` | `MAS_MAS` | Ejemplos: | frase | tokens | |-|-| |`4444++40`|`(CUATROS,4444),(MAS_MAS,++),(CUARENTA,40)`| |`++++4444`|`(MAS_MAS,++),(MAS_MAS,++),(CUATROS,4444)`| |`4__40`|`(CUATROS,4),(CUARENTA,40)`| |`404`|`(CUARENTA,40),(CUATROS,4)`|
Nuevos tipos de estado:
  • Estado inicial: separado
  • Estado tokenizable
  • Estado inválido
  • Estado muerto
## Intro a flex ``` sudo apt install flex ``` ``` flex -iI ejemplo.l && gcc -g lex.yy.c -o lexer -ll && ./lexer ``` ``` %% hola { printf("token1 %s\n",yytext); } 1 { printf("token2 %s\n",yytext); } . { printf("ERROR %s\n",yytext); } %% ```

¿Preguntas?

¡A trabajar!