Análise Léxica

Frank Coelho de Alcantara - 2021    

Tradução em Linguagem de Máquina

Para que uma máquina possa executar um algoritmo, o texto que escrevemos deve ser traduzido em uma linguagem que a máquina entenda. Uma linguagem de máquina.

Esta tradução pode ser realizada por compilação, interpretação ou por processos mistos. Não há relação entre uma linguagem e a forma como ela é traduzida.

Processo de Versionamento

Analisador Léxico

Módulo Responsável pela interpretação dos Lexemas (palavras) de uma determinada linguagem. No nosso caso, de uma linguagem formal.

Lexema é um termo mais amplo por que inclui todos os conjuntos de símbolos que são possíveis em uma linguagem.

Vamos usar preferencialmente lexema, mas palavra é um bom sinônimo para você entender o conceito.

Analisador Sintático

Responsável pela análise da estrutura da linguagem.

Cabe ao analisador sintático determinar se uma determinada declaração de uma determinada linguagem está corretamente formatada.

A análise sintática se preocupa com a forma das sentenças, não com os lexemas e não com o sentido da sentença.

Analisador Semântico

O analisador semântico é responsável pela interpretação de cada declaração da linguagem. Análise semântica é análise de sentido.

Erros de tipos, declaração de variáveis, composição de argumentos, estão entre os problemas que cabem ao analisador semântico.

A análise semântica se preocupa com o sentido da sentença.

Geração de código intermediário

Cabe ao gerador de código intermediário, otimizar o código e transformá-lo em uma linguagem mais próxima da linguagem da máquina.

Neste módulo encontramos as maiores oportunidades para desenvolvimento de tecnologia. O Java, o Chrome, o LLVM são projetos que dependem do código intermediário para o seu sucesso.

A geração de código intermediário é fundamental para o sucesso do processo de interpretação.

Otimização de código

Este módulo pode estar dentro, fora, ou tanto no gerador de código intermediário quanto após este módulo. É responsável por fazer com que o código de máquina gerado seja o mais eficiente e eficaz possível.

A otimização de código é a última ação, antes de chegarmos ao Assembly.

Sistemas de compilação como o LLVM, possuem diversos projetos diferentes competindo pelo código mais eficiênte.

Linguagens Formais

Uma linguagem formal é uma linguagem artificial criada pelo homem, para atender alguma função específica.

A música é uma linguagem formal. Existe uma linguagem artificial criada para a escrita, leitura e interpretação de músicas. O cálculo proposicional também é uma linguagem formal.

Há uma pequena diferença entre linguagens formais e regulares. Todas as regulares são formais, mas nem todas as formais são regulares.

Linguagens Naturais

As linguagens naturais são fruto da evolução da especie humana. Ocorrem de forma natural, ainda não perfeitamente entendida. A base do nosso desenvolvimento como espécie.

As linguagens naturais não possuem regras estáticas de grafia, sintaxe ou semântica. Estas definições evoluem com a linguagem.

Iremos, ao longo desta disciplina, melhorando a definição de linguagem formal até incluir todas as nuances deste conceito.

Alfabetos

Um alfabeto é um conjunto finito de símbolos que podem ser utilizados em uma determinada linguagem.

Nesta disciplina, vamos usar o caractere $\Sigma$ (Sigma) para representar um alfabeto com um índice para identificar sua linguagem.

Considerando esta norma, O $\Sigma_{bin}$ representa o alfabeto da linguagem binária. A definição deste alfabeto pode ser: $$\Sigma_{bin} = \{0,1\}$$

Alfabetos - representação

Se desconsideramos os símbolos de pontuação, e símbolos de outros idiomas como o latim ou o grego. O alfabeto do português, como falado no Brasil, pode ser representado por:
$$\Sigma_{pt_br} = \{a..z,A..Z,0..9\}$$

Este alfabeto, conjunto de símbolos, teria a cardinalidade de 62. Tal que: $$|\Sigma_{pt_br}| = |\{a..z,A..Z,0..9\}| = 62$$

Strings 1

Vamos chamar de strings a sequências finitas de símbolos de um alfabeto $\Sigma$ específico de uma linguagem determinada.

A strings podem ter qualquer comprimento, inclusive comprimento nenhum.

A esta string que existe, mas não tem comprimento daremos o nome de string vazia e representaremos pelo símbolo $\varepsilon$.

Strings 2

