A4_LP_conceitosSintaxe

Prévia do material em texto

Linguagens de Programação: 
Módulo 5 
Organização de LP´s: Sintaxe, 
Semântica e Pragmática 
Parte 0 - Conceitos Básicos 
Métodos de Implementação 
 
 
 Qualquer programa precisa ser convertido para linguagem 
de máquina para ser executado; 
 Tradutor descreve como uma entrada em código-fonte será 
traduzido em código de máquina; 
 Basicamente três métodos: 
 Compilação 
 Interpretação pura 
 Híbrido 
Métodos de Implementação 
 
 
 Compilação (Cobol, C, Pascal) 
 Transformação de programas de alto nível em 
código de máquina; 
 Requer apenas o executável para execução; 
 Execução mais rápida do programa; 
 Boa parte das verificações de erro já pode ser feita durante a 
tradução; 
 Nada precisa ser traduzido 
 Transformação lenta; 
 Falta de portabilidade 
 
 
 
 
 
 Compilação 
 
 
 Interpretação Pura 
 Não existe transformação, os programas são 
interpretados 
 Execução de 10 a 100 vezes mais lenta que 
programas compilados 
 Ocupa mais espaço de memória: tabela de 
símbolos tem que ser carregada na interpretação; 
 Ex.: .BAT, .SH 
 
 
 Interpretação Híbrida 
 Meio termo entre compilados e interpretados 
 Tradução de programas em linguagem de alto 
nível em linguagem intermediária 
 Visa combinar execução eficiente com 
portabilidade 
 Custo de transformação baixo 
 Tempo de execução razoável a muito bom 
 Ex.: JAVA 
 
 
 Interpretação Híbrida 
Um Modelo de Implementação 
Código fonte 
Árvore 
de parse e 
tabela de 
símbolos 
Translação ou parsing 
Sintaxe 
Código objeto 
intermediário 
Geração 
de código 
Semântica 
Código objeto 
binário 
Ligação ou linking 
Pragmática 
Interpretador 
Semântica 
Hardware 
Atribuições de uma LP 
• Reconhecer programas legais e ilegais 
• Gerar código correto 
• Gerenciar armazenamento de código e variáveis 
• Informar o usuário sobre problemas com o código 
LP em Duas Partes 
Código fonte 
Árvore 
de parsing 
e tabela de 
símbolos 
Código objeto 
intermediário 
Front end (sintaxe) 
Back end (semântica e 
geração de codigo) 
Representação 
Intermediária 
Representação 
Final RI RF 
Translação 
ou parsing 
Geração 
de código 
Parte 1 - Front end e Sintaxe 
Definições Básicas em Sintaxe (1) 
Alfabeto ou vocabulário é um conjunto de símbolos usados em 
uma linguagem. Representado pela letra grega  
 
1 = {0,1} 2= {a..z, A..Z, 0..9} 
 
String, sentença, ou palavra é uma seqüência de zero ou mais 
símbolos de um vocabulário. 
 
Ex. 00001001011 é uma sentença do vocabulário 1 
Definições Básicas em Sintaxe (2) 
Dicionário é o conjunto de todas as sentenças que eu posso 
formar sobre um vocabulário. Representado por * 
 
Linguagem L definida sobre  é qualquer subconjunto de * 
Definindo uma linguagem 
sobre um alfabeto  
Existem muitos meios para se definir uma linguagem sobre um 
alfabeto. O mais básico é enumerar todas as sentenças possíveis 
de uma linguagem. Por exemplo 
 
  = {0,1}, L = {, 0, 1, 01, 10, 111} 
Definindo a Sintaxe de uma 
Linguagem de Programação 
Evidentemente o método de enumeração de sentenças não é 
viável para uma linguagem de programação. Normalmente 
combina-se dois métodos para definir o que é aceitável numa LP. 
 
Um método é usado para analisar lexicamente a seqüência de 
caracteres o código fonte e identificar quais são os bastões 
(tokens) existentes naquele código. Ex.: palavras chaves, 
operadores, variáveis, etc. 
 
Outro método é usado para checar se os bastões formam uma 
gramática aceitável na LP, isto é chamado de parsing. 
Processamento Sintático em LPs 
Desta forma, compiladores e interpretadores usam uma 
combinação de processadores de linguagem regulares e 
processadores de gramáticas para produzir uma tabela de 
símbolos e uma árvore de parsing. 
 
