Análise Sintática

A Análise Sintática trata de relacionar uma palavra com uma gramática. Especificamente, pretende-se saber se a palavra é gerada pela gramática e, se sim, qual a sua derivação.

Portanto,

A Análise Sintática é uma versão do Problema Principal de ALP quando a linguagem é gerada por uma GIC.

No capítulo anterior definiram-se as gramáticas independentes de contexto e os autómatos de pilha, para ultrapassar os limites das linguagens regulares e dos autómatos finitos no que diz respeito à definição de linguagens de programação.

Ficaram assim resolvidas as necessidades sobre um esquema formal adequado para representar as linguagens de programação e dum modelo de computação para determinar se $p\in L\left(G\right)$.

Mas mantém-se o problema da eficiência porque, embora os autómatos de pilha proporcionem um modelo computacional para as linguagens independentes de contexto, não se conhecem formas gerais para garantir que as suas computações sejam eficientes.

Restam duas possibilidades: Ou condicionar as gramáticas de forma a reduzir a ramificação durante as derivações ou "espreitar" os símbolos por processar para "guiar" as computações,

Este capítulo começa por visitar os principais métodos de pesquisa geral em grafos, de forma a avaliar o problema da eficiência nalguns casos concretos.

De seguida é primeiro apresentado um processo (sequência de passos) que permite transformar uma GIC noutra equivalente e melhor adaptada ao algoritmos de pesquisa geral (a Forma Normal de Greibach). Por fim são apresentadas as classes de gramáticas $LL$ e $LR$, que "espreitam" os próximos símbolos "por processar" para definir algoritmos deterministas de análise sintática.