Implementace LL(1) překladů

Možnosti Popis metody přepisu rozkladové tabulky Rekurzivní sestup

Implementace LL(1) překladů Překladače, přednáška č. 6

Šárka Vavrečková Ústav informatiky, FPF SU Opava [email protected]

Poslední aktualizace: 30. října 2007

Šárka Vavrečková

Implementace LL(1) překladů


Postup Programujeme syntaktickou analýzu: 1

Navrhneme vhodnou LL(1) gramatiku popisující strukturu jazyka.

2

Vytvoříme podle ní překladový automat (rozkladovou tabulku). Naprogramujeme:

3

metodou přepisu rozkladové tabulky, metodou rekurzivního sestupu.






2


3







2


3







2


3







2


3





Myšlenka postupu Implementace Vlastnosti

Přepis rozkladové tabulky Potřebujeme rozkladovou tabulku, zásobník na ukládání symbolů, proměnnou, ve které je uložen právě zpracovávaný symbol, funkci lex(), která nám vrátí další symbol, který extrahovala ze vstupního souboru (uloží do proměnné z předchozího bodu), proměnnou pro výstup (soubor, dynamická struktura apod.).





Popis metody Analýza probíhá takto: 1

zavoláme funkci Lex(),

2

zjistíme, o jaký symbol jde, přiřadíme terminál,

3

provedeme analýzu symbolu, zařadíme do derivačního stromu, při chybě nebo akceptování celého vstupu končíme výpočet,

4

pokud je hodnota symbolu potřebná (například identifikátor nebo číslo), uložíme ji,

5

návrat k prvnímu bodu.







2


3


4


5








2


3


4


5








2


3


4


5








2


3


4


5






Popis metody Budeme potřebovat tyto funkce: expand(číslo pravidla) uloží pravou stranu pravidla s daným číslem do zásobníku a na výstup přidá číslo pravidla, pop ověří shodnost symbolu na vstupu se symbolem vyjmutým ze zásobníku a načte další symbol ze vstupu, accept při konci vstupu a konci zásobníku ukončí výpočet programu, error ošetří chybu, která se vyskytla při překladu, Akce je hlavní řídicí funkce, v cyklu volá předchozí, zajišťuje „pohyb v tabulceÿ, Init je inicializační funkce (inicializuje zásobník, zajistí „přednačteníÿ prvního symbolu apod.), úklidová funkce je Done. Šárka Vavrečková




Ukážeme na příkladu: 1 ○ 2 ○ 3 ○, 4 ○ 5 ○, 6 ○, 7 ○ 8 ○, 9 10 11 ○, ○, ○

S → AB A → CD B → +AB | − AB | ε C → (S) | i | n D → ∗CD | /CD | ε Rozkladová tabulka S A B C D

i e1 e2

n e1 e2

e7

e8

+

−

e3

e4

∗

/

( e1 e2

)

$

e5

e5

e11

e11

e6 e11

e11

e9


e10




Ukážeme na příkladu: 1 ○ 2 ○ 3 ○, 4 ○ 5 ○, 6 ○, 7 ○ 8 ○, 9 10 11 ○, ○, ○

S → AB A → CD B → +AB | − AB | ε C → (S) | i | n D → ∗CD | /CD | ε Rozkladová tabulka S A B C D

i e1 e2

n e1 e2

e7

e8

+

−

e3

e4

∗

/

( e1 e2

)

$

e5

e5

e11

e11

e6 e11

e11

e9


e10




Proměnné vystup soub: string; (* název výstupního souboru *) vystup: text: (* soubor pro výstup programu *) konec: boolean; (* indikátor konce výpočtu, proveden accept*) vstupni sym: char; (* aktuální symbol načtený z prom. vstup *) vstupni atr: TAtribut; (* atribut právě načteného vstup. symbolu *) vrchol zasob:char; (* symbol na vrcholu zásobníku *) Dále předpokládáme funkce a datové struktury pro načtení znaku a práci se zásobníkem.





