Análise Léxica:
Introdução, Tokens, Expressões
Regulares, Tabela de Símbolos
Prof. Alexandre Monteiro
Baseado em material cedido pelo Prof. Euclides Arcoverde
Recife
‹#›
Contatos

Prof. Guilherme Alexandre Monteiro Reinaldo

Apelido: Alexandre Cordel

E-mail/gtalk: [email protected]
[email protected]

Site: http://www.alexandrecordel.com.br/fbv

Celular: (81) 9801-1878
Agenda

Características das Linguagens de Alto Nível

Tipos de Especificação

Especificando a Sintaxe – Tokens

Especificando a Sintaxe – Gramática
3
Introdução

Para criar uma linguagem de programação, é
necessário
• Escolher as características desejadas
• Especificar a linguagem

A seguir:
• Características comuns nas linguagens de hoje
• Como especificar linguagens
4
Características das Linguagens de
Alto Nível
Relembrando...


Da linguagem de máquina às linguagens de alto nível...
A tendência hoje é de criar linguagens de nível cada vez
mais alto, ou seja, mais intuitivas
Mas como fazer isso? Que elementos tornam
as linguagens de alto nível?
6
Características

Controle de fluxo mais rígido
•Laços (como o while)
•Comandos de decisão (como o if-else)
•Sem comandos “goto”
•Execução Sequencial

Expressões em notações próximas da matemática
•2 + (temp * 10) / 3
7
Características

Tipos de dados e verificações de tipo
• Tipos numéricos (int, Integer, double, float),
strings, char, booblean, arrays, registros e tipos
abstratos dão ao programador maneiras intuitivas
de manipular dados binários da memória
• Cada tipo oferece operações especializadas
- Ex: adição (para inteiros) e acesso por índice (para arrays)
• Com isso, a linguagem pode impedir operações
inadequadas
- Ex: uma variável inteira não pode receber valor float
8
Características

Declarações
• As declarações preparam um nome (de variável,
função/método, classe, etc.) para ser usado
• Geralmente já identificam o tipo, para facilitar o
entendimento
• Regras de escopo vão indicar em que partes do
código o nome (que foi declarado) é válido
(variáveis globais ou locais)
9
Características

Desalocação automática de memória
• Quanto menos o programador precisar se preocupar
com a gestão de hardware, como a desalocação de
memória, melhor.
• Em C, as variáveis são desalocadas
automaticamente, mas o usuário tem que desalocar
manualmente endereços que ele alocar com a
função malloc().
• Em Java, toda posição de memória é desalocada
automaticamente pelo Garbage Collector, gc().
10
Características

Abstração (em geral)
• Tirar do usuário controle de detalhes irrelevantes
(ex: alocação de memória, tamanho do array), para
facilitar
• Separar “o que” deve ser feito de “como” é feito
- Ex: interfaces em Java

Uma boa regra é incorporar características de
abstração sempre
11
Linguagem de Alto Nível

Outros elementos podem ser criados, mas os que vimos
formam o estado atual da área
•Pode ser o ponto de partida para criar
outras linguagens de alto nível

Após escolher o que se deseja em uma linguagem é preciso
especificá-la...
12
Tipos de Especificação
O Que Especificar?

Uma linguagem apresenta duas partes que precisam ser
especificadas:
•Sintaxe
- Restrições de forma, ordem e escrita;
•Semântica
- Restrições contextuais, de sentido lógico.
14
Sintaxe



Diz respeito aos formatos dos programas
Restringe quais símbolos podem ser usados em cada
situação
Exemplos:
• Um declaração é um tipo seguindo de um nome e valor.
• Todo comando termina em “;”
• Todo “(“ precisa ter um “)” correspondente
-
int nota = 0
if ( nota > 7 ) {
print(“Aprovado!!!”);
} else {
print(“Reprovado!!!”);
}
15
Semântica



Diz respeito ao significado do programa
Especifica qual deve ser o comportamento dele
quando for compilado e executado
Exemplo para um comando while:
• Primeiro ele avalia a expressão de teste
• Se for positiva, executa o comando do corpo do while e
volta para a primeira etapa
• Se for negativa, passa para o próximo comando
16
Restrições Contextuais

Tratam o que não pode ser especificado na
sintaxe facilmente, pois depende do contexto
• Regras de escopo
• Regras de tipo

Também chamada “semântica estática”

Vamos considerá-la parte da semântica
17
Como Especificar?

Formalmente – Especificações formais
• São mais precisas
• Permitem um entendimento uniforme

Informalmente – Textos em linguagem natural
• Geralmente são muito ambíguas
• Diferentes leitores podem entender diferentemente
18
Na Prática

Sintaxe
• Especificada formalmente
• Formalismos vistos em Teoria da Computação

Semântica
• Especificações formais são muito pouco usadas
• Informalmente especificada
19
Na Disciplina

Seguiremos a prática comum:
•Sintaxe especificada formalmente
•Semântica especificada informalmente
20
Especificando a Sintaxe

Geralmente, feita em duas partes
•Tokens (ligada à 1ª etapa da compilação)
•Gramática (ligada à 2ª etapa da compilação)
21
Especificando a Sintaxe
Parte 1
Análise Léxica



A primeira fase da compilação
Recebe os caracteres do programa e os converte em um
fluxo de tokens
Tokens são unidades lógicas que representam um ou mais
caracteres

Cada palavra-chave é um token: Ex. begin, then, if, int

Cada idetificador é um token: Ex. a, soma, num, var1

Cada constante é um token: Ex. 123, 3.14, 1.2E3

Cada sinal é um token: Ex. >, <, =, >=, +, -, /, (
23
Análise Léxica



A análise léxica é, usualmente, invocada pelo parser cada
vez que um novo token é necessário
É uma fase que processa caracter por caracter.
(velocidade)
Possui 2 fases:
•Scanning: remove espaços e comentários
•Análise Léxica: agrupa os caracteres em
tokens
24
Análise Léxica

Como funciona a primeira etapa de um compilador
•Lê o fluxo de caracteres do código fonte
•Agrupa-os em sequências significativas
•Classifica essas sequências
25
Análise Léxica

Exemplo de código fonte
•pos = initial + rate * 60;

Exemplo de saída
• <ID, “pos”> <EQ> <ID,”initial”> <ADD> <ID,”rate”> <MUL> <NUM_INT,60> <PV>
26
Adiantando...


Lexema: sequência de caracteres com
significado interligado
Token: classificação dada ao lexema
• Geralmente retornado junto com o próprio lexema
ou outro atributo, como um ponteiro

Padrão: é uma descrição da forma que os
lexemas de um token podem tomar.
•Ex. sequência de caracteres que
formam palavra-chave como um token.
27
Exemplos
28
Especificando Tokens


Geralmente são especificados com expressões regulares
Cada token é associado a uma expressão regular que
representa seus lexemas válidos
•Padrão que representa várias palavras
(dizemos que as palavras “casam” com o
padrão)
29
Especificando Tokens

Expressões Regulares
• Formalismo utilizado para definir o conjunto de aceitação de
uma linguagem
• Principais operadores utilizados pelas ERs
Expressão
Reconhece
ε
A cadeia de caractedes vazia “”
“str”
A string “str”
A|B
Todas as cadeias reconhecidas por A ou B
A.B
Cadeias formadas pela concatenação das
cadeias reconhecidas por A e B
A+
Reconhece cadeias formadas pela concatenação
de um número finito de cadeias reconhecidas
30
por A
Especificando Tokens

Operadores derivados
Expressão
Equivale a
(A)
Agrupamento de operadores
A*
A+ | ε
A?
A|ε
[A-Z]
A | B | ... | Y | Z
A{N}
A . A . A ... } N vezes
A{M,N}
A . A . A ... } entre M e N vezes
AB
A.B
abc
String “abc”
31
Especificadores


Especificam o conjunto de caracteres a casar em uma posição.
Um metacaractere é um caractere ou sequência de caracteres
com significado especial em expressões regulares. Os
metacaracteres podem ser categorizados conforme seu uso.
32
Quantificadores

Definem o número permitido repetições da
expressão regular precedente.
33
Âncoras


Estabelecem posições de referência para o casamento
do restante da regex.
Note que estes metacaracteres não casam com
caracteres no texto, mas sim com posições antes,
depois ou entre os caracteres.
34
Agrupamentos

