Levá rekurze

Levá rekurze v teorii formálních jazyků v matematické informatice je speciální případ rekurze, kdy lze určitý neterminální symbol přepsat v jednom nebo více krocích na řetězec, který obsahuje stejný neterminální symbol. O levou rekurzi se jedná, pokud je příslušný neterminál na začátku výsledného řetězce. Lze také říct, že určitý řetězec je rozpoznán jako část jazyka tak, že se skládá z řetězce z téhož jazyka (vlevo) a zbytku, sufixu (vpravo). Například ve výseku gramatiky pro aritmetický výraz: $E\Rightarrow E+T$, $E\Rightarrow T$, $T\Rightarrow konstanta$, je neterminál E zleva rekurzivní. Výraz $1+2+3$ je rozpoznán jako součet, protože jej lze rozložit na součet $1+2$ a sufix $+3$.

V termínech bezkontextových gramatik neterminální symbol obsahuje levou rekurzi, jestliže první symbol v jednom z jeho pravidel je samotný (v případě přímé levé rekurze) nebo lze získat řetězec obsahující tentýž symbol nějakou posloupností substitucí (v případě nepřímé levé rekurze).

Definice

Gramatika obsahuje levou rekurzi právě tehdy, když existuje neterminální symbol $A$, ze kterého lze odvodit větnou formu, která začíná původním neterminálem. Symbolicky,

$A{\Rightarrow }^{+}A\alpha$,

kde ${\Rightarrow }^{+}$ je operace provedení jedné nebo více substitucí a $\alpha$ je libovolný řetězec terminálních a neterminálních symbolů.

Přímá levá rekurze

O přímou levou rekurzi se jedná, když podmínky z definice rekurze jsou splněny již jedinou substitucí. Vyžaduje pravidlo tvaru

$A\to A\alpha$

kde $\alpha$ je řetězec neterminálů a terminálů. Například pravidlo

$𝐸𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛\to 𝐸𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛+𝑇𝑒𝑟𝑚$

je přímo s levou rekurzí. Analyzátor s rekurzivním sestupem zleva doprava pro toto pravidlo může být následující:

funkce Expression()
{
    Expression();  match('+');  Term();
}

Tento kód způsobí při svém provedení nekonečnou rekurzi.

Nepřímá levá rekurze

O nepřímou levou rekurzi se jedná, když jsou podmínky z definice rekurze splněny až při použití více než jednoho přepsání. Má za následek sada pravidel následující vzorek

$A_0\to {\beta }_0{A}_1{\alpha }_0$

$A_1\to {\beta }_1{A}_2{\alpha }_1$

$\cdots$

$A_n\to {\beta }_n{A}_0{\alpha }_n$

kde ${\beta }_0,{\beta }_1,\dots ,{\beta }_n$ jsou řetězce, které všechny mohou dávat prázdný řetězec, a ${\alpha }_0,{\alpha }_1,\dots ,{\alpha }_n$ jsou libovolné řetězce. Derivace

$A_0\Rightarrow {\beta }_0{A}_1{\alpha }_0{\Rightarrow }^{+}{A}_1{\alpha }_0\Rightarrow {\beta }_1{A}_2{\alpha }_1{\alpha }_0{\Rightarrow }^{+}\cdots {\Rightarrow }^{+}{A}_0{\alpha }_n\dots {\alpha }_1{\alpha }_0$

pak dává $A_0$ jako první symbol v poslední větné formě.

Odstraňování levé rekurze

Levá rekurze často představuje problém pro analyzátory, buď protože vede k nekonečné rekurzi (v případě většiny analyzátorů shora dolů) anebo protože očekávají pravidla v normální formě, která rekurzi zakazuje (jako v případě mnoha analyzátorů zdola nahoru, včetně CYK algoritmu). Proto se gramatiky často upravují, aby levou rekurzi neobsahovaly.

Odstraňování přímé levé rekurze

Následující algoritmus slouží pro odstranění přímé levé rekurze. Existuje několik jeho vylepšení. Pro každý neterminál $A$ s levou rekurzí, zahodíme všechna pravidla tvaru $A\to A$ a ostatní pravidla tvaru:

$A\to A{\alpha }_1\mid \dots \mid A{\alpha }_n\mid {\beta }_1\mid \dots \mid {\beta }_m$

kde:

• $\alpha$ jsou neprázdné řetězce neterminálů a terminálů a
• $\beta$ jsou řetězce neterminálů a terminálů, které nezačínají symbolem $A$.

nahradíme dvěma množinami pravidel, jednou se symbolem $A$ na levé straně:

$A\to {\beta }_1{A}^{\prime }\mid \dots \mid {\beta }_m{A}^{\prime }$

a druhou s přidaným neterminálním symbolem $A^{\prime }$ (obvykle nazývaným „zakončení“ nebo "zbytek"):

$A^{\prime }\to {\alpha }_1{A}^{\prime }\mid \dots \mid {\alpha }_n{A}^{\prime }\mid ϵ$

Uvedený postup se opakuje, dokud nezůstává žádná přímá levá rekurze.

Jako příklad uvažujme sadu pravidel

$𝐸𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛\to 𝐸𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛+𝐸𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛\mid 𝐼𝑛𝑡𝑒𝑔𝑒𝑟\mid 𝑅𝑒𝑡𝑒𝑧𝑒𝑐$

kterou lze přepsat, aby se zabránilo levé rekurzi jako

$𝐸𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛\to 𝐼𝑛𝑡𝑒𝑔𝑒𝑟{𝐸𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛}^{\prime }\mid 𝑅𝑒𝑡𝑒𝑧𝑒𝑐{𝐸𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛}^{\prime }$

