De forma resumida:
Análise sintática ascendente, também chamada de bottom-up, o analisador pode iniciar com um entrada de dados e tentar reescrevê-la até o símbolo inicial. Intuitivamente, o analisador tentar localizar os elementos mais básicos, e então elementos maiores que contêm os elementos mais básicos, e assim por diante. Exemplo: analisador sintático LR (Left-to-right Right-most-derivation).
Análise sintática descendente, também chamada de top-down, o analisador pode iniciar com o símbolo inicial e tentar transformá-lo na entrada de dados. Intuitivamente, o analisador inicia dos maiores elementos e os quebra em elementos menores. Exemplo: analisador sintático LL (Left-to-right Left-most-derivation)
Análise sintática
A análise sintática é a segunda etapa do processo de compilação (a primeira é a análise léxica) e na maioria dos casos utiliza gramática livre de contexto para especificar a sintaxe de uma linguagem de programação. A principal tarefa do analisador sintático, conhecido como parsing, é determinar se o programa de entrada representado pelo fluxo de tokens possui as sentenças válidas para a linguagem de programação. No caso afirmativo, queremos adicionalmente descobrir a maneira (ou uma das maneiras) pela qual a cadeia pode ser derivada seguindo as regras da gramática.
Fazendo uma analogia gramática da língua portuguesa, que estuda a disposição das palavras em uma frase, essa parte da compilação é responsável por determinar se uma cadeia de símbolos léxicos pode ser gerada por uma gramática.
As gramáticas livres de contexto representam uma gramática formal e pode ser escrita através de algoritmos fazendo a derivação de todas as possíveis construções da linguagem. Essas derivações tem como objetivo determinar se um fluxo de palavras se encaixa na sintaxe da linguagem de programação.
Uma derivação é uma sequência de substituições de não‐terminais por uma escolha das regras de produção gramaticais. Quando fazemos a derivação deve-se aplicar a regra de produção para substituir cada símbolo não terminal por um símbolo terminal, isso permite identificar se certa cadeias de caracteres pertence a linguagem, as regras expandem todas as produções possíveis. Como resultado desse processo temos a árvore de derivação, que é uma alternativa gráfica para mostrar o processo de derivação de uma sentença em uma gramática.
A maneira pela qual a árvore de derivação da cadeia analisada x
é construída, diz se a análise sintática é descendente ou ascendente.
Análise sintática descendente, também chamada de top-down: a árvore de derivação correspondente a
x
é construída de cima para baixo, ou seja, da raiz (o símbolo inicialS
) para as folhas, onde se encontrax
. Nesse tipo de análise, é preciso decidir qual regraA→β
será aplicada a um nó rotulado por um não-terminalA
. A expansão deA
é feita criando nós filhos rotulados com os símbolos deβ
.Análise sintática ascendente, também chamada de bottom-up: a árvore de derivação correspondente a
x
é construída de baixo para cima, ou seja, das folhas, onde se encontrax
, para a raiz, onde se encontra o símbolo inicialS
. Nesse tipo de análise, é preciso decidir quando a regraA→β
será aplicada, e devemos encontrar nós vizinhos rotulados com os símbolos deβ
. A redução pela regraA→β
consiste em acrescentar à árvore um nóA
, cujos filhos são os nós correspondentes aos símbolos deβ
.
Nos dois tipos, as árvores são construídas da esquerda para a direita. A razão para isso é que a escolha das regras deve se basear na cadeia a ser gerada, que é lida da esquerda para a direita.
Exemplo, considere a seguinte gramática e a cadeia x = a+a*a
:
1. E → E + T
2. E → T
3. T → T*F
4. T → F
5. F → (E)
6. F → a
Na análise descendente:
As regras são consideradas na ordem 1 2 4 6 3 4 6 6, a mesma ordem em que as regras são usadas na derivação esquerda:
E ⇒ E+T ⇒ T+T⇒ a+T ⇒ a+T*F ⇒ a+F*F ⇒ a+a*F ⇒ a+a*a
Com a análise ascendente, por outro lado, as regras são identificadas na ordem 6 4 2 6 4 6 3 1, neste caso, a ordem das regras corresponde à derivação direita, invertida:
a+a*a ⇐ F+a*a ⇐ T+a*a ⇐ E+a*a ⇐ E+F*a ⇐ E+T*a
Ou seja:
E ⇒ E+T ⇒ E+T∗F ⇒ E+T∗a ⇒ E+F∗a ⇒ E+a∗a ⇒ T+a∗a ⇒ F+a∗a ⇒ a+a∗a
Referências: