Deterministická bezkontextová gramatika - Deterministic context-free grammar

v formální gramatika teorie, deterministické bezkontextové gramatiky (DCFG) plocha správná podmnožina z bezkontextové gramatiky. Jsou podmnožinou bezkontextových gramatik, z nichž lze odvodit deterministické posunovací automaty a generují deterministické bezkontextové jazyky. DCFG jsou vždy jednoznačný a jsou důležitou podtřídou jednoznačných CFG; existují však nedeterministické jednoznačné CFG.

DCFG mají velký praktický zájem, protože je lze analyzovat v lineárním čase a analyzátor lze ve skutečnosti automaticky generovat z gramatiky generátor analyzátoru. Jsou tedy široce používány v celé počítačové vědě. Různé omezené formy DCFG lze analyzovat jednoduššími analyzátory méně náročnými na zdroje, a proto se často používají. Na tyto gramatické třídy se odkazuje podle typu analyzátoru, který je analyzuje, a důležitými příklady jsou LALR, SLR a LL.

Dějiny

V 60. letech 20. století probíhal teoretický výzkum v informatice regulární výrazy a konečné automaty vedlo k objevu, že bezkontextové gramatiky jsou ekvivalentní nedeterministickým pushdown automaty.[1][2][3] Předpokládalo se, že tyto gramatiky zachycují syntaxi počítačových programovacích jazyků. První počítačové programovací jazyky byly v té době ve vývoji (viz Historie programovacích jazyků ) a psaní překladače bylo těžké. Ale pomocí bezkontextové gramatiky aby pomohla automatizovat syntaktickou část kompilátoru, zjednodušila úkol. Deterministické bezkontextové gramatiky byly obzvláště užitečné, protože je bylo možné analyzovat postupně pomocí a deterministický posunovací automat, což byl požadavek kvůli omezením paměti počítače.[4] V roce 1965 Donald Knuth vynalezl Analyzátor LR (k) a dokázal, že pro každý deterministický bezkontextový jazyk existuje gramatika LR (k).[5] Tento analyzátor stále vyžadoval hodně paměti. V roce 1969 Frank DeRemer vynalezl LALR a Jednoduché LR analyzátory, oba založené na analyzátoru LR a které mají výrazně snížené nároky na paměť za cenu menší síly rozpoznávání jazyka. Analyzátor LALR byl silnější alternativou.[6] Tyto dva analyzátory se od té doby široce používají v překladačích mnoha počítačových jazyků. Nedávný výzkum identifikoval metody, kterými lze implementovat kanonické analyzátory LR s dramaticky sníženými požadavky na tabulky oproti Knuthovu algoritmu pro vytváření tabulek.[7]

Viz také

Reference

  1. ^ Chomsky, Noam (1962). Msgstr "Bezkontextové gramatiky a úložiště dolů". Čtvrtletní zpráva o pokroku, výzkumná laboratoř MIT v elektronice. 65: 187–194.
  2. ^ Evey, R.J. (1963). "Aplikace strojů pro ukládání do skladu". 1963 AFIPS Proceedings of the Fall Joint Computer Conference: 215–227.
  3. ^ Schützenberger, Marcel Paul (1963). „Bezkontextové jazyky a push-down automaty“. Informace a kontrola. 6: 246–264. doi:10.1016 / s0019-9958 (63) 90306-1.
  4. ^ Salomaa; D dřevo; S Yu, eds. (2001). Půlstoletí teorie automatů. World Scientific Publishing. 38–39.
  5. ^ Knuth, D. E. (Červenec 1965). „K překladu jazyků zleva doprava“ (PDF). Informace a kontrola. 8 (6): 607–639. doi:10.1016 / S0019-9958 (65) 90426-2. Archivovány od originál (PDF) dne 15. března 2012. Citováno 29. května 2011.
  6. ^ Franklin L. DeRemer (1969). „Praktičtí překladatelé pro jazyky LR (k)“ (PDF). MIT, disertační práce. Archivovány od originál (PDF) dne 2012-04-05.
  7. ^ X. Chen, Měření a rozšiřování analýzy LR (1), Disertační práce University of Hawaii, 2009.