Proměnné vystup soub: string; (* název výstupního souboru *) vystup: text: (* soubor pro výstup programu *) konec: boolean; (* indikátor konce výpočtu, proveden accept*) vstupni sym: char; (* aktuální symbol načtený z prom. vstup *) vstupni atr: TAtribut; (* atribut právě načteného vstup. symbolu *) vrchol zasob:char; (* symbol na vrcholu zásobníku *) Dále předpokládáme funkce a datové struktury pro načtení znaku a práci se zásobníkem.





Hlavní funkce syntaktické analýzy Úkol: inicializovat výpočet, v cyklu volat funkci Akce pracující s tabulkou, ukončit výpočet.

procedure S analyza; begin Init; while (not Konec) do Akce; Done; end;





Hlavní funkce syntaktické analýzy Úkol: inicializovat výpočet, v cyklu volat funkci Akce pracující s tabulkou, ukončit výpočet.

procedure S analyza; begin Init; while (not Konec) do Akce; Done; end;





Init, Done procedure Init; begin ... otevře vstupní soubor Vytvor zasobnik; Pridej do zasobniku(’#’); Pridej do zasobniku(’S’); pop; (* načte symbol ze vstupu do vstupni sym *) Konec := false; end; procedure Done; begin Zlikviduj zasobnik; (* uvolní paměť zásobníku *) ... zavře soubory, atd. end; Šárka Vavrečková




Init, Done procedure Init; begin ... otevře vstupní soubor Vytvor zasobnik; Pridej do zasobniku(’#’); Pridej do zasobniku(’S’); pop; (* načte symbol ze vstupu do vstupni sym *) Konec := false; end; procedure Done; begin Zlikviduj zasobnik; (* uvolní paměť zásobníku *) ... zavře soubory, atd. end; Šárka Vavrečková




accept procedure accept; (* Jsme na konci vstupního souboru, syntaktická analýza správně ukončena. *) begin Konec := true; end;





pop porovná terminál ze zásobníku se vstupem (musí být stejné), posune se na vstupu (funkce Lex vrací další symbol ze vstupního souboru).

procedure pop; begin if vstupni sym = vrchol zasob then Lex(vstupni sym, vstupni atr) else error; end;





pop porovná terminál ze zásobníku se vstupem (musí být stejné), posune se na vstupu (funkce Lex vrací další symbol ze vstupního souboru).

procedure pop; begin if vstupni sym = vrchol zasob then Lex(vstupni sym, vstupni atr) else error; end;





expand procedure expand(cislo prav); begin case cislo prav of 1: begin (* S -> AB *) Pridej do zasobniku(’B’); Pridej do zasobniku(’A’); end; 2: begin (* A -> CD *) Pridej do zasobniku(’D’); Pridej do zasobniku(’C’); end; 3: begin (* B -> +AB *) Pridej do zasobniku(’B’); Pridej do zasobniku(’A’); Pridej do zasobniku(’+’); end;


4: begin (* B -> -AB *) Pridej do zasobniku(’B’); Pridej do zasobniku(’A’); Pridej do zasobniku(’-’); end; ... end; writeln(vystup, cislo prav); end;




error procedure error; begin Konec := true; writeln(’Chyba při syntaktické analýze, ...’); ... ošetření chyby end;





Akce Funkce Akce Pracuje takto: vyndá ze zásobníku jeden symbol, tím určí řádek tabulky a podle symbolu na vstupu určí sloupec tabulky, podle obsahu buňky na daném řádku a sloupci zavolá funkci expand, pop, accept nebo error (prázdná buňka znamená error), je volána v cyklu tak dlouho, dokud není konec zpracovávaného programu.





Akce procedure Akce; begin vrchol zasob := Vyjmi ze zasobniku; case vrchol zasob of ... pro S, A ’B’: case vstupni sym of (* řádek B *) ’+’: expand(3); (* sloupec + *) ’-’: expand(4); (* sloupec - *) ’)’,’$’: expand(5); (* sloupce ),$ *) else error; (* ostatní sloupce *) end; ... pro B, C, D ’#’: if (vstupni sym = ’$’) then accept else error; else if (vrchol zasob in terminaly) then pop else error; end; end; Šárka Vavrečková




Vlastnosti metody Výhody: nepoužíváme přímo rekurzi (netřeba řešit problém hloubky rekurze s prostorovou složitostí), lze využít rozkladovou tabulku. Nevýhody: hůře se implementuje sémantika.





