Compliadores

Compilador
Analisador Sintático

Métodos
• Podem seguir duas abordagens:
– Métodos bottom-up
• Utilizam derivação inversa
• Tenta casar partes da entrada com o lado direto das produções

– Métodos top-down

• Sempre partem da raiz (top-down)
• São baseados em derivações sucessivas
• Devem usar busca direcionada

• Tais abordagens pode ser com ou sem Backtracking
– Com = maior número de gramáticas, porém mais complexo e lento
– Sem = menor número de gramáticas, porém simples e eficiente

Método Top-Down ou Descendente
• Exemplo:
1
2
?

Gramática ambígua
TR
T  aTc
R
R  RbR

Método Top-Down ou Descendente
• Podemos escolher uma das seguintes opções:

– Análise preditiva recursiva
• Construção de um conjunto de procedimentos, normalmente recursivos, um para cada símbolo nãoterminal da gramática em questão

– Análise preditiva LL(1)
• Implementa o método descendente utilizando explicitamente uma pilha

Método Top-Down ou Descendente
• Análise preditiva recursiva:
– Seja a gramática

→ begin end | while do | if then

→ + | → * | → ** | → IDENT | NÚMERO | ( )

– Podemos reescrevê-la como: → { + }* → { * }* → { ** }* → IDENT | NÚMERO | ( )

Método Top-Down ou Descendente
• Análise preditiva recursiva:
Procedimento analisador_sintático { obtenha_símbolo(); /* chama o analisador léxico */
EXPR();
}

Procedimento EXPR() {
TERMO();
se símbolo_lido = '+' então { obtenha_símbolo(); EXPR();
}
}

::= { + }*

Método Top-Down ou Descendente
• Análise preditiva recursiva:
Procedimento TERMO() {
FATOR();
se símbolo_lido = '*' então { obtenha_símbolo(); TERMO();
}
}
Procedimento FATOR() {
PRIMÁRIO();
se símbolo_lido = '**' então { obtenha_símbolo(); FATOR();
}
}

::= { * }*

::= { ** }*

Método Top-Down ou Descendente
• Análise preditiva recursiva:
Procedimento PRIMÁRIO() { ::= IDENT | NÚMERO | ( ) se símbolo_lido = IDENT então {