Estas duas estruturas serão então usadas para se produzir 
código intermediário “interpretável” (como em Java) ou 
“linkável” em código objeto (como em C). 
Front end 
scanner ou 
analisador léxico 
parser 
Erros 
Código 
fonte 
RI 
tokens 
Desta forma o front end de uma LP é normalmente 
composto de dois módulos. 
Funções do Front End 
• Reconhecer se o código fonte é legal 
• Reportar erros de sintaxe 
• Produzir RI (representação intermediária) 
• Criar mapeamento preliminar de armazenamento 
• Arrumar o código para o back end 
Parte 1.1 - Análise Léxica 
Analisador Léxico 
scanner ou 
analisador léxico 
parser 
Erros 
Código 
fonte 
RI 
tokens 
Função do Analisador Léxico 
• Mapear caracteres em tokens eliminando caracteres inúteis 
tais como tabs, blanks, comentários, etc. Por exemplo: 
 
A expressão “x = x + y;” 
torna-se, 
 <id,x> = <id,x> + <id,y>; 
 
Tokens são a unidade básica da sintaxe. Exemplos típicos de 
tokens são: literal-número, identificador, +, -, /, 
do, end 
token 
Analisador Léxico 
Tokens seguem para o parser 
Métodos para Definição de 
Analisadores Léxicos 
Analisadores léxicos (scanners) normalmente usam métodos que 
enumeram os padrões de caracteres aceitáveis pela LP. Entre 
estes métodos estão as expressões regulares. 
Expressões Regulares (1) 
Método de definição de uma linguagem que enumera todos os 
padrões legais aceitos na linguagem, exemplo: 
 
Concatenação de x com y: xy 
Potência xxx ... x , n vezes: xn 
Sentença vazia, : x0 
Fechamento de Kleene: 
 x* = {x0, x1, x2, x3, ...} 
 x+ = {x1, x2, x3, x4, ...}, fechamento positivo 
Expressões Regulares (2) 
Exemplo 1 
 
Representando a linguagem L de todas as sentenças em {a,b} 
onde todos os as sempre precedem os bs 
 
L = {w, w = a*b*} 
Expressões Regulares (3) 
Continuação: 
 
Opção de x ou y: x | y 
Seleção (não padronizada) : [ x y ] 
Intervalo de a até g: a-g 
Qualquer caractere: . 
Começo de linha: ^ à esquerda 
Fim de linha: $ à direita 
Caracteres de controle: \, escape 
 ( ), agrupamento 
Expressões Regulares (4) 
Exemplo 2: 
 
Nomes válidos de variáveis em uma LP: 
 {w, w = [a-zA-Z][a-zA-Z0-9]*} 
 
Exemplo 3: 
 
Conjunto de todas as sentenças no alfabeto {a, b, c} em que 
todos os as sempre precedem os bs e os cs vão em qualquer 
lugar: 
 L = {w, w = (a|c)*(b|c)*} 
Expressões Regulares (5) 
Exemplo “quase” real de utilização de expressões regulares: 
números válidos em uma LP: 
 
digito  [0-9] 
inteiro  ( \+ | \- |  )(0|[1-9]digito*) 
decimal  inteiro \. (digito*) 
real  (inteiro | decimal) E (\+ | \- |  ) digito* 
Uso de Linguagem Regulares 
Scanners (analisadores léxicos) transformam linguagens 
regulares em máquinas de estados finitos que transformam o 
código fonte em uma seqüência de tokens ou bastões. Por 
exemplo: 
if (indice < 0) { 
 indice := indice +1; 
} 
<if> <beginExpr> <id 23> <opLessThan> <literal 0> <endExpr> 
<then> 
<beginBlock> 
 <beginStmt> 
 <id 23> <attrb> <id 23> <opPlus> <literal 1> 
 <endStmt> 
<endBlock> 
Alguns problemas de sintaxe (1) 
PL/I não tem palavra reservada: 
 if then then then = else; 
 else else = then; 
 
FORTRAN e ALGOL ignoravam os blanks, e reconheciam 
caracteres ambíguos: 
 
 integerVA 
 do 10 i = 1,25,2 
 do 10 i = 1.25,2 
derrubou uma sonda espacial 
Alguns problemas de sintaxe (2) 
FORTRAN66 e as primeiras versões de C tinham um 
fechamento transitivo limitadoque limitava o número de 
caracteres em nomes de variáveis a 6 caracteres. 
 
As linguagens de hoje ainda têm problemas para tratar 
caracteres especiais dentro de uma string. Por exemplo: 
newline, tab, quote, delimitadores de comentários, etc. 
Limites de linguagens regulares 
• Nem todas as linguagens são regulares. Neste caso, não se 
pode construir máquinas de estados finitos (DFA) para 
reconhecer este tipo de linguagem. Por exemplo: 
 
 L = {pkqk} 
 
