SEMANA 2

Prévia do material em texto

LINGUAGENS E 
COMPILADORES
Conceitos de Linguagens de 
Programação e Análise Léxica
LINGUAGENS E COMPILADORES
Agenda:
1. Conceitos de Linguagens de Programação
2. Análise Léxica
3. Terminologia Básica e Simbologia
4. Da Expressão Regular ao Autômato
5. Implementação de DFA
6. Gerador de Analisadores Léxicos
Obs.:
a. Leia a apresentação de introdução da disciplina.
b. Veja as apresentações sobre Linguagens de Programação 
deste módulo
Prof. Dr. Ricardo Luis de Azevedo da Rocha
1. CONCEITOS DE LINGUAGENS DE 
PROGRAMAÇÃO
•Aumento da capacidade de expressar ideias
• Limitações de uma linguagem
• Tipos de estrutura de dados
• Tipos de estrutura de controle
• Tipos de abstrações que podem ser utilizadas
• Assim, as formas de algoritmos também são 
limitadas
• Conhecimento de recursos de linguagens de 
programação reduz essas limitações
• Programadores aumentam seu poder de expressão 
aprendendo novas construções de linguagens
DEFINIÇÃO DE LINGUAGEM DE 
PROGRAMAÇÃO
•Sintática: Uma linguagem de 
programação é uma notação utilizada 
pelo programador para especificar ações 
a serem executadas por um computador
•Semântica: Uma linguagem de 
programação compreende um conjunto 
de conceitos que um programador usa 
para resolver problemas de programação
DOMÍNIOS DE PROGRAMAÇÃO
•Aplicações científicas
•Aplicações comerciais
• Inteligência artificial
•Sistemas básicos
•Aplicações Internet
DOMÍNIOS DE PROGRAMAÇÃO
aplicações
usuários
desenvolvedores
GUIS,
portabilidade
...
expressiva,
eficiente,
IDEs expressiva ,
simples
ARQUITETURA DE VON NEUMANN
COMPUTADOR E LINGUAGENS
•Um computador pode ser representado por:
• uma máquina virtual, capaz de executar operações mais abstratas 
(representadas através de uma linguagem de programação) 
• uma máquina real, capaz de executar um determinado conjunto de 
operações concretas (expressas em linguagem de máquina)
L1: máquina assembler
L2 máquina C
L3 máquina Pascal 
L0: máquina real
LINGUAGENS E MÁQUINAS
• Cada máquina representa um conjunto integrado 
de estruturas de dados e algoritmos
• Cada máquina é capaz de armazenar e executar 
programas em uma linguagem de programação 
L1, L2, L3,...Ln. 
mapeamento
L1
L2
L3
Ln
máquina
vitual
L0
DEFINIÇÃO
•Compilador: Um programa de computador que 
traduz código escrito em uma determinada 
linguagem (código-fonte) em código escrito em 
outra linguagem (linguagem-objeto).
Exemplos:
• Traduzir de C++ para C
• Traduzir de Java para JVM
• Traduzir de C para C (Por que?) Para tornar o código mais
eficiente, menor, mais rápido, ou mesmo medir
desempenho).
DEFINIÇÃO
•Compilador: Um programa de computador que 
traduz código escrito em uma determinada 
linguagem (código-fonte) em código escrito em 
outra linguagem (linguagem-objeto).
Exemplos:
• Traduzir de C++ para C
• Traduzir de Java para JVM
• Traduzir de C para C (Por que? Para tornar o 
código mais eficiente, menor, mais rápido, 
ou mesmo medir desempenho).
ESTRUTURA LÓGICA
Analisador
Léxico
Analisador
Sintático
Analisador
Semântico
Código
fonte Tokens Árvore
sintática
Árv. sint.
e tabela 
símbolos
Identifica palavras
Operadores, números, 
etc.
Identifica estrutura
Expressões, declarações, 
etc.
Identifica Tipos, etc.
Gerador de
Código Int.
Repres. 
Interna
Gera representação interna 
através da árvore sintática
Otimizador
de Código
Repres.
Interna
Transforma 
representação interna, 
modifica código 
(desempenho)
Gerador
de Código
Código
Objeto
Gera código objeto
Traduz representação 
interna para linguagem 
objeto (ex. Assembly)
FRONT-END E BACK-END
2. ANÁLISE LÉXICA
•Léxico
• Conjunto de palavras de um determinado idioma
• Conjunto de objetos de uma determinada linguagem
•Analisador Léxico
• Recebe como entrada um string e retorna 
tokens
• Retira símbolos sem valor sintático/ 
semântico
TokensNome de 
variáveis Números Palavras-chave
etc.
Slide extraído de Clauirton Siebra – UFPB “Construção de Compiladores”
DEFINIÇÃO 
•Entrada: Arquivo texto contendo os strings segundo 
alguma codificação (ASCII, UTF-8, etc.).
•Saída: Tokens - representação dos lexemas (objetos 
léxicos da linguagem, ex.: IF, ELSE, etc.) sob a forma 
de estrutura de dadosclasse, valor.
• classe: indica a classificação que pode ser 
número, identificador, palavra-reservada, 
etc.
• valor: o valor do token, por exemplo se for 
número seu valor numérico – “12”  12.
DEFINIÇÃO
•Os tokens usualmente são definidos pelo seu lexema 
(string ou sequência de caracteres que compõem um 
único token) e atributos adicionais.
•Os tokens podem ser entregues ao parser como tuplas
na forma <a, b,..., n > assim, a entrada:
a = b + 3
• poderia gerar as tuplas <classe, valor>:
<id, a> <=,> <id, b> <+,> <num, 3>
• note “a” e “b” podem ser ponteiros 
para outra estrutura de dados (tabela de 
símbolos) e que alguns tokens não 
necessitam atributos adicionais.
Slide modificado de Maurício Rodrigues de Morais – “Compiladores”
OBJETIVO 
•Remoção de espaços em branco e 
comentários.
• Identificação de constantes.
• Identificação de palavras-reservadas 
(construções da linguagem).
•Reconhecimento dos identificadores.
•Separação entre o analisador sintático 
e a representação da entrada.
Slide extraído de Maurício Rodrigues de Morais – “Compiladores”
CLASSES DE TOKENS
•As linguagens de programação usualmente 
distinguem certas classes ou tipos de tokens:
• palavras-reservadas
• operadores
• identificadores
• números
• literais
• símbolos de pontuação
Slide extraído de Maurício Rodrigues de Morais – “Compiladores”
ATRIBUTOS DOS TOKENS
•Quando um lexema é reconhecido por um 
padrão, o analisador léxico deve 
providenciar outras informações adicionais 
(atributos) conforme o padrão.
lexema
token
classe
atributos
Analisador
Léxico
Analisador
Gramatical
Geração de
Código
Slide modificado de Maurício Rodrigues de Morais – “Compiladores”
Token Lexemas Exemplo Descrição informal do padrão
if if if
relação <, <=, =, >, >= < ou <= ou = ou > ou >=
id pi, contador, varSoma Letra seguida por letras ou dígitos
num 3.1416, 0, 6.02E23 Qualquer constante numérica
string “string qualquer” Quaisquer caracteres entre aspas, exceto 
aspas
Slide extraído de Guilherme Amaral Avelino – “Compiladores”
EXEMPLOS
INTERAÇÃO ENTRE LÉXICO E 
SINTÁTICO
•Um analisador léxico interage com a entrada e com o 
parser (analisador sintático ou gramatical):
Entrada
Analisador
Léxico
Analisador
Sintático
Leitura de
caractere
Devolução
de caractere
Entrega de 
tokens e seus 
atributos
Tabela de
Símbolos
Pedido 
de token
Inserção ou 
Consulta
Consulta
Slide extraído de Maurício Rodrigues de Morais – “Compiladores”
INFORMAÇÃO NECESSÁRIA:
•Linguagens regulares 
• “Constituem um conjunto de linguagens que 
podem ser geradas por gramáticas regulares, 
reconhecidas por autômatos finitos e 
facilmente descritas por expressões simples, 
chamadas expressões regulares”
Slide extraído de Clauirton Siebra – UFPB “Construção de Compiladores”
3. TERMINOLOGIA BÁSICA E SIMBOLOGIA
• Linguagem: Conjunto (coleção) de cadeias de símbolos
• Cadeias: Sentenças (ou palavras, strings) da linguagem
• Símbolos: Elementos de um alfabeto que justapostos formam as 
sentenças (chamados de tokens na linguagem léxica)
• Alfabeto: Conjunto finito (em nosso caso de símbolos 
codificados)
• Formas de representação de linguagens infinitas:
• Conjunto de leis de formação das cadeias 
(gramática)
• Conjunto de regras de aceitação das cadeias 
(reconhecedores)
• Conjunto de funções (funcional)
• Derivação: utilizar leis de formação para obter 
uma sentença
EXPRESSÕESREGULARES
•Constituída a partir de regras de definição aplicadas a 
um conjunto de expressões regulares mais simples:
•  é uma expressão regular (contém a cadeia vazia)
• Se a é um símbolo do alfabeto (), a é uma expressão 
regular
• Supondo-se que r e s são expressões 
regulares que denotam as linguagens 
L(r) e L(s), tem-se:
• (r) | (s) é expressão regular [L(r)  L(s)]
• (r) (s) é expressão regular [L(r) L(s)]
• (r)* é expressão regular [(L(r))*]
• (r) é expressão regular [L(r)]
•Qual a linguagem de ?
EXPRESSÕES REGULARES
•Reescrever a expressão regular até se obter 
apenas uma sequência de letras (string)
Exemplo
(0 | 1)*”.”(0 | 1)*
(0 | 1)(0 | 1)*”.”(0 | 1)*
1(0 | 1)*”.”(0 | 1)*
1”.”(0 | 1)*
1”.”(0 | 1)(0 | 1)*
1”.”(0 | 1)
1”.”0
Regras gerais
1) r1| r2 → r1
2) r1| r2 → r2
3) r* → rr*
4) r* → 
Slide extraído de João M. P. Cardoso – Universidade do Algarve “Compiladores”
RECONHECEDORES
• Alternativa para a definição de uma linguagem, na qual utiliza-se 
dispositivos aceitadores denominados reconhecedores da 
linguagem.
• Um reconhecedor é dispositivo conceitual composto de texto de 
entrada (cadeia de símbolos), cursor de leitura, controle (máquina 
finita de estados) que pode usar uma memória auxiliar
• Há dois tipos de reconhecedores: determinísticos 
(um único movimento para qualquer configuração) 
e não-determinísticos (conjunto de movimentos 
possíveis para cada configuração)
• Um reconhecedor pode definir uma linguagem 
(quando só aceita cadeias desta linguagem)
• Para linguagens regulares o reconhecedor 
empregado é o autômato de estados finitos 
(DFA, ou NFA)
Slide extraído de João M. P. Cardoso – Universidade do Algarve “Compiladores”
AUTÔMATOS FINITOS
•Exemplo Estado de início
Estado de aceitação
1
0
1
0
(0 | 1)* “.”(0 | 1)*
Slide extraído de João M. P. Cardoso – Universidade do Algarve “Compiladores”
NFA × DFA
•DFA
• Sem transições 
•No máximo uma transição de cada estado para cada
símbolo
•NFA – nenhuma destas restrições
a
a
a
b
OK NOT
OK
Slide extraído de João M. P. Cardoso – Universidade do Algarve “Compiladores”
4. DA EXPRESSÃO REGULAR 
AO AUTÔMATO
Slide extraído de João M. P. Cardoso – Universidade do Algarve “Compiladores”
REGRAS DE CONVERSÃO
r1 r2
r1.r2 


