Compiladores
1
Programa
v = 5;
if (v>5)
x = 12 + v;
while (x !=3) {
x = x - 3;
v = 10;
}
......
Código de Máquina
Compilador
Add v,v,0
cmp v,5
jmplt ELSE
THEN:
add x, 12,v
ELSE:
WHILE:
cmp x,3
...
2
Compilador
analisador
léxico
entrada
programa
parser
saída
código de
máquina
3
Um parser conhece a gramática
da linguagem de programação
4
Parser
PROGRAM  STMT_LIST
STMT_LIST  STMT; STMT_LIST | STMT;
STMT  EXPR | IF_STMT | WHILE_STMT
| { STMT_LIST }
EXPR  EXPR + EXPR | EXPR - EXPR | ID
IF_STMT  if (EXPR) then STMT
| if (EXPR) then STMT else STMT
WHILE_STMT while (EXPR) do STMT
5
O parser encontra a derivação
para uma entrada particular
derivação
entrada
10 + 2 * 5
Parser
E -> E + E
|E*E
| INT
E => E + E
=> E + E * E
=> 10 + E*E
=> 10 + 2 * E
=> 10 + 2 * 5
6
árvore de derivação
derivação
E => E + E
=> E + E * E
=> 10 + E*E
=> 10 + 2 * E
=> 10 + 2 * 5
E
E
10
+
E
2
E
*
E
5
7
árvore de derivação
E
E
10
código de máquina
+
E
2
E
*
mult a, 2, 5
add b, 10, a
E
5
8
Parsing
9
string
de entrada
Parser
gramática
derivação
10
Exemplo:
Parser
entrada
aabb
S  SS
S  aSb
S  bSa
S 
derivação
?
11
Busca Exaustiva
S  SS | aSb | bSa | 
Fase 1:
S  SS
S  aSb
Encontrar derivação
aabb
S  bSa
S 
Todas as possíveis derivações de comprimento 1
12
S  SS
S  aSb
aabb
S  bSa
S 
13
Fase 2
S  SS | aSb | bSa | 
S  SS  SSS
S  SS  aSbS
Fase 1
S  SS
S  aSb
aabb
S  SS  bSaS
S  SS  S
S  aSb  aSSb
S  aSb  aaSbb
S  aSb  abSab
S  aSb  ab
14
S  SS | aSb | bSa | 
Fase 2
S  SS  SSS
S  SS  aSbS
aabb
S  SS  S
S  aSb  aSSb
S  aSb  aaSbb
Fase 3
S  aSb  aaSbb  aabb
15
Resultado final da busca exaustiva
(top-down parsing)
Parser
entrada
aabb
S  SS
S  aSb
S  bSa
S 
derivação
S  aSb  aaSbb  aabb
16
Complexidade de tempo da busca exaustiva
Suponha que não existam produções da forma
A
A B
Número de fases para um string w :
2| w|
17
Para uma gramática com
Tempo para a fase 1:
k regras
k
k possíveis derivações
18
Tempo para a fase 2:
k
2
k
2
possíveis derivações
19
Tempo para a fase
2| w| :
k
2|w|
2|w| possíveis derivações
k
20
Tempo total requerido para um string
k  k  k
2
fase 1
fase 2
w:
2|w|
fase 2|w|
Extremamente ruim!!!
21
Existem algoritmos mais rápidos
para tipos especiais de gramáticas
S-grammar:
A  ax
símbolo
Par
string
de variáveis
( A, a) ocorre apenas uma vez
22
S-grammar - exemplo:
S  aS
S  bSS
S c
Cada string tem uma única derivação
S  aS  abSS  abcS  abcc
23
Para S-grammars:
No parser por busca exaustiva
existe uma única escolha em cada fase
Tempo para cada fase:
1
Tempo total para parsing de
w : | w|
24
Para gramáticas livres de contexto em geral:
Existe um algoritmo de parsing
que faz parsing de um string w
3
em tempo | w |
25
Simplificações
de
Gramáticas Livres de Contexto
26
Regra de Substituição
gramática
equivalente
Aa
A  aaA
A  abBc
B  abbA
Bb
Substitua B
Aa
A  aaA
A  ababbAc
A  abbc
27
Em geral:
A  xBz
B  y1 | y2 |  | yn
Substitua
B
A  xy1z | xy2 z |  | xyn z
gramática
equivalente
28
Produções Inúteis
S  aSb
S 
SA
A  aA
Produção Inútil
Algumas derivações nunca terminam...
S  A  aA  aaA    aaaA  
29
Outra gramática:
SA
A  aA
A
B  bA
Produção inútil
Nunca é atingida a partir de S
30
Em geral:
Se
S    xAy    w
w L(G )
Então a variável
A é útil
Caso contrário, a variável
A é inútil
31
Uma produção A  x é útil
se todas as suas variáveis são úteis
32
Removendo Produções Inúteis
Gramática Exemplo:
S  aS | A | C
Aa
B  aa
C  aCb
33
Primero: encontre todas as variáveis que
produzem strings só com terminais
S  aS | A | C
Aa
Passo 1:
{ A, B}
Passo 2:
{ A, B, S}
B  aa
C  aCb
34
Mantenha apenas as variáveis
{ A, B, S}
que produzem símbolos terminais
S  aS | A | C
Aa
B  aa
C  aCb
S  aS | A
Aa
B  aa
35
Segundo: Encontre todas as variáveis
atingíveis a partir de
S
Grafo de Dependência
S  aS | A
Aa
B  aa
S
A
B
não
atingível
36
Mantenha apenas as variáveis
atingíveis a partir de S
S  aS | A
Aa
B  aa
Gramática Final
S  aS | A
Aa
37
Variáveis Nulas
l - produção:
A
Variável Nula:
A  
38
Removendo Variáveis Nulas
Gramática Exemplo:
S  aMb
M  aMb
M 
Variável nula
39
Gramática Final
S  aMb
M  aMb
M 
Substitua
M 
S  aMb
S  ab
M  aMb
M  ab
40
Produções Unitárias
Produção Unitária:
A B
41
Removendo Produções Unitárias
Observação:
A A
É removida imediatamente
42
Gramática Exemplo:
S  aA
Aa
A B
BA
B  bb
43
S  aA
Aa
A B
BA
B  bb
Substitua
A B
S  aA | aB
Aa
B  A| B
B  bb
44
S  aA | aB
Aa
B  A| B
B  bb
Remova
BB
S  aA | aB
Aa
BA
B  bb
45
S  aA | aB
Aa
Substitua
BA
BA
B  bb
S  aA | aB | aA
Aa
B  bb
46
Remova produções repetidas
Gramática final
S  aA | aB | aA
S  aA | aB
Aa
Aa
B  bb
B  bb
47
Removendo Tudo
Passo 1: Remova Variáveis Nulas
Passo 2: Remova Produções Unitárias
Passo 3: Remova Variáveis Inúteis
48