Syntaktická analýza – LL(1) parser

17.11.2018 · by Jan Smuda · in .NET, Programování

Derivační strom na obrázku z předchozího článku je to, čeho chci dosáhnout. Jenže jak jej zkonstruovat? Mám seznam tokenů z lexikální analýzy a gramatiku, ale budu potřebovat algoritmus, který dokáže rozhodnout, které pravidlo gramatiky mám použít na konstrukci další větve stromu, pokud mám na vstupu konkrétní token. Těmito a jinými problémy se zabývá syntaktická analýza. V tomto konkrétní případě budu řešit LL(1) syntaktický analyzátor (také se mu říká parser).

Série: Překladače a syntaktické analyzátory

Syntaktická analýza – Trocha teorie úvodem
Syntaktická analýza – Lexikální analyzátor
Syntaktická analýza – Bezkontextová gramatika
Syntaktická analýza – LL(1) parser

LL se mu říká proto, že provádí analýzu shora dolů a zleva doprava. V podstatě konstruuje levou derivaci slova a vyrábí syntaktický strom od kořene, tedy od startovacího neterminálu k listům (terminály). Existují ještě LR parsery ty to dělají opačně. Abych to mohl nějak rozumně naprogramovat je dobré si vyrobit tzv. překladovou (parsovací) tabulku. K tomu budu potřebovat množiny FIRST a FOLLOW. Gramatiku G2 použiju z předchozího článku.

Pro výpočet množiny FIRST, FOLLOW a sestavení prediktivní rozkladové tabulky, můžete využít tuto aplikaci.

Množina FIRST(G)

Množina FIRST určuje množinu terminálních symbolů, kterým může začínat daný neterminál. Algoritmus pro každý neterminál na levé straně pravidla určí množinu terminálních symbolů, kterými může začínat. Toto se provede pro každý neterminál a pravidlo gramatiky G.

Algoritmus výpočtu množiny FIRST(G)

V případě, že G začíná terminálem a, pak výsledkem FIRST(G) je terminál a. G = aX, pak FIRST(G) = {a}
V případě, že G je prázdné slovo ε, pak výsledkem FIRST(G) je prázdné slovo. G = ε, pak FIRST(G) = {ε}
V případě, že G začíná neterminálem X, např. XY, pak jsou dvě možnosti
- Množina FIRST(X) neobsahuje prázdné slovo ε. ε ∉ FIRST(X) pak FIRST(G) = FIRST(Y)
- Množina FIRST(X) obsahuje prázdné slovo ε. ε ∈ FIRST(X) pak FIRST(G) = (FIRST(X) \ {ε}) ∪ FIRST(Y). (FIRST(G) je množina FIRST(X) kromě prázdného slova, sjednocena s výsledkem FIRST(Y))

Výpočet

FIRST(G) = { . , ε }
FIRST(J) = { d, ε }
FIRST(F) = { (, [, s }
FIRST(A) = FIRST(F) = { (, [, s }
FIRST(Y) = FIRST(A) = { (, [, s }
FIRST(H) = FIRST(Y) ∪ { ε } = { (, [, s, ε }
FIRST(X) = d ∪ FIRST(Y) = { d, (, [, s }
FIRST(S) = FIRST(X) = { d, (, [, s }

Množina FOLLOW(G)

Množina FOLLOW určuje množinu terminálních symbolů, které můžou následovat bezprostředně za neterminálem. Opět provedeme pro všechny pravidla v gramatice G.

Algoritmus výpočtu množiny FOLLOW(G)

Pro startovací neterminál S vložím do FOLLOW(S) prázdné slovo ε, FOLLOW(S) = {ε}
Pro pravidla typu X -> aAB je FOLLOW(A) = FIRST(B) \ {ε}
- Pokud do FIRST(B) patří prázdné slovo, ε ∈ FIRST(B), pak FOLLOW(A) = FOLLOW(X) ∪ (FIRST(B) \ {ε})
Pro pravidla X -> aA je FOLLOW(A) = FOLLOW(X)

Výpočet

FOLLOW(E) = { ε } ∪ FOLLOW(G) ∪ { ), ] } = { ε } ∪ FOLLOW(E) ∪ { ), ] } = { ε, ), ] }
FOLLOW(G) = FOLLOW(E) = { ε, ), ] }
FOLLOW(X) = (FIRST(G) \ { ε }) ∪ FOLLOW(E) = { . , ε ) ] } = { . } ∪ { ε, ), ] } = { . , ε, ), ] }
FOLLOW(Y) = FOLLOW(X) ∪ FOLLOW(H) = { . , ε, ), ] } ∪ FOLLOW(Y) = { . , ε, ), ] }
FOLLOW(H) = FOLLOW(Y) = { . , ε, ), ] }
FOLLOW(A) = (FIRST(H) \ { ε }) ∪ FOLLOW(Y) = { (, [, s, . , ε, ), ] }
FOLLOW(J) = FOLLOW(A) = { (, [, s, . , ε, ), ] }
FOLLOW(F) = (FIRST(J) \ { ε }) ∪ FOLLOW(A) = { d, (, [, s, . , ε, ), ] }