Dado o alfabeto $\Sigma=\{a,b\}$, o conjunto de todas as strings possíveis com este alfabeto será dado por: $$S=\{\varepsilon,a,b,ab,ba,aa,bb,aaa, ...\}$$

O conjunto das strings possíveis é infinito, como não há limites em comprimento, sempre podemos colocar outro símbolo na string.

O conjunto das strings de uma linguagem não é infinto.

Strings 3

Formalmente, representaremos strings como conjuntos. Afinal é isso que elas são. Então uma string qualquer poderia ser: $$s=\{a,b,b\}$$ informalmente representaremos como: $s=\text{"abb"}$.

A string $s$ tem cardinalidade 3.
Observe que: $|{a,b,b}|_a = 1$.

Definição

Linguagens Formais e Regulares

Linguagens formais e regulares, são aquelas que podem ser definidas por máquinas de estado finito, determinísticas ou não, e por expressões regulares. Atendendo ao Teorema de Kleene .
Isto significa que podemos criar uma máquina de estado finito (MEF) equivalente a uma expressão regular (Regex) ou uma expressão regular equivalente a uma máquina de estados finitos. De tal forma que: $$MEF \equiv Regex$$

Máquinas de Estado Finito

Um máquina de estados finitos é uma abstração matemática definida pela 5-tupla, com apenas cinco conceitos:

1. $S$: um conjunto finito de estados;
2. $\Sigma$: um alfabeto de entrada finito;
3. $\delta: S\times \Sigma \rightarrow S$: um conjunto finito funções de transição;
4. $s_0$: um estado inicial;
5. $A \subseteq S$: um conjunto finito de estados de aceitação;

$$MEF=\{S, \Sigma, \delta, s_0, A\}$$

Estados e Transições

Conceitos Adicionais

$\Sigma^*$ é o conjunto de todos os strings, de comprimento maior que $0$ que podem ser criadas a partir de $\Sigma$.

$L(MEF)=\{w|\delta^*(s_0,w)\in A\}$ é o conjunto de todas as strings aceitas por $MEF$.

Chamamos o conjunto $L(MEF)$ de Linguagem da $MEF$.

Aceitação ou identificação

Uma string $w$ será aceita por uma $MEF$ se, e somente se, depois que $MEF$ terminar o processamento de $w$, $MEF$ esteja parada em um dos estados de aceitação do conjunto $A$ que define esta máquina.

Neste caso, dizemos que a $MEF$ aceita a string $w$.

Representação

Podemos representar uma $MEF$ com três notações diferentes:

1. Uma lista de elementos na $5-tupla$.
2. Uma tabela de transição.
3. Um diagrama de transição.

Caberá a você escolher a representação mais adequada para resolver o problema, ou a representação mais adequada para o seu entendimento do problema.

Algebricamente

$MEF=\{S, \Sigma, \delta, s_0, A\}$

$MEF=\{\{s_0, s_1, s_2\}, \{0,1\}\\ \{\delta_{(s_0,0)}=s_1, \\ \delta_{(s_0,1)}=s_0, \\ \delta_{(s_1,0)}=s_2, \\ \delta_{(s_1,1)}=s_0, \\ \delta_{(s_2,0)}=s_2, \\ \delta_{(s_2,1)}=s_0\}, s_0 = s_0, A=\{s_2\} \}$

Tabela de Transição

Existem pelo menos duas formas de se representar uma tabela de transição. Clique aqui para explicar que formas são estas e qual a diferença entre elas.

Diagrama de Transição

Existem várias formas de se representar o diagrama de transição. Nesta disciplina usaremos preferencialmente diagramas de transição.

Exemplo 1

Uma máquina de estados comum em ambientes de comunicação de dados é a máquina de detecção de paridade. Este tipo de máquina é capaz de detectar a paridade de um conjunto de bits, fornecidos como entrada de forma sequêncial.

Esta máquina conta o número de símbolos $1$ em uma string do alfabeto $\Sigma_{bin} =\{0,1\}$. Qualquer número para de $1$ é paridade par. Lembre-se nenhum $1$ é par. Coisas das regras de paridade.

Clique aqui para simular.

Exemplo 2

Cabe a você fazer uma máquina de paridade ímpar. Esta máquina irá receber uma linguagem definida pelo alfabeto $\Sigma_{bin} =\{0,1\}$ e reconhecer todos os strings cuja paridade seja ímpar. Ou seja, que o número de símbolos $1$ em uma determinada string seja ímpar

Lembre-se nenhum $1$ é par.

Clique aqui e envie o link da sua simulação para revisão

