Komplexita parsingu

[Quant]

Ve škole nás učili, že CF parsing je O(n^3). Na stránce o LLVM jsem se teď dočetl, že parsing je NP-úplný. Trochu mě to zmátlo, co mi uniká?

[Reklama]

[Ivan]

O jaky typ gramatiky se jedna?

[zboj]

O jaky typ gramatiky se jedna?

Vždyť to tam píše.

[zboj]

Ve škole nás učili, že CF parsing je O(n^3). Na stránce o LLVM jsem se teď dočetl, že parsing je NP-úplný. Trochu mě to zmátlo, co mi uniká?

Rozpoznání, zda CF gramatika nějaké slovo přijímá, je skutečně za použití dynamického programování vždy nejvýše O(n^3). Nicméně jakmile se generuje nějaká sémantická reprezentace (AST nebo něco ekvivalentního), je z toho rázem NP-těžký problém a v některých (prakticky ale nezajímavých) případech může jít o problém nerozhodnutelný - snadno lze sestavit gramatiku, podle níž vyžaduje parsing exponenciální počet kroků vzhledem k délce vstupu. V praxi to moc nevadí, vstup je typicky rozdělen do "segmentů", takže místo O(2^n) to ve skutečnosti je O(2^n_1) + ... + O(2^n_k), kde n_i jsou malá čísla (a v mnoha praktických aplikacích to vůbec exponenciální není, ale jde o nejhorší případ). V LLVM jde mimochodem o něco jiného, némlich o časovou komplexitu inference typů, která se provádí až po parsingu, kdy už existuje AST.

[Ivan]

O jaky typ gramatiky se jedna?

Vždyť to tam píše.

Aha me se nejak spojilo LLVM s C++ a to rozhodne neni CF gramatika.

[Reklama]

[zboj]

O jaky typ gramatiky se jedna?

Vždyť to tam píše.

Aha me se nejak spojilo LLVM s C++ a to rozhodne neni CF gramatika.

To ne, v případě C++ je parsing turingovsky úplný (díky templatům).