Pozn.: Pokud v některém výrazu např. vyjde, že FOLLOW(E) = {ε} ∪ FOLLOW(G) ∪ { ), ] } a FOLLOW(G) = FOLLOW(E) pak dosazením dostávám, že FOLLOW(E) = {ε} ∪ FOLLOW(E) ∪ { ), ] } a to se rovná { ε, ), ] }. Sjednocením dvou stejných množin je tatáž množina.

Množiny FIRST a FOLLOW
TERMINAL	FIRST	FOLLOW
E	d ( [ s	ε ) ]
G	. ε	ε ) ]
X	d ( [ s	. ε ) ]
Y	( [ s	. ε ) ]
H	ε ( [ s	. ε ) ]
A	( [ s	( [ s . ε ) ]
J	d ε	( [ s . ε ) ]
F	( [ s	d ( [ s . ε ) ]

Prediktivní parsovací tabulka

Dalším krokem je sestavení parsovací(rozkladové) tabulky. Na ose x bude množina terminálních symbolů a na ose y bude množina všech neterminálů. Na průniku terminálu a neterminálu v tabulce bude vždy sada (ideálně jedno) pravidel, které se mají v takovém případě použít. Pozice v tabulce bude tedy udána jako M[N, t] kde N je neterminál a t je terminál. Pokud v některém místě není žádné pravidlo, jedná se o chybu překladu. Pokud tabulka obsahuje v jedné buňce více pravidel nejedná se o LL(1) gramatiku a je potřeba ji upravit viz. předchozí článek!

Algoritmus sestavení parsovací tabulky

Pro každé pravidlo X -> N z mojí gramatiky proveď:
Pro každý terminál a z FIRST(N) přidej pravidlo X -> N do M[X, a]
Pokud je N = ε nebo ε ∈ FIRST(N), pak pro každý terminál b z FOLLOW(X) přidej pravidlo X -> N do M[X, b]

Výpočet

E -> XG => FIRST(XG) = FIRST(X) = { d, (, [, s } => M[E, d] = M[E, (] = M[E, [] = M[E, s]
G -> .E => FIRST(.E) = FIRST(.) = { . } => M[G, .]
G -> ε => FIRST(ε) ∪ FOLLOW(G) = { ε } ∪ { ), ] } => M[G, ε] = M[G, )] = M[G, ]]
Provedu pro všechny pravidla a zanesu do tabulky

Parsovací/rozkladová tabulka
	.	d	(	)	[	]	s	ε
E		E -> XG	E -> XG		E -> XG		E -> XG
G	G -> .E			G -> ε		G -> ε		G -> ε
X		X -> dY	X -> Y		X -> Y		X -> Y
Y			Y -> AH		Y -> AH		Y -> AH
H	H -> ε		H -> Y	H -> ε	H -> Y	H -> ε	H -> Y	H -> ε
A			A -> FJ		A -> FJ		A -> FJ
J	J -> ε	J -> d	J -> ε	J -> ε	J -> ε	J -> ε	J -> ε	J -> ε
F			F -> (E)		F -> [E]		F -> s

Prediktivní analýza

Prediktivní analýza je nerekurzivní algoritmus, využívající zásobníkový automat a prediktivní rozkladovou tabulku. Takovýto zásobníkový automat má čtyři části. Vstupní páska, kde se nachází seznam vstupních tokenů (vstupní věta). Zásobník pro ukládání půběžného stavu algoritmu. Prediktivní rozkladovou tabulku, a nakonec výstupní pásku, kde jsou průběžně ukládána pravidla, která byla při analýze použita. Na konci algoritmu obsahuje výstupní páska levou derivaci slova nebo dojde k syntaktické chybě.

Tento algoritmus má oproti následujícímu (rekurzivnímu sestupu) jednu podstatnou výhodu. Je totiž obecně aplikovatelný na jakoukoliv (LL(1)) gramatiku kterou do něj vložím. To může být výhoda v případě, že chci mít obecný způsob, jak vyhodnocovat gramatiky. Stačí mi vyměnit rozkladovou tabulku a algoritmus bude funkční. Většina knihoven a generátorů parserů používá obdobný algoritmus.

Algoritmus derivace slova zásobníkovým automatem

Inicializace – na zásobník se uloží počáteční neterminál a prázdné slovo ε. Vstupní páska obsahuje celé slovo (složené z terminálů t) a prázdné slovo ε.
Načte terminál t ze vstupní pásky. Pokud jsem přečetl celé slovo, vracím pro každé další čtení znak ε.
1. Pokud je na vrcholu zásobníku neterminál N, vyjme neterminál N ze zásobníku a provede se operace Expand podle pravidla z překladové tabulky na souřadnicích M[N, t].
  1. Pokud na souřadnicích M[N, t] existuje pravidlo, vloží se na zásobník. Symboly pravidla je potřeba na zásobník vložit od konce! Symbol ε se nevkládá!
  2. Pokud na souřadnicích M[N, t] neexistuje pravidlo, jedná se o syntaktickou chybu.
2. Pokud je na vrcholu zásobníku terminál u, porovná se s terminálem t načteným ze vstupní pásky.
  1. Pokud t = u, provede se operace Pop, která odstraní u z vrcholu zásobníku a pokračuje bodem 2, načtením nového terminálu t.
  2. Pokud se terminály liší došlo k syntaktické chybě.
3. Pokud je na vrcholu zásobníku symbol ε a na vstupu také symbol ε, je syntaktická analýza úspěšně dokončena.

Derivace slova H2O

Než se podíváte do tabulky s postupem, je potřeba vyjasnit několik věcí. V gramatice nemám terminální symboly pro vodík H a kyslík O ani pro číslici 2. Místo toho tam mám zástupné terminály s a d. Je to pro zjednodušení tabulky. Pokud je tedy na vstupu nějaký symbol z periodické soustavy prvků je potřeba se dívat na sloupec s terminálem s. Pokud je na vstupu číslo tak na sloupec s terminálem d. Dále mi při použití symbolů pro vodík a kyslík vzniká konflikt mezi vodíkem H a neterminálem z gramatiky. Proto jsem použil místo symbolů malá písmena. H2O=h2o=sds

Derivace slova zásobníkovým automatem
Krok	Nepřečteno	Načtený term.	Zásobník	Operace	Pravidlo
1.	h2oε	h	Eε	Expand(E, h)	E -> XG
2.	h2oε	h	XGε	Expand(X, h)	X -> Y
3.	h2oε	h	YGε	Expand(Y, h)	Y -> AH
4.	h2oε	h	AHGε	Expand(A, h)	A -> FJ
5.	h2oε	h	FJHGε	Expand(F, h)	F -> h
6.	h2oε	h	hJHGε	Pop
7.	2oε	2	JHGε	Expand(J, 2)	J -> 2
8.	2oε	2	2HGε	Pop
9.	oε	o	HGε	Expand(H, o)	H -> Y
10.	oε	o	YGε	Expand(Y, o)	Y -> AH
11.	oε	o	AHGε	Expand(A, o)	A -> FJ
12.	oε	o	FJHGε	Expand(F, o)	F -> o
13.	oε	o	oJHGε	Pop
14.	ε	ε	JHGε	Expand(J, ε)	J -> ε
15.	ε	ε	HGε	Expand(H, ε)	H -> ε
16.	ε	ε	Gε	Expand(G, ε)	G -> ε
17.	ε	ε	ε	Accept

Levá derivace slova H2O podle gramtiky G1 je následující: E -> XG -> YG -> AHG -> FJHG -> hJHG ->h2HG -> h2YG -> h2AHG -> h2FJHG -> h2oJHG -> h2oHG -> h2oG -> h2o

Rekurzivní sestup

Postup implementace analýzy rekurzivním sestupem je poměrně jednoduchý. Za každý neterminál z mojí gramatiky vyrobím jednu funkci, která bude provádět rozklad podle pravidel překladové tabulky. Pokud tedy začínám (metoda Analyze) musím načít první token a zavolat funkci Fce_E, která odpovídá neterminálu E. Z překladové tabulky zjistím, že pokud je načtený token otevírací závorka, symbol nebo číslice pak můžu provést volání funkcí Fce_X a Fce_G. Pořadí volání je samozřejmě důležité! Pokud je načtený token jiného typu jedná se o syntaktickou chybu.

V případě, že narazím pravidlo začínající terminálem je to obdobné funkci pop z předchozí metody. Porovnám aktuální token s povolenými terminály a pokud se některý shoduje, použiju pravidlo a načtu další token. Např. ve funkci Fce_G pokud je aktuální token separator, načtu další token a volám funkci Fce_E podle pravidla G -> .E.

Pokud gramatika povoluje i ε přechody pak v místě, kde je v tabulce pravidlo typu N -> ε se nedělá vůbec nic! Taky se mi může stát, že načtu prázdné slovo ε, ale jsem ještě zanořen na nějaké úrovni volání funkcí. V mé implementaci představuje ε hodnota null. Lexer funguje tak, že když přečte celý řetězec, každé další čtení vrací null. V takových případech se normálně provádí operace na souřadnicích M[N, ε], kde N je neterminál (funkce).

Nakonec je ještě potřeba zkontrolovat, jestli byl přečtený celý řetězec přijat nebo ne. V předchozí metodě se porovnával symbol na vrcholu zásobníku (ε) s aktuálně načteným symbolem (ε). Pokud se rovnaly pak bylo slovo přijato. Tentokráte zásobník nemám, ale to nevadí. Stav zásobníku z předchozí metody je zde reprezentován úrovní rekurze. Pokud tedy program vystoupá až do funkce Analyze, tak je to jako by byl zásobník prázdný, nebo na něm byl znak ε. Stačí mi tak zkontrolovat poslední načtený token. Pokud je roven null slovo bylo přijato.

    public bool Analyze()
    {
        try
        {
            GetNextToken();
            Fce_E();
            return _currentToken == null;
        }
        catch
        {
            return false;
        }
    }

    private void Fce_E()
    {
        if (_currentToken.Type == TokenType.RoundBracketOpen ||
            _currentToken.Type == TokenType.SquareBracketOpen ||
            _currentToken.Type == TokenType.Symbol ||
            _currentToken.Type == TokenType.Number)
        {
            Fce_X();
            Fce_G();
        }
        else
        {
            throw new NotSupportedException("Syntax error");
        }
    }

    private void Fce_G()
    {
        if (_currentToken == null ||
            _currentToken.Type == TokenType.RoundBracketClose ||
            _currentToken.Type == TokenType.SquareBracketClose)
        {
            //Nothing
        }
        else if (_currentToken.Type == TokenType.Separator)
        {
            GetNextToken();
            Fce_E();
        }            
        else
        {
            throw new NotSupportedException("Syntax error");
        }
    }
   
    private void Fce_F()
    {
        if (_currentToken.Type == TokenType.RoundBracketOpen)
        {
            GetNextToken();
            Fce_E();

            if (_currentToken.Type == TokenType.RoundBracketClose)
            {
                GetNextToken();
            }
            else
            {
                throw new NotSupportedException("Syntax error");
            }
        }
        else if (_currentToken.Type == TokenType.SquareBracketOpen)
        {
            GetNextToken();
            Fce_E();

            if (_currentToken.Type == TokenType.SquareBracketClose)
            {
                GetNextToken();
            }
            else
            {
                throw new NotSupportedException("Syntax error");
            }
        }
        else if (_currentToken.Type == TokenType.Symbol)
        {
            GetNextToken();
        }
        else
        {
            throw new NotSupportedException("Syntax error");
        }
    }

public bool Analyze()

{

try

{

GetNextToken();

Fce_E();

return _currentToken == null;

}

catch

{

return false;

}

private void Fce_E()

{

if (_currentToken.Type == TokenType.RoundBracketOpen ||

_currentToken.Type == TokenType.SquareBracketOpen ||

_currentToken.Type == TokenType.Symbol ||

_currentToken.Type == TokenType.Number)

{

Fce_X();

Fce_G();

}

else

{

throw new NotSupportedException("Syntax error");

}

private void Fce_G()

{

if (_currentToken == null ||

_currentToken.Type == TokenType.RoundBracketClose ||

_currentToken.Type == TokenType.SquareBracketClose)

{

//Nothing

}

else if (_currentToken.Type == TokenType.Separator)

{

GetNextToken();

Fce_E();

}

else

{

throw new NotSupportedException("Syntax error");

}

private void Fce_F()

{

if (_currentToken.Type == TokenType.RoundBracketOpen)

{

GetNextToken();

Fce_E();

if (_currentToken.Type == TokenType.RoundBracketClose)

{

GetNextToken();

}

else

{

throw new NotSupportedException("Syntax error");

}

else if (_currentToken.Type == TokenType.SquareBracketOpen)

{

GetNextToken();

Fce_E();

if (_currentToken.Type == TokenType.SquareBracketClose)

{

GetNextToken();

}

else

{

throw new NotSupportedException("Syntax error");

}

else if (_currentToken.Type == TokenType.Symbol)

{

GetNextToken();

}

else

{

throw new NotSupportedException("Syntax error");

}

Závěr

Syntaktický analyzátor jsem sestavil, ale zatím umí chemické vzorce pouze validovat. V příštím článku ukážu, jak ho upravit, aby vytvářel derivační strom a podívám se i na to, jakým způsobem realizovat průchod stromem a provést jednotlivé výpočty ve vzorci.

Zdroje

Štítky: Algoritmy, Teoretická informatika

Syntaktická analýza – LL(1) parser