DFAs não conseguem contar! 
Parte 1.2 - Gramáticas Livres de 
Contexto e Parsers 
Parser 
scanner ou 
analisador léxico 
parser 
Erros 
Código 
fonte 
RI 
tokens 
Função do Parser 
• Reconhecer a sintaxe livre de contexto formada pelos 
tokens produzidos pelo analisador léxico para construir as 
representações intermediárias para geração de código objeto. 
• Produzir mensagens de erros úteis ao usuário e quando 
possível corrigir estes erros. 
 
Geradores de parsers podem automatizar boa parte deste 
trabalho. => YACC, Cup, JavaCC 
Gramáticas Generativas 
Sintaxe livre de contexto são interpretadas por gramáticas 
generativas que determinam as palavras legais de uma 
linguagem através de regras de produção, por exemplo 
Gramáticas BNF (Backus Naur Form) 
 
G = <, N, P, S>, onde: 
 
 é um conjunto de símbolos terminais (o alfabeto) 
N é um conjunto de símbolos não terminais 
P é um conjunto de regras de produção 
S é o símbolo de partida 
Gramáticas BNF (1) 
Regras de produção são regras da forma A::=  , onde A é um 
símbolo não terminal e  é uma seqüência de símbolos 
terminais e não terminais. 
 
 
Exemplo 1: regras de produção 
 
<corpo> ::= BEGIN <declaração> END 
<declaração> ::= <palavra> ; <declaração> 
<declaração> ::= <palavra> 
Gramáticas BNF (2) 
Exemplo 2: Linguagem com alfabeto {a,b} onde os as sempre 
precedem os bs . 
 
G = <, N, P, S>, onde: 
 = {a,b}, alfabeto 
N = {b}, conjunto de símbolos não terminais 
P = {b ::= ab, b ::= bb, b ::= }, conjunto de regras de produção 
S = b, símbolo de partida 
 
L(G) é a linguagem gerada a partir de G 
Gramáticas BNF (3) 
Exemplo 2 (continuação): Para gerar a palavra aaabb na 
linguagem L(G) com alfabeto {a,b} podemos usar a seguinte 
derivação. 
 
S = b 
 
b  ab  aab  aaab  aaabb  aaabbb  aaabb  aaabb 
 
Também escrito como: 
 
b * aaabb , ou seja, b deriva aaabb com zero ou mais operações de 
derivação 
Gramáticas BNF: Definições 
Forma Sentencial (FS) é uma seqüência válida de símbolos 
terminais e não terminais que podem ser obtidos a partir das 
regras de produção de uma gramática. Ex.: aab; aaabbb; e aaabb 
 
Operação de derivação (OD) é ato de aplicar uma regra de 
produção a uma FS com símbolos não terminais para se obter 
uma outra FS válida. Ex.: aaabb  aaabbb 
 
Derivação é uma seqüência de ODs que leva do símbolo de 
partida b a uma palavra válida (conjunto de símbolos terminais) 
na linguagem L(G). 
Exemplo de BNF 
Expressões simples sobre números e identificadores: 
 
 
<meta> ::= <expr> 
<expr> ::= <expr><op><expr> 
 | num 
 | id 
<op> ::= + 
 | - 
 | * 
 | / 
símbolo de partida 
não terminais 
terminais 
Análise Léxica versus Parsing 
Expressões regulares: 
 
• são usadas para reconhecer tokens, isto é classificar identificadores, 
números, palavras chaves, etc. 
• são mais concisas e mais fáceis de entender 
• tornam fácil construir analisadores léxicos a partir de DFA 
 
Gramáticas livres de contextos: 
 
• são usadas para reconhecer a gramática de LPs 
• podem contar: (), begin ... end, e if ... then ... else, etc. 
• são usadas para construir estruturas intermediárias (árvores de 
parsing e tabelas de símbolos) 
 
A gramática da linguagem C tem cerca de 200 regras de 
produção. 
Exemplo de Derivação à Direita 
Expressão “x + 2 - y” 
 