Pausa para o Gatinho

Teorema de Kleene

O Teorema de Kleene afirma que, para que uma linguagem seja considerada formal, ela deve ser definida por: expressões regulares e máquinas de estado finitas.

Isto significa que, com um pouco de álgebra é possível transformar uma em outra.

Hardware em Software?.

Expressões Regulares

Expressões regulares são uma notação algébrica, criada por Stephen Kleene, para representar uma determinada linguagem $L$ dado um alfabeto $\Sigma$ qualquer.

A nós interessam as linguagens regulares.

As Linguagens regulares são as linguagens formais que são fechadas nas operações de união, concatenação e fechamento de Kleene.

Fechamento - Closure

União

Dados os conjunto $L_1=\{a,b,c,eg,hf\}$ e $L_2=\{ea,af\}$ definimos a união entre estes conjuntos como:

$L_1 \cup L_2=\{a,b,c,eg,hf,ea,af\}$

Em algumas disciplinas usamos o símbolo $+$ para representar a união, se for o caso, teremos:

$L_1 + L_2=\{a,b,c,eg,hf,ea,af\}$

Em outros casos podemos usar uma barra vertical $|$ para representar a união.

Concatenação

Definimos a concatenação entre dois conjuntos $ L_1 \land L_2 $ como:

$ L= L_1 \cdot L_2 = \{ xy | x \in L_1, y \in L_2 \}$

Não é coincidência o uso do símbolo do produto escalar para representar a concatenação.

O produto escalar representa perfeitamente a operação de concatenação entre dois conjuntos.

Concatenação - Exemplos

As casas do Tabuleiro de Xadrez são nomeadas usando o conjunto resultado da operação entre $ L_1 \land L_2 $ desde que:

$ L_1 = \{ a, b, c, d, e, f, g, h \} \land L_2 = \{ 1, 2, 3, 4, 5, 6, 7, 8 \}$

Contudo, as casas jámais são nomeadas usando o conjunto:

$ L_1 = \{ 1, 2, 3, 4, 5, 6, 7, 8 \} \land L_2 = \{ a, b, c, d, e, f, g, h \}$

Você consegue explicar porquê?

No mundo do Xadrez temos $ L_1 = F \wedge L_2 = R$.

Fechamento de Kleene

A operação Kleene Star, ou Fechamento de Kleene, ou só fechamento (closure), pode ser definida, de forma intuitiva, como sendo o conjunto formado pela união de todas as formas possíveis de concatenar qualquer número de cópias das strings da linguagem $L$. Esta operação é representada por um asterisco $*$, de tal forma que:

$ L^* = \{ \varepsilon \} \cup L \cup L \cdot L \cup L \cdot L \cdot L \cup . . . \}$

Na prática fica mais claro!

Fechamento de Kleene - Exemplo

Considerando a linguagem $ L=\{ 0,1 \}$ teremos:

1. $L^0 = \{ \varepsilon \}$
2. $L^1=\{ 0,1 \}$
3. $L^2=L \cdot L^1 = \{ 00,01,10,11 \}$
4. $L^3= \{ 000,001,010,011,100,101,110,111\}$
5. $L^*=\{ \varepsilon,0, 1, 00, 01, 10,11, 000,001,010,… \}$

Representando a União da Concatenação de todos os strings possíveis

Um pouco de Formalidade

Formalmente uma expressão regular é uma string de um alfabeto $\Sigma^* \cup \{\emptyset, +, \cdot, *, (,)\}$ que pode ser construída segundo o seguinte conjunto de regras:

1. $\emptyset$ é uma expressão regular que indica o conjunto vazio.
2. Se $r$ e $s$ são duas expressões regulares que representam as linguagens $L(r)$ e $L(s)$ então, $r \cdot s$, geralmente representado por $rs$ será uma expressão regular.
3. Se $r$ e $s$ são duas expressões regulares que representam as linguagens $L(r)$ e $L(s)$ então, $r \cup s$, geralmente representado por $r+s$ será uma expressão regular.
4. Se $r$ é uma expressão regular representando a linguagem $L(r)$ então $r^*$ é uma expressão regular e irá representar a a operação Kleene Star, $L(r)^*$.
5. Nada mais será uma expressão regular.

Identidades das Expressões Regulares

considerando a linguagem $ L_1,L_2 e L_3 $

O uso destas entidades simplifica a análise das expressões regulares de forma algébrica.

Material de apoio

Você pode baixar o material de apoio clicando aqui