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.
5 Odpovědí
1177 Zhlédnutí