Vlastnosti metody Výhody: nepoužíváme přímo rekurzi (netřeba řešit problém hloubky rekurze s prostorovou složitostí), lze využít rozkladovou tabulku. Nevýhody: hůře se implementuje sémantika.





Rekurzívní sestup Potřebujeme LL(1) gramatiku (nemusíme dělat rozkladovou tabulku), množiny F IRST a F OLLOW , pro každé pravidlo A → α vytvoříme „množinu signaturÿ F S(A, α) = F IRST (α · F OLLOW (A)) proměnnou, ve které je uložen právě zpracovávaný symbol, funkci lex(), která nám vrátí další symbol, který extrahovala ze vstupního souboru (uloží do proměnné z předchozího bodu), proměnnou pro výstup (soubor, dynamická struktura apod.).





Popis metody Analýza probíhá takto: 1 2

zavoláme funkci Lex(), pak opět voláme pro každý symbol, postupujeme přesně tak, jakobychom konstruovali derivační strom „ručněÿ: když jsme v uzlu ohodnoceném neterminálem, vytvoříme poduzly podle zvoleného pravidla, tentýž postup rekurzívně uplatníme na všechny poduzly (zleva doprava), které jsou ohodnoceny neterminály, u terminálních poduzlů pouze spustíme „kontrolní porovnáníÿ podobně, jako bylo u předchozí metody pop.

3

rekurzívní volání probíhá zleva doprava a shora dolů, tedy i vstup je čten zleva doprava,

4

když skončí všechny rekurzivní výpočty pro jednotlivé větve a vstup je celý přečtený ($), akceptujeme vstup. Šárka Vavrečková






3


4







3


4







3


4







3


4







3


4







3


4





Popis metody Budeme potřebovat tyto funkce: Init, Done, expect ověří shodnost symbolu na vstupu se symbolem, který je parametrem této funkce, a načte další symbol ze vstupu, S, A, B, . . . – pro každý neterminál vytvoříme stejně nazvanou funkci, tyto funkce se budou navzájem rekurzívně volat, error ošetří chybu, která se vyskytla při překladu.





Ukážeme na příkladu: S → AB A → CD B → +AB | − AB | ε C → (S) | i | n D → ∗CD | /CD | ε


1 ○ 2 ○ 3 ○, 4 ○ 5 ○, 6 ○, 7 ○ 8 ○, 9 ○, 10 ○ 11 ○,




Proměnné vystup soub: string; (* název výstupního souboru *) vystup: text: (* soubor pro výstup programu *) vstupni sym: char; (* aktuální symbol načtený z prom. vstup *) vstupni atr: TAtribut; (* atribut právě načteného vstup. symbolu *) Dále předpokládáme funkce pro načtení znaku ze vstupu.





Proměnné vystup soub: string; (* název výstupního souboru *) vystup: text: (* soubor pro výstup programu *) vstupni sym: char; (* aktuální symbol načtený z prom. vstup *) vstupni atr: TAtribut; (* atribut právě načteného vstup. symbolu *) Dále předpokládáme funkce pro načtení znaku ze vstupu.





Hlavní funkce syntaktické analýzy Úkol: inicializovat výpočet, zavolat funkci S, dále je vše voláno rekurzí, ukončit výpočet.

procedure S analyza; begin Init; S; Done; end; Šárka Vavrečková




Hlavní funkce syntaktické analýzy Úkol: inicializovat výpočet, zavolat funkci S, dále je vše voláno rekurzí, ukončit výpočet.

procedure S analyza; begin Init; S; Done; end; Šárka Vavrečková




Init, Done procedure Init; begin ... otevře vstupní soubor Lex(vstupni sym, vstupni atr); end; procedure Done; begin ... zavře soubory, atd. end;





Init, Done procedure Init; begin ... otevře vstupní soubor Lex(vstupni sym, vstupni atr); end; procedure Done; begin ... zavře soubory, atd. end;





expect porovná zpracovávaný symbol (terminál z pravidla) se znakem na vstupu (musí souhlasit), načte další znak ze vstupu.

procedure expect(term: char); begin if term = vstupni sym then Lex(vstupni sym, vstupni atr) else chyba; end;





