analise

Compiladores ––
Compiladores
Análise Sintática
Fabiano Baldo

Gramáticas Livre de Contexto (GLC)
Gramáticas Livre de Contexto (GLC)
• ÉÉ utilizada na especificação formal da sintaxe de uma ili d ifi ã f ld i d linguagem de programação.
• É um conjunto de produções ou regras gramaticais
É
j d d õ i i da seguinte forma:
A → X1 X2 Xn
A → X
• A produção tem exatamente um símbolo A do lado esquerdo. d
• Pode ter zero ou mais símbolos Xi do lado direito .
• Por exemplo, uma clausula while é definida desta forma: Fabiano Baldo ‐ UDESC

2

Gramáticas Livre de Contexto
Gramáticas Livre de Contexto
• Dois tipos de símbolos podem aparecer em uma GLC:
D i i d í b l d GLC
– Não‐terminais: São elementos substituídos pelo lado direito das produções quando aparecem do lado direito das produções, quando aparecem do lado esquerdo. – Terminais: Representam as marcações de uma linguagem p ç g g
(ou tokens).

• Uma gramática livre de contexto define uma linguagem: – Este linguagem é um conjunto de strings (seqüência) de tokens k
(
(terminais) i i)
– Cada string de tokens é derivada de uma regra de produção. produção
Fabiano Baldo ‐ UDESC

3

Gramáticas Livre de Contexto
Gramáticas Livre de Contexto
• Ex: Considere a seguinte gramática simplificada para expressões: Fabiano Baldo ‐ UDESC

4

Derivação
• Uma derivação é uma seqüência de substituições de não‐terminais por uma escolha das regras de produção gramaticais.
• A derivação é o método utilizado para a construção de uma cadeia específica de terminais, partindo de um não‐terminal inicial.
• Em geral, existem várias derivações para a construção da mesma cadeia de não‐terminais. ç Fabiano Baldo ‐ UDESC

5

Derivação
• Verificar se a seqüência de tokens é reconhecida:
– Inicia‐se com o símbolo não‐terminal chamado raiz;
– Aplica‐se produções, substituindo não‐terminais, até somente restarem terminais;
– Uma derivação