regra 1: <meta> 
regra 2: <expr> 
regra 4: <expr> <op> <expr> 
regra 6: <expr> <op> <id,y> 
regra 1: <expr> - <id,y> 
regra 3: <expr> <op> <expr> - <id,y> 
regra 5: <expr> <op> <num,2> - <id,y> 
regra 4: <expr> + <num,2> - <id,y> 
final: <id, x> + <num,2> - <id,y> 
derivação à 
direita 
(rightmost 
derivation) 
1) <meta> ::= <expr> 
2) <expr> ::= <expr><op><expr> 
3) | num 
4) | id 
5) <op> ::= + 
6) | - 
7) | * 
8) | / 
Árvore de Parsing 
meta 
op 
expr expr 
expr 
expr 
op 
expr 
+ 
- <id,y> 
<num,2> <id,x> 
Problema da Precedência 
Considere a seguinte expressão 
“x + 2 * y”, sua árvore de 
parsing será: 
meta 
op 
expr expr 
expr 
expr 
op 
expr 
+ 
* <id,y> 
<num,2> <id,x> 
Uma avaliação desta árvore produzirá (x+2)*y. Isto está errado. 
Nossa gramática não tem a noção de precedência na avaliação 
das regras de produção. A precedência deve ser embutida na 
própria gramática. Considere esta outra gramática ... 
Solucionando o Problema 
1) <meta> ::= <expr> 
2) <expr> ::= <expr><op><expr> 
3) | num 
4) | id 
5) <op> ::= + 
6) | - 
7) | * 
8) | / 
1) <meta> ::= <expr> 
2) <expr> ::= <expr> + <termo> 
3) | <expr> - <termo> 
4) | <termo> 
5) <termo> ::= <termo> * <fator> 
6) | <termo> / <fator> 
7) | <fator> 
8) <fator> ::= num 
9) | id 
A gramática força a precedência pois “termos” derivados de 
expressões multiplicativas são sempre derivados de expressões 
de soma e subtração. 
Problema da Ambigüidade 
Quando uma gramática tem mais de uma derivação para uma 
forma sentencial há um problema de ambigüidade. Considere 
o clássico problema do “if”: 
 
(A) <stmt> ::= if <expr> then <stmt> 
(B) | if <expr> then <stmt> else <stmt> 
(C) | outras declarações 
 
Considere a forma setencial “if E1 then if E2 then S1 else S2”. Esta FS 
tem duas derivações: (A)(B) e (B)(A). A correta seria a 
primeira pois normalmente o “else” casa com o “then” mais 
próximo. 
Solucionando o Problema 
Como no caso da precedência, a ambigüidade deve ser 
resolvida pela própria gramática. 
 
A) <stmt> ::= <casado> 
B) | <solto> 
C) <casado> ::= if <expr> then <casado> else <casado> 
D) | outras declarações 
E) <solto> ::= if <expr> then <stmt> 
F) | if <expr> then <casado> else <solto> 
 
Esta gramática gera a mesma linguagem da anterior mas 
sempre "casa" cada else com o then mais próximo. 
Como os Parsers são Construídos 
gerador de 
parser (yacc, 
bison, javaCC) 
parser gramática 
tokens 
RI 
Curiosidade: yacc, bison e JavaCC 
funcionam como linguagens funcionais 
Exemplo YACC 
file : program 
 | module 
 ; 
 
program : program_heading semicolon block DOT 
 ; 
 
program_heading : PROGRAM identifier 
 | PROGRAM identifier LPAREN identifier_list 
RPAREN 
 ; 
 
identifier_list : identifier_list comma identifier 
 | identifier 
 ; 
 
block : label_declaration_part 
 constant_definition_part 
 type_definition_part 
 variable_declaration_part 
 procedure_and_function_declaration_partstatement_part 
 ; 
Exemplo de trecho de um arquivo YACC para a linguagem Pascal. 
Arquivo completo está no FTP do curso. 
Exemplo JavaCC 
void IfStatement(): 
/* 
 * The disambiguating algorithm of JavaCC automatically binds dangling 
 * else's to the innermost if statement. The LOOKAHEAD specification 
 * is to tell JavaCC that we know what we are doing. 
 */ 
{} 
{ 
 "if" "(" Expression() ")" Statement() [ LOOKAHEAD(1) "else" Statement() 
] 
} 
 
void WhileStatement(): 
{} 
{ 
 "while" "(" Expression() ")" Statement() 
} 
 
void DoStatement(): 
{} 
{ 
 "do" Statement() "while" "(" Expression() ")" ";" 
} 
Exemplo de trecho de um arquivo JavaCC para a linguagem Java. 
Tipos de Parsers 
Top-down (de cima para baixo): 
 
• começa na raiz da árvore de derivação 
• pega uma produção e tenta encaixar ela a entrada (tokens) 
• pode requerer backtracking 
 
Bottom-up (de baixo para cima): 
 
• começa nas folhas da árvore de derivação 
• começa num estado aceitável de tokens de entrada 
• à medida que os tokens são consumidos muda de estado que codificam 
as novas possibilidades (reconhece prefixos válidos) 
• usa uma pilha para armazenar tanto o estado como a forma sentencial 
atual 
 
O YACC usa um parser LALR de baixo para cima. 
O JavaCC usa um parser de cima para baixo. 
Discussão de técnicas de Parsing estão fora o 
escopo deste curso. Este é um assunto extenso e 
algo complexo. 
 
Descrição destas técnicas podem ser encontradas 
em qualquer bom livro de compiladores.