Sintaxe de uma Linguagem
n
n
Vantagens de uma Gramática
Cada LP possui regras que descrevem a
estrutura sintática dos programas.
Especificada através de uma gramática livre
de contexto, BNF (Backus-Naur Form).
Uma gramática dá uma especificação precisa e fácil
de entender da sintaxe de uma linguagem de
programação.
Para algumas classes de gramáticas, é possível gerar
automaticamente um parser eficiente. Além disso as
ferramentas usadas indicam ambiguidades e outras
construções difíceis de serem reconhecidas e que
passariam desapercebidas.
Tem relação direta com a estrutura da linguagem
usada para tradução/compilação.
Fácil de ser estendida/atualizada.
n
n
n
n
1
2
Analisador Sintático - Parser
Parse
tree
token
programa
fonte
Analisador
Léxico
Parser
Papel do Analisador Sintático
Representação
intermediária
Resto do
front-end
n
n
pede próximo
token
n
n
Tabela de
Símbolos
3
4
Tipos de Parsers para Gramáticas
n
n
n
Métodos de parsing universais: funcionam
para qualquer gramática, mas são muito
ineficientes (inviáveis para uso prático).
Top down: constroem as parse trees a partir
da raiz em direção às folhas.
Bottom-up: constroem as parse trees a partir
das folhas.
5
Obter uma cadeia de tokens do Scanner e
verificar se pode ser gerada pela gramática.
Relatar quaisquer erros de sintaxe de uma
forma inteligível.
Deve se recuperar de erros que ocorram mais
comumente.
Assumimos que a saída de um Parser seja
uma representação de uma árvore gramatical.
Parsers Top-down ou Bottom-up
n
n
Em parsers top-down ou bottom-up a leitura
do arquivo é sempre feita da esquerda para
a direita, um símbolo de cada vez.
Só funcionam para um subconjunto de
gramáticas, que na prática são suficientes
para a grande maioria das linguagens de
programação.
6
1
Tratamento de Erros de Sintaxe
n
n
n
n
Tratamento de Erros de Sintaxe
n
Léxicos: erro de grafia.
Sintáticos: desbalanceamento de expressões.
Semânticos: operador aplicado a um operando
incompatível.
Lógicos: chamada infinitamente recursiva.
n
n
Relatar presença de erros clara e
acuradamente.
Recuperar-se do erro rapidamente, para
possibilitar a detecção de erros
subseqüentes.
Não deve gerar overhead significativo
para programas corretos.
7
8
Estratégias de Recuperação de
Erros
n
n
n
n
Gramáticas Livres de Contexto
n
Modalidade do desespero
Nível de frase
Produções de erro
Correção global
n
n
n
n
cmd → if expr then cmd else cmd
Um conjunto de símbolos terminais (tokens).
Um conjunto de símbolos não-terminais: “variáveis”.
Um conjunto de produções, cada produção consiste
de um não-terminal, uma seta, e uma seqüência de
tokens e/ou não terminais.
Um não-terminal designado como símbolo inicial.
9
Exemplo 1
10
Exemplo 1 (notação abreviada)
expr → expr op expr
expr → ( expr )
expr → - expr
expr → id
op → +
op → op → *
op → /
op → ↑
expr → expr op expr | ( expr ) | - expr | id
op → + | - | * | / | ^
11
12
2
Exemplo 2
Parse Trees
n
bloco → begin cmd_opc end
cmd_opc → lista_cmd | ∈
lista_cmd → lista_cmd ; cmd | cmd
n
Mostra graficamente como o símbolo
inicial de uma gramática deriva uma
string da linguagem.
Para uma produção A → XYZ
A
X
Y
Z
13
14
Derivações
n
n
n
Ambigüidade
Visão alternativa para verificar a validade de
uma entrada para uma dada gramática.
Fornece uma precisa descrição da construção
top-down da árvore gramatical.
Ex: derivar a cadeia
–(id+id)
n
n
Parse-tree gera uma string, mas uma
string pode possuir várias parse-trees,
se a gramática for ambígüa.
Solução: usar sempre gramáticas nãoambígüas, ou gramáticas ambígüas com
informações adicionais sobre como
resolver ambigüidades.
15
16
Gramática para Expr. Aritméticas
Exemplo: Duas Parse Trees
E → E + E | E * E | - E | ( E ) | id
Ex: -(id + id)
Ambigüidade: id + id * id
E
E
E
id
17
+
*
E
id
E
E
E
+
E
id
id
E
*
id
E
id
18
3
Expressões Regulares ×
Gramáticas Livres de Contexto
n
Exemplo
Tudo que pode ser descrito por uma expressão
regular pode ser descrito com gramáticas livres de
contexto, mas:
n
n
n
n
As regras léxicas são especificadas mais simplesmente
com expressões regulares
Expressões Regulares geralmente são mais concisas e
simples de entender
Podem ser gerados analisadores léxicos mais eficientes
a partir de expressões regulares
Estrutura/modulariza o front-end do compilador
n
n
n
(a | b)*abb
A 0 → aA0 | bA 0 | aA 1
A 1 → bA2
A 2 → bA3
A3 → ∈
Conseqüentemente, pode-se converter um
AFN em uma gramática.
19
20
Expressões Regulares ×
Gramáticas Livres de Contexto
n
n
Eliminando Ambigüidades
Expressões regulares são convenientes para
especificar a estrutura de construções
léxicas, como identificadores, constantes,
palavras chave, etc.
Em geral usa-se gramáticas para especificar
estruturas aninhadas, como parenteses,
begin-end, if-then-else, etc.
n
n
cmd → if expr then cmd
| if expr then cmd else cmd
| outro
Nas linguagens de programação normalmente
a regra é que o else casa com o then mais
próximo.
21
22
Eliminando Ambigüidades
n
Eliminando Ambigüidades
if E1 then S1 else if E2 then S2 else S3
n
23
if E1 then if E 2 then S1 else S2
24
4
Solução
Recursão à Esquerda
cmd → cmd_associado
| cmd_não_associado
cmd_associado → if expr then cmd_associado
else cmd_associado
| outro
cmd_não_associado → if expr then cmd
| if expr then cmd_associado
else cmd_não_associado
n
É possível um analisador gramatical descendente
recursivo rodar para sempre.
expr → expr + termo | termo
A → Aα | β
25
26
Eliminação da Recursão à
Esquerda
n
n
Eliminação da Recursão à
Esquerda
Uma gramática é recursiva à esquerda se
possui um não-terminal A tal que exista
uma derivação de A que gera Aα, para
alguma cadeia α.
Existem técnicas/algoritmos para eliminar
a recursão à esquerda.
n
n
A → Aα | β
pode ser substituído por
A → βA’
A’ → αA’ | ∈
E →E + T |T
pode ser substituído por
E → TE’
E’ → +TE’ | ∈
27
28
Eliminação da Recursão à
Esquerda
Exemplo
n
n
Gramática para expressões aritméticas:
E→ E+T|T
T→ T*F|F
F → (E) | id
Eliminando a recursão imediata à esquerda:
E → TE’
E’ → +TE’ | ∈
T → FT’
T’ → *FT’ | ∈
F → (E) | id
n
n
n
29
Não importa quantas produções -A existam, podemos
eliminar a recursão imediata das mesmas pela seguinte
técnica:
A → Aα1 | Aα2 | ... | Aαm | β1 | β2 | ... | βn
Onde nenhum βi começa por um A. Em seguida:
A → β1 A’ | β2 A’ | ... | βn A’
A’ → α1 A’ | α2 A’ | ... | αmA’ | ∈
Eliminar recursão envolvendo derivações em vários passos:
S → Aa | b
A → Ac | Aad | bd | ∈
⇒
A → Ac | Sd | ∈
S → Aa | b
A → bdA’ | A’
A’ → cA’ | adA’ | ∈
30
5
Fatoração à Esquerda
n
n
n
Fatoração à Esquerda
Técnica de transformação gramatical usada
para produzir uma gramática adequada à
análise sintática preditiva.
Combina os casos em que há mais de uma
alternativa
possível
a
partir
do
reconhecimento de um token.
Existem técnicas/algoritmos para fazer a
fatoração à esquerda.
Ex: cmd → if expr then cmd else cmd
| if expr then cmd
Para cada não-terminal A, encontrar o mais longo prefixo
α comum a duas ou mais alternativas. Substituir todas as
produções de A:
A → αβ1 | αβ2 | ... | αβn | γ
por: A → αA’ | γ
A’ → β1 | β2 | ... | βn
Ex:
S → iEtS | iEtSeS | a
S → iEtSS’ | a
⇒
E→b
S’ → eS | ∈
E→b
n
n
n
31
32
Análise Gramatical Preditiva
n
n
n
n
Análise Sintática Top-Down
Análise gramatical descendente recursiva é um
método top-down de análise sintática.
Não-terminal de uma G ⇒ Procedimento.
Análise gramatical preditiva é uma forma especial
de análise gramat. desc. recursiva: lookahead.
A seqüência de procedimentos chamada no
processamento da entrada ⇒ árvore gramatical.
Tentativa de se encontrar uma derivação mais à esquerda
para uma cadeia de entrada.
Análise sintática de descendência recursiva: técnica de
análise sintática top-down que suporta retrocesso.
Ex: S → cAd
A → ab | a
entrada: w = cad
Análise sintática preditiva: caso especial de análise
sintática de descendência recursiva sem retrocesso.
Relativamente fáceis de escrever à mão.
Só reconhecem alguns tipos de gramáticas: não suportam
recursão à esquerda, precisa fazer fatoração à esquerda.
n
n
n
n
n
33
Analisadores Sintáticos Preditivos
n
n
n
Escrevendo-se cuidadosamente uma gramática,
eliminando-se a recursão à esquerda e fatorandose à esquerda a gramática resultante ⇒ ASP.
Exemplo: reconhecer
cmd → if expr then cmd else cmd
| while expr do cmd
| begin lista_cmds end
Pode fazer uso na implementação de diagramas de
transição, ou ser implementado recursivamente.
35
34
Diagramas de Transições para
Analisadores Sintáticos Preditivos
n
Gramática para
expressões
aritméticas sem
recursão à
esquerda:
E → TE’
E’ → +TE’ | ∈
T → FT’
T’ → *FT’ | ∈
F → (E) | id
36
6
Diagramas de Transições
Simplificados
Análise Sintática Preditiva
Não-Recursiva
n
⇓
n
1.
2.
⇓
3.
⇒
Faz-se uso explicitamente de uma pilha, ao
invés de implicitamente através de chamadas
recursivas.
Possibilidades:
X=a=$
X=a≠$
X é um nãoterminal.
37
38
Programa de Análise Sintática
Preditiva
faça ip apontar para o primeiro símbolo de w$ ;
repetir
seja X o símbolo ao topo da pilha e a o símbolo apontado por ip ;
se X for um terminal ou $ então
se X = a então
remover X da pilha e avançar i p
senão // X é um não-terminal
se M[X, a] = X→Y1Y2...Yk então início
remover X da pilha;
empilhar Yk,Yk-1,...,Y1, com Y1 ao topo da pilha;
escrever a produção X →Y1Y2...Yk
fim
senão erro( );
até que X = $
// a pilha está vazia
PRIMEIRO e SEGUINTE
n
n
n
n
n
39
Auxilia a construção de um analisador sintático
preditivo.
Permitem preencher as entradas de uma tabela
sintática preditiva.
Os conjuntos de tokens produzidos pela função
SEGUINTE podem ser usados como tokens de
sincronização.
PRIMEIRO(α) ⇒ conjunto de terminais que
começam as cadeias derivadas de α.
SEGUINTE(A) ⇒ conjunto de terminais a que
figuram à direita do não-terminal A.
40
Tabela Sintática
NãoTerminal
PRIMEIRO e SEGUINTE
Símbolo de Entrada
id
E
E’
E→TE’
T
T’
F
T → FT’
+
*
(
)
$
E’ → ∈
E’ → ∈
T’ → ∈
T’ → ∈
E → TE’
E’ → +TE’
T → FT’
T’ → ∈
T’ → *FT’
F → id
1.
F →(E)
2.
Pilha
Entrada
$E
$E’ T
$E’ T’ F
$E’ T’ id
$E’ T’
$E’
$E’ T +
$E’ T
$E’ T’ F
$E’ T’ id
$E’ T’
$E’ T’ F *
$E’ T’ F
$E’ T’ id
$E’ T’
$E’
$
id + id * id $
id + id * id $
id + id * id $
id + id * id $
id + id * id $
id + id * id $
id + id * id $
id + id * id $
id + id * id $
id + id * id $
id + id * id $
id + id * id $
id + id * id $
id + id * id $
id + id * id $
id + id * id $
id + id * id $
Saída
E → TE’
T → FT’
F → id
T’ → ∈
E’ → +TE’
T → FT’
F → id
T’ → *FT’
Gramática:
3.
E → TE’
E’ → +TE’ | ∈
T → F T’
T’ → * F T’ | ∈
F → (E) | id
F → id
T’ → ∈
E’ → ∈
Entrada: id + id * id
41
Regras para computar PRIMEIRO(X):
Se X for um terminal, então PRIMEIRO (X) é {X}.
Se X → ∈ for uma produção, adicionar ∈ a
PRIMEIRO(X).
Se X for um não-terminal e X → Y1 Y2 ...Yk uma
produção, colocar a em PRIMEIRO(X) se, para
algum i, a estiver em PRIMEIRO(Yi ) e ∈ estiver
em todos PRIMEIRO(Y1 ), ..., PRIMEIRO(Yi - 1 );
tudo o que estiver em PRIMEIRO(Y1 ) estará
certamente em PRIMEIRO(X).
42
7
PRIMEIRO e SEGUINTE
1.
2.
3.
Exemplo
E → TE’
E’ → +TE’ | ∈
T → FT’
T’ → *FT’ | ∈
F → (E) | id
PRIMEIRO(E) = PRIMEIRO(T) = PRIMEIRO(F) = { (, id}
PRIMEIRO(E’) = {+, ∈}
PRIMEIRO(T’) = {*, ∈}
SEGUINTE(E) = SEGUINTE(E’) = { ), $}
SEGUINTE(T) = SEGUINTE(T’) = {+, ), $}
SEGUINTE(F) = {+, *, ), $}
Regras para computar SEGUINTE(A):
Colocar $ em SEGUINTE(S), onde S é o símbolo de
partida e $ o marcador de fim de entrada à direita.
Se existir uma produção A → αBβ, então tudo em
PRIMEIRO(β), exceto ∈, é colocado em
SEGUINTE(B).
Se existir uma produção A → αB ou uma produção
A → αBβ onde PRIMEIRO( β) contém ∈ (isto é, β
⇒ ∈), então, tudo em SEGUINTE(A) está em
SEGUINTE(B).
43
44
Tabela Sintática
Gramática para Tipos de Pascal
tipo → tipo_simples
| ↑ id
| array [ tipo_simples ] of tipo
tipo_simples → integer
| char
| num pontoponto num
S → iEtSS’ | a
S’ → eS | ∈
E→b
NãoTerminal
a
Símbolo de Entrada
S
S →a
b
i
t
$
S → iEtSS’
S’ → ∈
S’ → eS
S’
E
e
S’ → ∈
n
E→b
Ex: considere a entrada
array [1..5] of integer
45
46
Pseudocódigo para um
Analisador Gramatical Preditivo
void tipo ( )
{ if (lookahead está em { integer, char, num }) tipo_simples ( );
else if (lookahead = = ‘↑’) { reconhecer (‘↑’); reconhecer (id); }
else if (lookahead = = array)
{ reconhecer (array); reconhecer (‘[’); tipo_simples ( ); reconhecer (‘]’);
reconhecer (of); tipo ( ); }
else error ( );
}
void tipo_simples ( )
{ if (lookahead = = integer) reconhecer (integer) ;
else if (lookahead = = char)
reconhecer (char);
else if (lookahead = = num)
{ reconhecer (num); reconhecer (pontoponto); reconhecer (num); }
else error ( ); }
void reconhecer (token t)
{ if (lookahead = = t)
lookahead = proximo_token ( );
else error ( ); }
47
8