Análise Sintática
Introdução
Dada uma gramática G = (T, N, P, S) uma palavra u pertencente a T*, o papel da análise sintática é:
Descobrir uma derivação que a partir de S produza u.
Gerar um árvore de derivação (parse tree) que transforme S (a raiz) em u (as folhas).
Se nenhuma derivação/árvore existir, então u não pertence a L(G).
A análise sintática pode ser descendente ou ascendente.
Na análise sintática descendente:
a derivação pretendida é à esquerda.
a árvore é gerada a partir da raiz, descendo para as folhas-
Na análise sintática ascendente:
a derivação pretendida é à direita
a árvore é gerada a partir das folhas, subindo para as folhas
O objetivo final é a transformação da gramática num programa (reconhecedor sintático) que produza tais derivações/árvores
Para as gramáticas independentes do contexto, estes reconhecedores são os autómatos de pilha
Last updated