Levá faktorizace

Kombinátorové vytváření parserů je velmi podobné navrhování gramatik. Parsery, které jsou konstruovány v této práci, svým zápisem nejen nahrazují specifikaci pomocí gramatik, ale jsou navíc také funkčními syntaktickými analyzátory. Blízkého vztahu mezi gramatikami a kombinátorovými parsery můžeme využít a osvojit si některé transformace a optimalizační techniky, které byly původně určeny pro gramatiky, ale lze je stejným způsobem použít také pro parsery. Ze zřejmých důvodů pro nás budou zajímavé především transformace LL gramatik. Mezi tyto transformace patří například levá faktorizace, rohová substituce nebo extrakce pravého kontextu. Kromě výše uvedených existuje celá řada dalších.

V řadě případů můžeme pomocí nich jednoduchými transformacemi získat ekvivalentní efektivněji pracující parsery. Vzhledem k rozsahu této problematiky a tématu této práce si zde ukážeme pouze levou faktorizaci, se kterou se při konstrukci parserů setkáme nejčastěji. Problémům s levou rekurzí se budeme částečně věnovat v části .

Programátorskou techniku levé faktorizace parserů si ukážeme na parseru jednoduchého aritmetického výrazu, který přijímá součin nebo podíl dvou čísel a jeho úkolem je vydat výsledek výrazu dle použité operace:

fooLeftFactorization(W):-
 W :->  (double <&>> symbolA("*") <&>> double
          <:
         double <&>> symbolA("/") <&>> double) <@ evalLeftFact.
           
evalLeftFact(X>(Op>Y),R):- Op == '*', R is X*Y ; R is X/Y.

Parser je přímým přepisem úvodních vět, v nichž jsme specifikovali účel jeho použití. Podívejme se na to, jak funguje -- například pro vstup "3.14/2.72". Nejdříve je prvním parserem v alternativní kompozici přijato číslo "3.14". Pak však tato první alternativa selže, protože přijímá součin a nikoli podíl. Dojde tedy k navrácení a v druhé alternativě se analyzuje číslo "3.14" zbytečně znovu. Zbytek vstupu je již tentokrát zpracován bez problémů.

Příčinu tohoto typu navracení můžeme z parserů odstranit jejich levou faktorizací. Rozvětvíme výpočet až v místě, kde to má skutečný význam:

fooLeftFactorization(W):-
 W :->  (double <&>>
           (symbolA("*") <: symbolA("/"))
                                <&>> double) <@ evalLeftFact.

Tato varianta vydává stejné výsledky jako původní parser. Na rozdíl od něj však nedochází při jejím výpočtu k navracení a vstup je zpracován v lineárním čase. Faktorizace druhé části parseru sice nebyla nezbytně nutná, ale jeho zápis zčitelnila.

V následujících kapitolách se budeme snažit vytvářet takové konstruktory parserů, které využívají levou faktorizaci již ve své definici, aby jí programátor nemusel věnovat pozornost v takové míře.

Na příklad z této části navážeme v další kapitole, v níž se budeme věnovat kromě jiného analýze aritmetických výrazů.