Principiul analizei sintactice descendente nerecursive

Este acelasi ca si in cazul analizorului cu descendenti recursivi, in sensul ca procesul de analiza se realizeaza prin derivari succesive ale neterminalelor, incepand cu radacina, dar implementarea este diferita, si anume, derivarile nu se transpun ca secvente de cod, ci se bazeaza pe structuri de date in care se indica ramurile de derivare.

Structurile folosite sunt:

O tabela de analiza, ale carei intrari contin cate o productie a gramaticii (dupa care se face derivarea la un moment dat).
O stiva de analiza in care se introduc simboluri ale gramaticii.

• extragere din varful stivei si avans in sirul de intrare;
• selectarea unei intrari a tabelei de analiza si expandarea (derivarea) conform productiei indicate in tabela;
• semnalarea unei situatii de eroare.

Restrictiile care se impun asupra unei gramatici, in vederea aplicarii analizei de tip LL(1) sunt aceleasi ca si in cazul analizei cu descendenti recursivi, si anume:

• eliminarea recursivitatii stangi;
• eliminarea ambiguitatii (prin factorizare la stanga si/sau alte ajustari aduse gramaticii).

Algoritmul de analiza

Vom nota:

• sp - indicatorul stivei de analiza,
• atom - simbolul curent din sirul de intrare, TabSIN- tabela de analiza.

procedure  AsinLL1 is
    *initializeaza stiva cu simbolul $ si cu radacina gramaticii
    sp = 2
    call ALEX
    repeat
        X= stiva[sp]
        if  X este terminal then
           if  X = atom then
               sp = sp - 1
               if atom nu este $ then
                   call  ALEX
              endif
           else
                *semnaleaza eroare
           endif
        else
           i = TabSIN [X, atom]
           if i nu este 0 then
                    *extrage X din stiva
                    *depune in stiva sirul simbolurilor din membrul drept al productiei indicate de i, incepand cu
                      simbolul cel mai din dreapta
           else
                    *semnaleaza eroare
           endif
        endif
    until atom = $
end  AsinLL1

Algoritmii de construire a tabelei de analiza

Tabela de analiza va avea un numar de linii egal cu numarul neterminalelor si numarul de coloane egal cu numarul terminalelor (inclusiv simbolul $).

Completarea tabelei de analiza

procedure complTabSIN is
    for fiecare relatie A alfa din G  do
        for fiecare a din PRIM(alfa) do
          TabSIN[A, a] = A alfa
         endfor
        if  Epsilon este in PRIM(alfa) then
          for fiecare b din URM(A) do
            TabSIN [A, b] = A alfa
          endfor
          if Epsilon este in URM(A) then
           TabSIN [A, $] = A alfa
          endif
        endif
    endfor
    for fiecare TabSIN [A, a] necompletat  do
        *completeaza TabSIN [A, a] cu apel de eroare
    endfor
end complTabSIN

O multime URM(A) contine toate terminalele a care pot sa apara imediat in dreapta lui A, intr-un sir oarecare al limbajului sursa:

Calculul acestor multimi se face conform algoritmilor de mai jos:
 

Calculul multimilor PRIM

procedure calculPRIM(alfa) is
    *initializeaza PRIM(alfa) cu multimea vida
    if alfa este format dintr-un singur simbol X then
        if X este terminal then
            PRIM (X) = { X }
        else
            for toate relatiile X a beta do
                    *adauga a la PRIM (X)
            endfor
            if exista X Epsilon then
                    *adauga Epsilon la PRIM (X)
           endif
            for toate relatiile X Y₁Y₂ . . .Y_n, cu Y₁ - neterminal do
                    *adauga PRIM (Y₁) - { Epsilon } la PRIM(X)
                   gata = false
                   i = 2
                   repeat
                       if  Epsilon nu este in PRIM(Y_i-1) then
                           gata = true
                       else
                            *adauga PRIM (Y_i ) - { Epsilon } la PRIM (X)
                           i = i + 1
                           if  i > n then
                                *adauga Epsilon la PRIM(X)
                           endif
                       endif
                   until  i > n or gata
            endfor
        endif
    else
        *consideram ca alfa este de forma X₁X₂ . . . X_m
        *adauga PRIM (X₁)- { Epsilon } la PRIM (alfa )
        i = 2
        gata = false
        repeat
            if Epsilon nu este in PRIM (X_i-1) then
               gata = true
            else
                *adauga PRIM (X_i ) - { Epsilon } la PRIM (alfa)
               i = i + 1
               if  i > m then
                    *adauga Epsilon la PRIM (alfa)
               endif
            endif
        until  i > m or gata
    endif
end  calculPRIM

Calculul multimilor URM

procedure calculURM(A) is
    *initializeaza URM(A) cu multimea vida
    if  A este radacina gramaticii then
        *adauga Epsilon la URM(A)
    endif
    for toate productiile Balfa A beta do
        *adauga PRIM(beta)- { Epsilon } la URM(A)
        if beta este sirul vid or Epsilon este in PRIM(beta) then
            *adauga URM(beta) la URM(A)
        endif
    endfor
end  calculURM(A)

Multimile PRIM si URM corespunzatoare fiecarui neterminal al gramaticii se pot reprezenta folosind cate o tabela, TabPRIM, respectiv TabURM, cu elemente de tip boolean, indexate pe verticala cu neterminale, iar pe orizontala cu terminale; un element de coordonate [A, a] oarecare al acestor tabele va contine valoarea true daca a este in PRIM(A), respectiv a este in URM(A), si false in caz contrar.

Daca, in urma completarii tabelei de analiza, se obtin intrari multiple (care contin doua sau mai multe productii), inseamna ca gramatica respectiva este ambigua. In cazul limbajelor de programare cunoscute, de cele mai multe ori, la o analiza atenta a gramaticii, proiectantul poate stabili care dintre productii poate ramane in tabela, la elementul in cauza.
 
 

Desfasurarea lucrarii

Se va realiza un generator de analizor LL(1) care sa primeasca la intrare productiile unei gramatici date de conducatorul lucrarii (sau cea din Anexa B). Analizorul rezultat va tipari la executie, la fiecare pas, urmatoarele informatii:

• continutul stivei de analiza;
• atomul curent din sirul de intrare;
• actiunea efectuata: extragere din stiva si avans in sirul de intrare, sau expandare (caz in care se indica productia cu care se face expandarea);