r1
r2


r1 | r2
r 


r*
a a
 
Slide extraído de João M. P. Cardoso – Universidade do Algarve “Compiladores”
NFA PARA DFA •Exemplo: (0 | 1)*.(0|1)*

1 2
3
4
5
6
1
0
7


8



9 10
11
12
13
14
1
0
15


16


.
Slide extraído de João M. P. Cardoso – Universidade do Algarve “Compiladores”
NFA PARA DFA •Exemplo: (0 | 1)*.(0|1)*
1,2,3,4,8
5,7,2,3,4,8
6,7,2,3,4,8
9,10,11,12,16
13,15,10,11,12,16
14,15,10,11,12,16
1
0
1
0
1
0
1
0
00
1 1
Slide extraído de João M. P. Cardoso – Universidade do Algarve “Compiladores”
EXEMPLO DE CATEGORIAS 
LEXICAIS
•Palavra_chave_if = if
•Palavra_chave_while = while
•Operador = +|-|*|/
• Inteiro = [0-9] [0-9]*
•Float = [0-9]*. [0-9]*
• Identificador = [a-z]([a-z]|[0-9])*
•Na análise sintática utilizaremos 
estas categorias
Slide extraído de João M. P. Cardoso – Universidade do Algarve “Compiladores”
INTERPRETADOR DO DFA 
State = DFA initial state;
inputChar = getchar();
While(inputChar) {
State = trans(State, inputChar]);
inputChar = getchar();
}
If(State é um estado de aceitação) 
realizar ação relativa ao estado State (reconheceu String)
Else 
realizar outra ação
Algoritmo do Interpretador
Slide extraído de João M. P. Cardoso – Universidade do Algarve “Compiladores”
5. IMPLEMENTAÇÃO DO DFA
• Implementar a tabela de transições de 
estados com um array bidimensional
Slide extraído de João M. P. Cardoso – Universidade do Algarve “Compiladores”
1
2
3
4
5
6
1
0
1
0
1
0
1
0
00
1 1
5. IMPLEMENTAÇÃO DO DFA
• Implementar a tabela de transições de 
estados com um array bidimensional
Slide extraído de João M. P. Cardoso – Universidade do Algarve “Compiladores”
Estado 
Atual
Próximo Estado
“0” “1” “.”
0 0 0 0
1 3 2 4
2 3 2 4
3 3 2 4
4 6 5 0
5 6 5 0
6 6 5 0
6. GERADOR DE ANALISADORES 
LÉXICOS
• Auxiliam na construção de analisadores Léxicos
• Utilizam expressões regulares para descrever tokens
• Permite a combinação da identificação de padrões com execução de 
ações
• Compilador e linguagem Lex
• Ex:
• Flex – versão GNU do lex para C. 
http://www.monmouth.com/~wstreett/lex-yacc/lex-yacc.html
• Jlex – versão Java com pequena diferença na sintaxe de entrada.
http://www.cs.princeton.edu/~appel/modern/java/JLex/
• CSLex – versão C#, derivada do Jlex.
http://www.cybercom.net/~zbrad/DotNet/Lex
Slide extraído de Guilherme Amaral Avelino – “Compiladores”
LINGUAGENS E 
COMPILADORES
Conceitos de Linguagens de 
Programação e Análise Léxica