Análise Sintática Ascendente e Descendente

 Estratégias gerais de Análise Sintática

Ascendente (Bottom-up);

Descendente (Top-down);

 Análise Sintática Ascendente

  Analise Sintática Descendente

  Estratégia Descendente ( Top-down)

  Estratégia Ascendente (Bottom-up)

   Método Escolhido: Método de Análise Sintática Descendente 

 Gramáticas tratadas por este método:

 Gramáticas LL(K)

    Gramáticas LL(K)

g _q^(k) ® K símbolos mais à esquerda de g .

 Exemplo: G₁₄

L(G₁₄) = {acbbc , acbc , dcbc , dcc }

Análise descendente de L(G₁₄) :

1-

Na parte (i) e (ii) da figura acima, N deve ser reconhecido como 'c' ou 'cb' baseado em c(5) e b(4), respectivamente;

2-

Nunca é necessário examinarmos 4 símbolos, pois G₁₄ é LL(3);

3-

Em (i) e (iii) a decisão de que produção de N usar é baseada na cadeia já reconhecida (t ). Em ambos os casos falta reconhecer a cadeia 'cbc';

Contra-exemplo: G₁₅ S ® S a | b . G₁₅ não é LL(K), qualquer que seja K.

1-

Não pode ser analisada. Não sabemos qual das duas produções usar.

2-

Não sabemos qual é o último 'a', já que dispomos só de K símbolos.

Obs.: Qualquer gramática livre de comtexto que tenha para um de seus NT N símbolos uma geração da forma N ð Na (qualquer que seja a ) não é LL(K).

   Eliminação de Recursão à Esquerda

Qualquer gramática com recursão à esquerda possui uma gramática equivalente sem recursão à esquerda.

Exemplo: G₁₅' é equivalente a G₁₅: S ® bM M ® aM | l (G₁₅')

Usando-se ERE - gramática: S ® ba* (G₁₅'')

G₁₅'' é LL(1). Não é LL(0) porque após reconhecer 'b', precisa reconhecer o próximo símbolo para decidir se a cadeia de 'a' já terminou.

   LL(K) Fortes

1970, Rosenkrantz e Steans

Em um ponto qualquer da análise canônica, se N está sendo procurado, a j é determinado exclusivamente pelos k próximos símbolos ainda não reconhecidos, independentemente de t (histórico do reconhecimento).

Obs.:

1-

As gramáticas LL(K) menos fortes simplificam o processo de análise sintática;

2-

Todas as gramáticas LL(1) são fortes e não-ambíguas;

   Gramáticas PLL(K)

1973 , Rechenberg

São LL(K) fortes com produções da forma N ® E ou N ® E{E}* , onde E contém alternativas e/ou alternativas fatoradas.

Gramáticas PLL(1)

1. S ® M | N
2. M ® a {b | Nc}*
3. D( S | e f | l ) | g

Chamaremos a esta gramática de G₁₆.

Primeiros: Para distinguir-se entre S ® M e S ® N é necessário saber se o próximo símbolo de entrada é do conjunto {'a'} ou {'d','g'} que contém os símbolos gerados mais à esquerda por M e N, respectivamente.

Seguintes: Em alguns casos é preciso deduzir os símbolos que podem sequir um determinado NT em qualquer forma sentencial.

   Gramáticas ESLL(1)

• Extensões das LL(1);
• Lados direitos das produções mais gerais do que os das gramáticas PLL(K);
• Restrições nas produções garantem análise mais eficiente do que a das gramáticas PLL(1);

  Grafos Sintáticos das Gramáticas ESLL(1)

Nó alternativo

n é uma alternativa de m.

N é alternativa de b

b é alternativa de a

/ tem uma alternativa vazia ou l - alternativa

S ® a | l
A alternativa de a é um l - nó

A alternativa de a é uma l - alternativa

A estrutura de dados para implementar estas duas gramáticas será idêntica. Gera-se um l - nó para cada l - alternativa. Logo N ® ab e N ® al b são produções equivalentes.

  Seqüência de nós alternativos (seqüência de alternativas)

Quando os nós n₁, n₂ ,..., n_m são tais que m > 1, n_i é alternativa de n _i-1, com i = 2, ..., m.

l - alternativa não é considerada um nó da seqüência.

  Sucessor

Dado um nó m de um grafo sintático, digamos que n é um sucessor de m se, e somente se, o arco que sai de m aponta diretamente para n. Se o arco leva a uma seqüência de alternativas, o primeiro nó da seqüência será o sucessor de m.

Exemplos:

1 - Na figura (i), 'c' é sucessor de 'b' ;

2 - Na figura (ii) 'b' é sucessor de 'a' ( e também sua alternativa )