Definem ou grupos ou alternativas.
35
Especificando Tokens

Exercícios
•Defina expressões para expressar:
-
Número IP:
Números naturais (e inteiros):
Números de telefone (com DDD opcional):
Horas:
E-mails:
URLs:
Placa de Carro:
CEP:
36

Especificando Tokens
Exercícios
•Defina expressões para expressar:
-
Número IP: \d{3}.\d{3} .\d{3} .\d{3}
Números naturais (e inteiros): \d{n} ou [0-9]{n}
Números de telefone (com DDD opcional): \([0-9]{2}\).[0-9]{4}. [0-9]{4}
Horas: [012]\d:[0-5]\d
E-mails: [a-zA-Z0-9\._-]@[A-Za-z]+\\.[A-Za-z]+
Placa de Carro: [A-Z]{3}-\d{4}
CEP: \d{5}-\d{3} ou \d\d\d\d\d
URLs:
- Com http - (http|https)://([\w-]+\.)+[\w-]+(/[\w- ./?%&=]*)?
- Sem http - ([\w-]+\.)+[\w-]+(/[\w- ./?%&=]*)?
37
Especificando Tokens

Exercícios
•Testar as definições de ERs anteriores (em
Java)
•Pattern
•Matcher
38
Especificando Tokens

Definições regulares
• Define nomes para expressões regulares
• Uma definição pode usar definições anteriores

Exemplo
letra
→ [a-zA-Z]
dígito
→ [0-9]
letra_
→ (letra|_)
dois_dígt
→ [1-9][0-9]?
data
→ dois_dígt/dois_dígt/dois_dígt
39
Especificando Tokens

Tokens são, geralmente, especificados na forma de
definições definições regulares
40
Exemplo

Linguagem Expressao1
ABRE_PAR
→(
FECHA_PAR
→)
ATRIB
→=
ADD
→+
MULT
→*
DEF
→ def
ID
→ [_a-z][_a-z0-9]*
NUM_INT
→ [0-9][0-9]*
PT_VG
→ ;
WHITESPACE
→ [ \t\n\r]+
41
Especificando Tokens

A maioria das linguagens definem tokens para
os seguintes elementos:
• Tokens para os operadores, em grupo ou
separadamente
• Um só token para todos os identificadores (nomes)
• Tokens diferentes para cada palavra-chave
• Tokens diferentes para constantes numéricas de
tipos diferentes e para as strings literais (int,
double, float e char, String)
• Tokens para cada símbolo de pontuação (;)
42
Alguns Tokens

Tokens para operadores podem ser definidos
individualmente ou agrupados
•Fica a critério do criador da linguagem

Exemplo 1
ADD → +
MUL → *
DIV → /

Exemplo 2
OP → (+|*|/)
43
Alguns Tokens

Identificadores
•Nomes que podem ser atribuídos a variáveis,
funções, classes, etc.
•Usa-se um único token para todos os casos
44
Alguns Tokens

Palavras-chave
•Parecem identificadores, mas têm
significados especiais
•Exemplos de Java: “class”, “int”, “float”,
“return”
•Melhor considerar como tokens diferentes
45
Tokens Especiais

Palavras reservadas
•São palavras-chaves que não podem ser
usadas como identificadores
- Neste caso, não é permitido usar palavras-chave para dar nome a
entidades da linguagem (variáveis, etc.)
•Considerar todas as palavras-chaves como
palavras reservadas é muito comum
- Facilita a construção do compilador
46
Tokens Especiais

Exemplo de PL/I, onde palavras-chave não são palavras
reservadas
IF (THEN) THEN
THEN = ELSE;
ELSE
ELSE = THEN;
47
Tokens Especiais

Espaços em branco
• Caracteres que devem ser ignorados
- Na verdade, é um “não-token”
• Exemplo de definição
WHITESPACE
→ [ \t\n\r]+
• A primeira etapa do compilador simplesmente não
retorna token para esse padrão
48
Especificando a Sintaxe
Parte 2
Adiantando...

Como funciona a segunda etapa de um compilador
•Lê a sequência de tokens
•Monta uma organização lógica deles na
forma de árvore sintática
50
Árvore sintática

Exemplo de árvore sintática
DECLARACAO
TIPO
INT

