Análise Léxica: Introdução, Tokens, Expressões Regulares, Tabela de Símbolos

1

Análise Léxica:Introdução, Tokens,

Expressões Regulares, Tabela de SímbolosProf. Alexandre Monteiro

Baseado em material cedido pelo Prof. Euclides Arcoverde

Recife

Contatos

Prof. Guilherme Alexandre Monteiro Reinaldo

Apelido: Alexandre Cordel

E-mail/gtalk: alexandrecordel@gmail.com

greinaldo@fbv.edu.br

Site: http://www.alexandrecordel.com.br/fbv

Celular: (81) 9801-1878

3

Agenda

Características das Linguagens de Alto Nível

Tipos de Especificação

Especificando a Sintaxe – Tokens

Especificando a Sintaxe – Gramática

4

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

Características das Linguagens de Alto Nível

6

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?

7

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

8

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

9

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)

10

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().

11

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

12

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...

Tipos de Especificação

14

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.

15

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!!!”); }

16

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

17

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

18

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

19

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

20

Na Disciplina

Seguiremos a prática comum:

• Sintaxe especificada formalmente• Semântica especificada informalmente

21

Especificando a Sintaxe

Geralmente, feita em duas partes

• Tokens (ligada à 1ª etapa da compilação)

• Gramática (ligada à 2ª etapa da compilação)

Especificando a Sintaxe

Parte 1

23

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. >, <, =, >=, +, -, /, (

24

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

25

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

26

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>

27

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.

28

Exemplos

29

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)

30

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 por A

31

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”

32

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.

33

Quantificadores

Definem o número permitido repetições da expressão regular precedente.

34

Â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.

35

Agrupamentos

Definem ou grupos ou alternativas.

36

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:

37

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- ./?%&=]*)?

38

Especificando Tokens

Exercícios

• Testar as definições de ERs anteriores (em Java)

• Pattern• Matcher

39

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

40

Especificando Tokens

Tokens são, geralmente, especificados na forma de definições definições regulares

41

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]+

42

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 (;)

43

Alguns Tokens

Tokens para operadores podem ser definidos individualmente ou agrupados

• Fica a critério do criador da linguagem

Exemplo 1

Exemplo 2

ADD → +

MUL → *

DIV → /

OP → (+|*|/)

44

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

45

Alguns Tokens

Palavras-chave

• Parecem identificadores, mas têm significados especiais

• Exemplos de Java: “class”, “int”, “float”, “return”

• Melhor considerar como tokens diferentes

46

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

47

Tokens Especiais

Exemplo de PL/I, onde palavras-chave não são palavras reservadas

IF (THEN) THEN

THEN = ELSE;

ELSE

ELSE = THEN;

48

Tokens Especiais

Espaços em branco• Caracteres que devem ser ignorados

- Na verdade, é um “não-token”

• Exemplo de definição

• A primeira etapa do compilador simplesmente não retorna token para esse padrão

WHITESPACE → [ \t\n\r]+

Especificando a Sintaxe

Parte 2

50

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

51

Árvore sintática

Exemplo de árvore sintática

Como definir formalmente essa estrutura?

DECLARACAO

PTO_VIRGTIPO ID

INT CHAR

52

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 ID ;

tipo -> INT

tipo -> CHAR

53

Especificando Sintaxe

Notação quando há mais de uma produção para o mesmo conceito:

Ou simplificando...

expressao -> CTE_INT

expressao -> ID

expressao -> expressao + expressao

expressao -> CTE_INT | ID | expressao + expressao

54

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

55

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”

56

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

57

Especificando Sintaxe

Diferentes notações para as produções

• BNF (Backus-Naur Form)

• EBNF (Extended BNF)

58

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> ::= ...

59

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ão-terminais aparecem sem delimitador

bloco = BEGIN comando* END

comando = ...

60

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

61

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

62

Exemplo

Linguagem Expressao1

<programa> ::= <comando>*

<comando> ::= <definicao> ; | <expr> ;

<definicao> ::= def ID = <expr>

<expr> ::= <expr> + <expr> | <expr> * <expr> | ( <expr> ) | NUM | ID

63

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

64

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.

65

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)

66

Análise Léxica:Introdução, Tokens,

Expressões Regulares, Tabela de SímbolosProf. Alexandre Monteiro

Baseado em material cedido pelo Prof. Euclides Arcoverde

Recife