Compiladores

COMPILADORES

3. ANÁLISE SINTÁTICA
INTRODUÇÃO Toda linguagem de programação tem regras que descrevem sua estrutura sintática (ou sintaxe). A sintaxe de uma LP pode ser descrita por uma gramática livre de contexto1 ou pela notação BNF. O uso de gramáticas traz vantagens para projetistas de linguagens e escritores de compiladores pelas seguintes razões:
•

•

•

•

uma gramática dá uma especificação sintática precisa de uma LP (embora talvez menos clara que a notação BNF); para certas classes de gramáticas, pode-se automatizar o processo de construção do analisador sintático e o gerador automático pode revelar certas ambigüidades sintáticas da LP difíceis de serem detectadas pelo escritor do compilador; uma gramática bem projetada dá estrutura à uma LP, o que facilita a compilação e a detecção de erros de programas fonte; e novas construções sintáticas que surgem com a evolução de uma LP podem ser incorporadas mais facilmente à linguagem se seu compilador tem uma implementação baseada em uma descrição gramatical.

1Gramática

livre de contexto é aquela que tem regras do tipo A ::= α, com A ∈ VN e α ∈ V

*

© UFCG / DSC / PSN, 2005 – Parte 3: Análise Sintática – Pág. 1

COMPILADORES Dada uma gramática G(S), verificar se uma dada sentença w pertence ou não à L(G) é verificar se S =>+ w para alguma seqüência de derivação S => w1 => w2 => ... => wn => w (em outra palavras, é obter uma árvore de derivação sintática (ADS) para w). Nesse sentido, o analisador sintático de um compilador nada mais é do que um construtor de ADS. Quando ele consegue construir uma ADS para uma sentença w (um programa), dizemos que w está sintaticamente correta. Em caso contrário, dizemos que w está sintaticamente incorreta. Os analisadores sintáticos podem ser classificados basicamente em dois grupos: descendentes e ascendentes.

© UFCG / DSC / PSN, 2005 – Parte 3: Análise Sintática – Pág. 2

COMPILADORES Um analisador sintático descendente tenta construir a ADS para