${𝐸𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛}^{\prime }\to +𝐸𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛{𝐸𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛}^{\prime }\mid ϵ$

Odstraňování veškeré levé rekurze

Topologickým setříděním neterminálů lze výše uvedený postup rozšířit na odstraňování nepřímé levé rekurze:

Vstup Gramatika: množina neterminálů $A_1,\dots ,A_n$ a jejich pravidel

Výstup Upravená gramatika generující stejný jazyk, ale bez levé rekurze

1. Pro každý neterminál $A_i$:
   1. Opakuj, dokud iterace mění gramatiku:
      1. Pro každé pravidlo $A_i\to {\alpha }_i$, ${\alpha }_i$ je řetězec terminálů a neterminálů:
         1. Jestliže ${\alpha }_i$ začíná neterminálem $A_j$ a $j<i$:
            1. Nechť ${\beta }_i$ jsou ${\alpha }_i$ bez jeho úvodní $A_j$.
            2. Odstraň pravidlo $A_i\to {\alpha }_i$.
            3. Pro každé pravidlo $A_j\to {\alpha }_j$:
               1. Přidej pravidlo $A_i\to {\alpha }_j{\beta }_i$.
   2. Odstraň přímou levou rekurzi pro $A_i$, jak je popsáno výše.

Všimněte si, že tento algoritmus je velmi citlivý na pořadí neterminálů; jeho optimalizace se často zaměřují na správný výběr tohoto řazení.

Skryté nástrahy

Ačkoli výše uvedené transformace nemění generovaný jazyk, mohou měnit derivační strom, na kterém závisí struktura řetězce. Existují postupy, které pomocí stromových transformací mohou vést k původním výsledkům. Při vynechání tohoto kroku však rozdíly mohou změnit sémantiku analýzy.

Obzvláště zranitelná je asociativita; zleva asociativní operátory jsou do nové gramatiky převedeny jako zprava asociativní. Pokud například uvažujeme následující gramatiku:

$𝐸𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛\to 𝐸𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛-𝑇𝑒𝑟𝑚\mid 𝑇𝑒𝑟𝑚$

$𝑇𝑒𝑟𝑚\to 𝑇𝑒𝑟𝑚*𝐹𝑎𝑐𝑡𝑜𝑟\mid 𝐹𝑎𝑐𝑡𝑜𝑟$

$𝐹𝑎𝑐𝑡𝑜𝑟\to (𝐸𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛)\mid 𝐼𝑛𝑡𝑒𝑔𝑒𝑟$

standardní transformace pro odstranění levé rekurze dává následující:

$𝐸𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛\to 𝑇𝑒𝑟𝑚{𝐸𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛}^{\prime }$

${𝐸𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛}^{\prime }\to -𝑇𝑒𝑟𝑚{𝐸𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛}^{\prime }\mid ϵ$

$𝑇𝑒𝑟𝑚\to 𝐹𝑎𝑐𝑡𝑜𝑟{𝑇𝑒𝑟𝑚}^{\prime }$

${𝑇𝑒𝑟𝑚}^{\prime }\to *𝐹𝑎𝑐𝑡𝑜𝑟{𝑇𝑒𝑟𝑚}^{\prime }\mid ϵ$

$𝐹𝑎𝑐𝑡𝑜𝑟\to (𝐸𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛)\mid 𝐼𝑛𝑡𝑒𝑔𝑒𝑟$

Syntaktická analýza řetězce „1 - 2 - 3“ LALR analyzátorem podle původní gramatiky (LALR analyzátor umožňuje analýzu gramatik s levou rekurzí) dává derivační strom:

Analýza opakovaného odčítání s levou rekurzí

Tento derivační strom seskupuje termy odleva, což dává správnou sémantiku (1 - 2) - 3.

Syntaktická analýza podle upravené gramatiky dává derivační strom

Analýza opakovaného odčítání obsahující pravou rekurzi

,

který je při správné interpretaci 1 + (-2 + (-3)) také správný, ale méně věrný vstupu, a implementace některých operátorů může být mnohem obtížnější. Všimněte si, že se termy vpravo vyskytují hlouběji ve stromě, podobně jako v gramatice s pravou rekurzí jejich úpravou na 1 - (2 - 3).

Ošetření levé rekurze při analýze shora dolů

Formální gramatika, která obsahuje levou rekurzi, nemůže být analyzována LL(k)-analyzátorem nebo jiným naivním analyzátorem s rekurzivním sestupem, pokud není zkonvertována na tvar slabě ekvivalentní gramatiky s pravou rekurzí. Naproti tomu, levá rekurze je upřednostňovaná pro LALR analyzátory, protože vede k menšímu využívání zásobníku než pravá rekurze. Rafinovanější analyzátory shora dolů však mohou implementovat obecné bezkontextové gramatiky pomocí omezení. V roce 2006 popsali Frost a Hafiz algoritmus, který je použitelný pro nejednoznačné gramatiky s přímou levou rekurzí. Tento algoritmus v roce 2007 rozšířil Frost, Hafiz a Callaghan na úplný algoritmus analýzy, který dovoluje nepřímou i přímou levou rekurzi v polynomiálním čase a pro vysoce nejednoznačné gramatiky generuje kompaktní reprezentaci polynomiální velikosti pro potenciálně exponenciální funkci počtu stromů analýzy. Autoři pak implementovali algoritmus jako sadu kombinátorů syntaktických analyzátorů napsaný v jazyce Haskell.

Odkazy

Související články

• Koncová rekurze

Externí odkazy

• CMU lecture on left recursion Šablona:Wayback
• Practical Considerations for LALR(1) Grammars
• X-SAIGA – eXecutable SpecificAtIons of GrAmmars