Kompilátory: Jaký je rozdíl mezi analyzátory LL (0) a LR (0). Existuje něco jako parsery LL (0)?


Odpověď 1:

Zdá se, že tato otázka je zaměřena na analyzátory LL (0), takže je definujme. Analyzátor LL (0) analyzuje zleva doprava pomocí 0 žetonů na začátku výroby, aby určil, která produkce se má použít. Co to znamená, že tokeny 0 znamenají, že syntaktický analyzátor nemůže použít analyzovaný text k určení, která produkce se má použít. To znamená, že analyzátor nemůže provádět žádné volby. Musí vědět, než začne analyzovat přesně pořadí tokenů, které bude analyzovat. Posloupnost tokenů musí být pevná, což znamená, že může být pouze jedna sekvence, kterou bude analyzátor analyzovat. Můžete tedy mít syntaktický analyzátor, který přijímá „Ahoj svět!“ s gramatikou jako je tato:

cíl: „Ahoj“ vykřičník „svět“;

Povšimněte si, že jediné povolené variace jsou, jak lexer odpovídá tokenům.

(Doufám, že zápis je zřejmý - je to v podstatě ten, který používám v Yacc ++. Citované řetězce jsou tokeny, stejně jako identifikátory, které nejsou definovány.)

Analyzátor vždy očekává přesně stejnou sekvenci tokenů. Nemusí to mít pouze jedno pravidlo, jak to udělal náš první příklad. Mohlo by to vypadat takto.

cíl: hello-part whitespace end-part;

hello-part: hello1;

hello1: "Ahoj";

end-part: world-last last-part;

část světa: „svět“;

poslední část: "!";

Všimněte si však, že žádné z pravidel nemá žádné operátory „nebo“ (|) a na non-terminál platí pouze jedno pravidlo. To umožňuje analyzátoru, aby věděl, jak se shoduje s každým pravidlem bez použití jakýchkoli rozlišovacích tokenů (tokenů, které volí, jakým způsobem bude syntaktický analyzátor jít), což způsobí gramatiku LL (0).

Nyní je možné použít rekurzivní produkci a přesto mít gramatiku LL (0)? Odpověď je ne". Uvidíme, co se stane, pokud budeme mít rekurzivní pravidlo.

cíl: "x" cíl "y";

Pamatujte, že na non-terminál máme povoleno pouze jedno pravidlo a žádný operátor „nebo“. Když se tedy dostaneme k rekurzivnímu vyvolání cíle, musíme nás vzít na cestu, kam se znovu dostaneme k tomuto rekurzivnímu vyvolání, nekonečné smyčce. Dokažte sami, nezáleží na tom, jak toto vyvolání hnízdíme nebo zda je rekurze nepřímá. Vždy to povede k nekonečné smyčce.

Gramatika LL (0) tedy musí analyzovat konečný seznam tokenů, přesně jeden konečný seznam (vždy stejný seznam).

Všimněte si rozdílu od významu LR (0). Analyzátor LR (k) může používat jakékoli tokeny (tolik, kolik se mu líbí) v produkci k rozlišení, plus tokeny k z kontextu, když se výroba sníží, aby určila, zda by se měla snížit. V případě LR (0) nemůže použít žádné další tokeny k určení, zda se má zmenšit. Musí se jednoduše rozhodnout na základě tokenů v pravidle, které je redukováno. Zde je jednoduchá gramatika LR (0):

cíl: "x" | "(" fotbalová branka ")";

Tato gramatika analyzuje „x“ obklopené určitým počtem závorek. Všimněte si, že může použít token "x" a token "(" pro rozhodnutí, které pravidlo se použije. 0 v LR (0) neomezuje použití tokenů v rámci pravidla, jako to dělá 0 v LL (0). Jediné, co omezuje, je použití tokenů (kontextu, po pravidlu v nějakém použití non-terminálu) při rozhodování o redukci. Tato gramatika nepotřebuje žádný kontext, aby se rozhodla redukovat. "x" za sekundu se zmenší po zobrazení ")". Tokeny v rámci pravidla určují přesně, kdy by se pravidlo mělo snížit.


Odpověď 2:

Parsery LL (0) znamenají, že zpracovávají token tokenů zleva doprava a používají derivaci zleva bez výhledu dopředu. Teoreticky jsou možné analyzátory LL (0), ale i když existují, nevidím pro ně moc využití. Parsery LL (0) by musely předpovídat, které produkce se mají použít na základě současného non-terminálu s nulovým pohledem dopředu. V takových gramatikách může mít každý nekonečný terminál pouze jednu produkci a nemělo by docházet k rekurzi.

Parsery LR (0) znamenají, že zpracovávají token tokenů zleva doprava pomocí derivace Rightmost s nulovým pohledem dopředu. To znamená, že vytvářejí parsový strom zdola nahoru, zatímco LL (0) parsery vytvářejí parsový strom shora dolů.