Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: Quant 20. 10. 2015, 15:53:32
-
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á?
-
O jaky typ gramatiky se jedna?
-
O jaky typ gramatiky se jedna?
Vždyť to tam píše.
-
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.
-
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.
-
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).