Laboratório de Computação II
Augusto L. P. Nunes
[Link]@[Link]
Ferramentas de Apoio
E-mail: [Link]@[Link]
Site: [Link]/~alpnunes/lessons
One Drive|Dropbox|Google Drive
2
Descrição Formal de Sintaxe
• Reconstruir partes de códigos como sequência de
símbolos de uma linguagem e suas regras
Reconstrução
Código
Sebesta, 2003
3
Descrição Formal de Sintaxe
• Forma de Backs-Naur (BNF): metalinguagem usada
para descrever sitaxe.
• Exemplo: definição de atribuição
<atribuição> → <var> = <expressão>
4
Descrição Formal de Sintaxe
• Forma de Backs-Naur (BNF): metalinguagem usada
para descrever sitaxe.
• Exemplo: definição de estrutura condicional
<inst_if> → if <expr_logica> then <inst>
<inst_if> → if <expr_logica> then <inst> else <inst>
5
Descrição Formal de Sintaxe
• Forma de Backs-Naur (BNF): metalinguagem usada
para descrever sitaxe.
• Exemplo: definição de estrutura condicional
<inst_if> → if <expr_logica> then <inst>
<inst_if> → if <expr_logica> then <inst> else <inst>
Símbolos terminais 6
Descrição Formal de Sintaxe
• Forma de Backs-Naur (BNF): metalinguagem usada
para descrever sitaxe.
• Exemplo: definição de estrutura condicional
<inst_if> → if <expr_logica> then <inst>
<inst_if> → if <expr_logica> then <inst> else <inst>
Símbolos não-terminais 7
Análise Sintática
• Árvore de Análise (parse trees):
estrutura que descreve a derivação de
um conjunto de regras
BNF para atribuição
Derivação para
A = B * (A + C) 8
Árvore de Análise
Especificação de Gramáticas
• As gramáticas são responsáveis por definirem as
regras de produção de uma linguagem
<programa> → begin <lista_inst> end
9
Especificação de Gramáticas
• As gramáticas são responsáveis por definirem as
regras de produção de uma linguagem
<programa> → begin <lista_inst> end
Define o corpo do programa
10
Especificação de Gramáticas
• As gramáticas são responsáveis por definirem as
regras de produção de uma linguagem
<programa> → begin <lista_inst> end
<lista_inst> → <inst> | <inst> ; <lista_inst>
11
Especificação de Gramáticas
• As gramáticas são responsáveis por definirem as
regras de produção de uma linguagem
<programa> → begin <lista_inst> end
<lista_inst> → <inst> | <inst> ; <lista_inst>
Abre a possibilidade de o corpo do
programa ser desenvolvido
12
Especificação de Gramáticas
• As gramáticas são responsáveis por definirem as
regras de produção de uma linguagem
<programa> → begin <lista_inst> end
<lista_inst> → <inst> | <inst> ; <lista_inst>
<inst> → <var> = <expressão>
13
Especificação de Gramáticas
• As gramáticas são responsáveis por definirem as
regras de produção de uma linguagem
<programa> → begin <lista_inst> end
<lista_inst> → <inst> | <inst> ; <lista_inst>
<inst> → <var> = <expressão>
Adiciona expressões à definição da linguagem
14
Especificação de Gramáticas
• As gramáticas são responsáveis por definirem as
regras de produção de uma linguagem
<programa> → begin <lista_inst> end
<lista_inst> → <inst> | <inst> ; <lista_inst>
<inst> → <var> = <expressão>
<var> → A | B | C
15
Especificação de Gramáticas
• As gramáticas são responsáveis por definirem as
regras de produção de uma linguagem
<programa> → begin <lista_inst> end
<lista_inst> → <inst> | <inst> ; <lista_inst>
<inst> → <var> = <expressão>
<var> → A | B | C
Define o padrão para nomes de
variáveis 16
Especificação de Gramáticas
• As gramáticas são responsáveis por definirem as
regras de produção de uma linguagem
<programa> → begin <lista_inst> end
<lista_inst> → <inst> | <inst> ; <lista_inst>
<inst> → <var> = <expressão>
<var> → A | B | C
<expressao> → <var> + var | <var> - <var> | <var>
17
Especificação de Gramáticas
• As gramáticas são responsáveis por definirem as
regras de produção de uma linguagem
<programa> → begin <lista_inst> end
<lista_inst> → <inst> | <inst> ; <lista_inst>
<inst> → <var> = <expressão>
<var> → A | B | C
<expressao> → <var> + var | <var> - <var> | <var>
Define o as operações da linguagem 18
Aplicação de Gramáticas
<programa> → begin <lista_inst> end
→ begin <nst> ; <lista_inst> end
→ begin <var> = <expressão> ; <lsita_inst> end
→ begin A = <expressão> ; <lsita_inst> end
→ begin A = <var> + <var> ; <lsita_inst> end
→ begin A = B + <var>; <lsita_inst> end
→ begin A = B + C; <lsita_inst> end
→ begin A = B + C; <inst> end
→ begin A = B + C; <var> = <expressão> end
→ begin A = B + C; B = <expressão> end
→ begin A = B + C; B = <var> end
→ begin A = B + C; B = C end
19
Aplicação de Gramáticas
<programa> → begin <lista_inst> end
→ begin <nst> ; <lista_inst> end
→ begin <var> = <expressão> ; <lsita_inst> end
→ begin A = <expressão> ; <lsita_inst> end
→ begin A = <var> + <var> ; <lsita_inst> end
→ begin A = B + <var>; <lsita_inst> end
→ begin A = B + C; <lsita_inst> end
→ begin A = B + C; <inst> end
→ begin A = B + C; <var> = <expressão> end
→ begin A = B + C; B = <expressão> end
→ begin A = B + C; B = <var> end
→ begin A = B + C; B = CPrograma
end construído a
partir do exemplo de
20
gramática
Árvore de Análise
• As gramáticas utilizadas nas linguagens de
programação podem ser organizadas em estruturas
hierárquicas
• Qualquer sequência de código pode ser construída a
partir de uma árvore da gramática correspondente
• Exemplo:
Gramática Código Fonte
<atribuicao> → <id> = <expressao>
<id> → A | B | C A=B+ A+C
<expressao> → id + <expressao> | id 21
Árvore de Análise
<atribuição>
<id> = <expressao>
A <id> + <expressao>
B <id> + <expressao>
A <id>
C
22
Análise Inversa
• É um processo no qual partimos de um fragmento
de código e tentamos construir uma árvore de
análise válida
• Caso a árvore de análise não possa ser construída, o
código não pertence à linguagem
23
Referências
ROBERT W. SEBESTA, Conceitos de Linguagens de Programação, Bookman
Companhia Ed, 2003 - 638 páginas, ISBN 8536301716, 9788536301716
24
25
