LL gramatika - LL grammar

int v; main () {
„a jde o výběr pravidla pro odvození neterminálu“Stmt
". Podíváme se pouze na první token hledací hlavy"proti
„, nemůže rozhodnout, která z obou alternativ pro“Stmt
"vybrat, protože jsou možná dvě vstupní pokračování. Mohou být diskriminována nahlédnutím do druhého tokenu dopředného pohledu (žluté pozadí)."v teorie formálního jazyka, an LL gramatika je bezkontextová gramatika to může být analyzován podle Analyzátor LL, který analyzuje vstup z Left doprava a konstruuje a Leftmost derivation věty (tedy LL ve srovnání s Analyzátor LR který vytváří derivaci zcela vpravo). Jazyk, který má gramatiku LL, je znám jako Jazyk LL. Tyto tvoří podmnožiny deterministické bezkontextové gramatiky (DCFG) a deterministické bezkontextové jazyky (DCFL). Jeden říká, že daná gramatika nebo jazyk „je gramatikou / jazykem LL“ nebo jednoduše „je LL“, což znamená, že je v této třídě.
Analyzátory LL jsou analyzátory založené na tabulce, podobné analyzátorům LR. LL gramatiky lze alternativně charakterizovat jako přesně ty, které lze analyzovat pomocí a prediktivní analyzátor - a analyzátor rekurzivního sestupu bez ustoupit - a ty lze snadno napsat ručně. Tento článek je o formálních vlastnostech gramatik LL; pro analýzu, viz Analyzátor LL nebo analyzátor rekurzivního sestupu.
Formální definice
Konečný případ
Vzhledem k přirozenému číslu ,A bezkontextová gramatika je LL (k) gramatika -li
- pro každý řetězec symbolu terminálu délky až symboly,
- pro každý neterminální symbol , a
- pro každý řetězec symbolu terminálu ,
existuje nanejvýš jedno produkční pravidlo takové, že pro některé řetězce terminálových symbolů ,
- řetězec lze odvodit od počátečního symbolu ,
- lze odvodit z po prvním použití pravidla , a
- první symboly a ze dne souhlasit.[2]
Alternativní, ale ekvivalentní formální definice je následující: je LL (k) gramatika if, pro libovolné derivace
když první symboly souhlasím s těmi z , pak .[3][4]
Neformálně, když je analyzátor odvozen , s jeho nejvíce vlevo neterminální a již spotřebované ze vstupu, pak při pohledu na to a koukat na další symboly analyzátoru může s jistotou identifikovat produkční pravidlo pro .
Když je identifikace pravidla možná i bez zohlednění minulého vstupu , pak se gramatika nazývá a silná LL (k) gramatika.[5] Ve formální definici silné LL (k) gramatika, univerzální kvantifikátor pro je vynechán a je přidán do kvantifikátoru "pro některé" pro Pro každou LL (k) gramatika, strukturálně ekvivalentní silná LL (k) gramatiku lze sestavit.[6]
Třída LL (k) jazyky tvoří přísně rostoucí posloupnost množin: LL (0) ⊊ LL (1) ⊊ LL (2) ⊊….[7] Je rozhodné, zda je daná gramatika G je LL (k), ale nelze rozhodnout, zda je libovolná gramatika LL (k) pro některé k. Je také rozhodující, zda daný LR (k) gramatika je také LL (m) gramatika pro některé m.[8]
Každý LL (k) gramatika je také LR (k) gramatika. An ε-free LL (1) grammar is also a SLR (1) grammar. Gramatika LL (1) se symboly, které mají prázdné i neprázdné derivace, je také gramatikou LALR (1). Gramatika LL (1) se symboly, které mají pouze prázdnou derivaci, může nebo nemusí být LALR (1).[9]
LL gramatiky nemohou obsahovat pravidla obsahující rekurze doleva.[10] Každá LL (k) gramatiku, která je bez ε, lze převést na ekvivalentní LL (k) gramatika v Greibachova normální forma (který podle definice nemá pravidla s levou rekurzí).[11].
Pravidelný případ
Nechat být terminální abeceda. Podmnožina je běžná sada pokud je to běžný jazyk přes . A rozdělit z se nazývá a běžný oddíl pokud pro každého sada je pravidelný.
Nechat být bezkontextovou gramatikou a nechat být pravidelným oddílem . Říkáme to je LL () gramatika if, pro libovolné derivace
takhle z toho vyplývá, že . [12]
Gramatika G se říká, že je LL-regular (LLR), pokud existuje pravidelný oddíl takhle G je LL ().
LLR gramatiky nejsou nutně nejednoznačné a nejsou levo rekurzivní.
Každý LL (k) gramatika je LLR. Každý LL (k) gramatika je deterministická, ale existuje LLR gramatika, která není deterministická.[13] Proto je třída gramatik LLR přísně větší než sjednocení LL (k) pro každého k.
Je rozhodné, zda vzhledem k běžnému oddílu , daná gramatika je LL (). Nelze však rozhodnout, zda jde o libovolnou gramatiku G je LLR. To je způsobeno tím, že při rozhodování, zda jde o gramatiku G generuje regulární jazyk, který by byl nezbytný pro nalezení regulárního oddílu pro G, lze snížit na Problém s korespondencí.
Každá gramatika LLR je pravidelná LR (LRR, odpovídající ekvivalent pro LR (k) gramatiky), ale existuje gramatika LR (1), která není LLR.[14]
Historicky gramatiky LLR následovaly po vynálezu gramatik LRR. Vzhledem k normálnímu oddílu a Mooreův stroj mohou být konstruovány tak, aby transdukovaly analýzu zprava doleva a identifikovaly případy pravidelných produkcí. Jakmile to bylo provedeno, analyzátor LL (1) je dostatečný pro zpracování transdukovaného vstupu v lineárním čase. Analyzátory LLR tedy zvládnou třídu gramatik striktně větší než LL (k) analyzátory, přestože jsou stejně efektivní. Přesto teorie LLR nemá žádné zásadní aplikace. Jedním z možných a velmi pravděpodobných důvodů je, že zatímco pro LL existují generativní algoritmy (k) a LR (k) analyzátory, problém s generováním analyzátoru LLR / LRR je nerozhodnutelný, pokud si předem nezadáte běžný oddíl. Ale i problém konstrukce vhodného regulárního oddílu dané gramatiky je nerozhodnutelný.
Jednoduché deterministické jazyky
Bezkontextová gramatika se nazývá jednoduché deterministické,[15] nebo prostě jednoduchý,[16] -li
- to je v Greibachova normální forma (tj. každé pravidlo má formu ), a
- různé pravé strany pro stejný neterminál vždy začněte s různými terminály .
Sada řetězců se nazývá jednoduchý deterministický nebo prostý jazyk, pokud má jednoduchou deterministickou gramatiku.
Třída jazyků s gramatikou LL (1) bez ε v Greibachově normálním tvaru se rovná třídě jednoduchých deterministických jazyků.[17]Tato jazyková třída zahrnuje běžné sady neobsahující ε.[16] Rovnocennost je pro ni rozhodující, zatímco zahrnutí nikoli.[15]
Aplikace
LL gramatiky, zejména gramatiky LL (1), mají velký praktický zájem, protože je snadné je analyzovat, buď analyzátory LL, nebo analyzátory rekurzivního sestupu, a mnoho počítačové jazyky[vyjasnit ] jsou z tohoto důvodu navrženy jako LL (1). Jazyky založené na gramatikách s vysokou hodnotou k byly tradičně zvažovány[Citace je zapotřebí ] je obtížné analyzovat, i když to je nyní méně pravdivé vzhledem k dostupnosti a širokému použití[Citace je zapotřebí ] generátorů syntaktických analyzátorů podporujících LL (k) gramatiky pro libovolné k.
Viz také
- Porovnání generátorů syntaktických analyzátorů pro seznam analyzátorů LL (k) a LL (*)
Poznámky
- ^ Kernighan a Ritchie 1988, Příloha A.13 „Gramatika“, s. 193 a násl. Horní část obrázku ukazuje zjednodušený výňatek v EBNF -jako notace ..
- ^ Rosenkrantz & Stearns (1970, str. 227). Def.1. Autoři případ neuvažují k=0.
- ^ kde ""označuje derivovatelnost derivacemi zcela vlevo a , , a
- ^ Waite & Goos (1984, str. 123) Def. 5.22
- ^ Rosenkrantz & Stearns (1970, str. 235) Def.2
- ^ Rosenkrantz & Stearns (1970, str. 235) Věta 2
- ^ Rosenkrantz & Stearns (1970, str. 246-247): Použití „"to denote" nebo ", sada řetězců má , ale bez ε gramatika, pro každého .
- ^ Rosenkrantz & Stearns (1970, str. 254–255)
- ^ Beatty (1982)
- ^ Rosenkrantz & Stearns (1970 241) Lemma 5
- ^ Rosenkrantz & Stearns (1970, str. 242) Věta 4
- ^ Poplawski, David (1977). "Vlastnosti jazyků LL-Regular". Purdue University. Citovat deník vyžaduje
| deník =
(Pomoc) - ^ David A. Poplawski (srpen 1977). Vlastnosti běžných jazyků LL (Technická zpráva). Purdue University, Ústav výpočetní techniky.
- ^ David A. Poplawski (srpen 1977). Vlastnosti běžných jazyků LL (Technická zpráva). Purdue University, Ústav výpočetní techniky.
- ^ A b Korenjak a Hopcroft (1966)
- ^ A b Hopcroft & Ullman (1979, str. 229) Cvičení 9.3
- ^ Rosenkrantz & Stearns (1970, str. 243)
Zdroje
- Beatty, J. C. (1982). „O vztahu mezi gramatikami LL (1) a LR (1)“ (PDF). Deník ACM. 29 (4 (říjen)): 1007–1022. doi:10.1145/322344.322350.
- Hopcroft, John E .; Ullman, Jeffrey D. (1979). Úvod do teorie automatů, jazyků a výpočtu. Addison-Wesley. ISBN 978-0-201-02988-8.
- Kernighan, Brian W .; Ritchie, Dennis M. (duben 1988). Programovací jazyk C.. Softwarová řada Prentice Hall (2. vydání). Englewood Cliffs / NJ: Prentice Hall. ISBN 978-013110362-7.
- Korenjak, A.J .; Hopcroft, J. E. (1966). Msgstr "Jednoduché deterministické jazyky". Konf. IEEE Rec. 7. Ann. Symp. o teorii přepínání a automatů (SWAT). IEEE Pub. Č. 16-C-40. s. 36–46. doi:10.1109 / SWAT.1966.22.
- Parr, T .; Fisher, K. (2011). "LL (*): Založení generátoru analyzátoru ANTLR" (PDF). Oznámení ACM SIGPLAN. 46 (6): 425–436. doi:10.1145/1993316.1993548.
- Rosenkrantz, D. J .; Stearns, R. E. (1970). "Vlastnosti deterministických gramatik shora dolů". Informace a kontrola. 17 (3): 226–256. doi:10.1016 / s0019-9958 (70) 90446-8.
- Waite, William M .; Goos, Gerhard (1984). Konstrukce kompilátoru. Texty a monografie v informatice. Heidelberg: Springer. ISBN 978-3-540-90821-0.
Další čtení
- Sippu, Seppo; Soisalon-Soininen, Eljas (1990). Teorie analýzy: Analýza LR (k) a LL (k). Springer Science & Business Media. ISBN 978-3-540-51732-0.