expect porovná zpracovávaný symbol (terminál z pravidla) se znakem na vstupu (musí souhlasit), načte další znak ze vstupu.

procedure expect(term: char); begin if term = vstupni sym then Lex(vstupni sym, vstupni atr) else chyba; end;





Funkce neterminálů Pro každou množinu pravidel se stejnou levou stranou: A → α1 α2 · · · αn

procedure A; begin if vstupni sym in FS(A,α1 ) then ... postupně jsou ošetřeny symboly z řetězce α1 else if vstupni sym in FS(A,α2 ) then ... postupně jsou ošetřeny symboly z řetězce α2 else ... ostatní pravidla else error; end; Šárka Vavrečková




Funkce neterminálů Pro každou množinu pravidel se stejnou levou stranou: A → α1 α2 · · · αn

procedure A; begin if vstupni sym in FS(A,α1 ) then ... postupně jsou ošetřeny symboly z řetězce α1 else if vstupni sym in FS(A,α2 ) then ... postupně jsou ošetřeny symboly z řetězce α2 else ... ostatní pravidla else error; end; Šárka Vavrečková




Funkce neterminálů S → AB procedure S; begin if vstupni sym in (’i’,’n’,’(’) then begin A; B; end else error; end;





Funkce neterminálů S → AB procedure S; begin if vstupni sym in (’i’,’n’,’(’) then begin A; B; end else error; end;





Funkce neterminálů A → CD procedure A; begin if vstupni sym in (’i’,’n’,’(’) then begin C; D; end else error; end;





Funkce neterminálů A → CD procedure A; begin if vstupni sym in (’i’,’n’,’(’) then begin C; D; end else error; end;





Funkce neterminálů B → +AB | − AB | ε procedure B; begin if vstupni sym = ’+’ then begin expect(’+’); A; B; end else if vstupni sym = ’-’ then begin expect(’-’); A; B; end else if vstupni sym in (’)’,$) then ; else error; end; Šárka Vavrečková




Funkce neterminálů B → +AB | − AB | ε procedure B; begin if vstupni sym = ’+’ then begin expect(’+’); A; B; end else if vstupni sym = ’-’ then begin expect(’-’); A; B; end else if vstupni sym in (’)’,$) then ; else error; end; Šárka Vavrečková




Funkce neterminálů C → (S) | i | n procedure C; begin if vstupni sym = ’(’ then begin expect(’(’); S; expect(’)’); end else if vstupni sym = ’i’ then expect(’i’) else if vstupni sym = ’n’ then expect(’n’) else error; end; Šárka Vavrečková




Funkce neterminálů C → (S) | i | n procedure C; begin if vstupni sym = ’(’ then begin expect(’(’); S; expect(’)’); end else if vstupni sym = ’i’ then expect(’i’) else if vstupni sym = ’n’ then expect(’n’) else error; end; Šárka Vavrečková




Funkce neterminálů D → ∗CD | /CD | ε procedure D; begin if vstupni sym = ’*’ then begin expect(’*’); C; D; end else if vstupni sym = ’/’ then begin expect(’-’); C; D; end else if vstupni sym in (’+’,’-’,’)’,$) then ; else error; end; Šárka Vavrečková




Funkce neterminálů D → ∗CD | /CD | ε procedure D; begin if vstupni sym = ’*’ then begin expect(’*’); C; D; end else if vstupni sym = ’/’ then begin expect(’-’); C; D; end else if vstupni sym in (’+’,’-’,’)’,$) then ; else error; end; Šárka Vavrečková




Vlastnosti metody Výhody: není nutné vytvářet rozkladovou tabulku, třebaže množiny signatur vytvořit musíme, není problém s navázáním sémantické analýzy. Nevýhody: hloubka rekurze může za určitých okolností působit problémy s prostorovou složitostí.





Vlastnosti metody Výhody: není nutné vytvářet rozkladovou tabulku, třebaže množiny signatur vytvořit musíme, není problém s navázáním sémantické analýzy. Nevýhody: hloubka rekurze může za určitých okolností působit problémy s prostorovou složitostí.



Implementace LL(1) překladů

Recommend Documents