ID
PTO_VIRG
CHAR
Como definir formalmente essa estrutura?
51
Especificando Sintaxe

Pensar na organização dos tokens em frases
• Uma declaração é um tipo seguido de um
identificador seguido de ponto-e-vírgula
• Um tipo pode ser os tokens INT ou CHAR

“Regras de formação”
declaração
-> tipo
tipo
-> INT
tipo
-> CHAR
ID
;
52
Especificando Sintaxe

Notação quando há mais de uma produção
para o mesmo conceito:
expressao -> CTE_INT
expressao -> ID
expressao -> expressao + expressao

Ou simplificando...
expressao -> CTE_INT
| ID
| expressao + expressao
53
Especificando Sintaxe

São usadas gramáticas livres de contexto, que possuem
quatro elementos:
•Símbolos terminais
•Símbolos não-terminais
•Símbolo inicial
•Produções
54
Especificando Sintaxe

Elementos das gramáticas livres de contexto:
• Símbolos terminais:
- Símbolos assumidos como atômicos, indivisíveis
- Assumiremos os tokens como terminais
• Símbolos não-terminais:
- Auxiliares usados para organizar os tokens em “frases”
55
Especificando Sintaxe

Elementos das gramáticas livres de contexto:
• Símbolo inicial:
- Não-terminal que será a raiz (topo) da árvore
- Geralmente é um não-terminal chamado programa
• Produções:
- São as regras de formação
- Definem as “frases” de símbolos válidas
56
Especificando Sintaxe

Diferentes notações para as produções
•BNF (Backus-Naur Form)
•EBNF (Extended BNF)
57
BNF (Backus-Naur Form)

Não-terminais entre “<“ e “>”

Terminais entre aspas ou sem delimitadores

Usa “::=“ ao invés de “→”
<bloco>
::= BEGIN <comando-l> END
<comando-l> ::= <comando>
| <comando> <comando-l>
<comando>
::= ...
58
EBNF (Extended BNF)

Existem diversas variações...
• Numa boa especificação, devem vir anotações sobre
quais as extensões assumidas

A característica mais comum é que nãoterminais aparecem sem delimitador
bloco
= BEGIN comando* END
comando
= ...
59
EBNF (Extended BNF)

Outras características típicas
• Chaves ou “*” significam repetições
• Colchetes ou “?” significam opcional (zero ou um)
• Oferecer expressões regulares, permitindo que os
tokens sejam especificados como não-terminais
Identificador = [a-zA-Z]+
Igual
= “=“
Comando
= Identificador Igual Expresssao
60
Exemplo

Linguagem Expressao1
•Uma linguagem simples para criar
expressões
•Apenas dois comandos:
- Definir um nome para alguma expressão (constante)
- Avaliar uma expressão
61
Exemplo

Linguagem Expressao1
<programa> ::= <comando>*
<comando> ::= <definicao> ; | <expr> ;
<definicao> ::= def ID = <expr>
<expr> ::= <expr> + <expr>
| <expr> * <expr>
| ( <expr> )
| NUM
| ID
62
Exemplo

Linguagem Expressao1 (com os tokens
explícitos)
<programa> ::= <comando>*
<comando> ::= <definicao> PT_VG
| <expr> PT_VG
<definicao> ::= DEF ID EQ <expr>
<expr> ::=
|
|
|
|
<expr> ADD <expr>
<expr> MUL <expr>
ABRE_PAR <expr> FECHA_PAR
NUM
ID
63
Especificando Sintaxe


As gramáticas livres de contexto podem representar tudo
que expressões regulares representam (e algo mais)
Por isso, às vezes, a definição completa da sintaxe da
linguagem (incluindo tokens) é feita usando apenas uma
gramática em EBNF.
64
Bibliografia

AHO, A., LAM, M. S., SETHI, R., ULLMAN, J. D.,
Compiladores: princípios, técnicas e ferramentas. Ed.
Addison Wesley. 2a Edição, 2008 (Capítulo 2)
65
Análise Léxica:
Introdução, Tokens, Expressões
Regulares, Tabela de Símbolos
Prof. Alexandre Monteiro
Baseado em material cedido pelo Prof. Euclides Arcoverde
Recife
‹#›