Parsování částečně napsaného textu

[botux]

Ahoj

Různá vývojová prostředí parsují program hned jak ho programátor píše a napovídají mu jména metod, případně jsou schopna najít definici funkce a podobně. Přitom musí parsovat kód programu, který není kompletní a neodpovídá gramatice.

Zajímalo by mě, jak je to udělané, jestli existuje nějaká teorie, jak konstruovat parsery pro částečně napsaný kód.

Kdyby člověk napsal gramatiku a nechal si ji parsovat třeba bisonem, tak je to na částečně napsaný kód nepoužitelné, bude docházet k chybám nebo k absurditám, jako například, uživatel napíše do těla nějaké funkce "{", parser si začně myslet, že všechny následující funkce jsou vnořené v současné funkci, no a nakonci souboru slavnostně dá chybu, že mu schází "}".

[Reklama]

[libcha]

S tím jsem se teda v praxi nesetkal, ale rozumná strategie jde vymyslet selským rozumem.
Prostě to z času na čas zkoušíš parsovat (heuristika: třeba kdykoliv uživatel zadá } ), a když to náhodou skončí bez chyb, tak si z toho vybereš ty názvy funkcí apod., které pak budeš od té chvíle našeptávat.

[Ivan]

Pokud jde chyby na urovni lexeru, tak ty se vyresi celkem snadno. Proste reknes lexeru, ze kdyz uz nemuze dal tak at preskoci jedno pismeno - alespon ANTLR to umi. U parsovani je to slozitejsi. Ciste teoreticky muzes u ANTLR predhodit vlastni error handler. Ten defaultni jen preskoci jeden token a zkusi jet dal. Prakticky to ale moc nefunguje zvlast gramatik kde se musi pouzit backtracking. Ten parser totiz zavola tvuj error handler az kdyz vyzkousi vsechny moznosti. Kdyz se tvuj handler zavola, tak treba vis, ze jsi v deklaraci promenny, ze muzou nasledovat tokeny A,B anebo C ale na vstupu je D(ale uz nevis jestli prednim nezkusil parsovat dekalraci funkce). Osetrit takovou situaci ale vyzaduje znalosti vnitrnosti toho parseru a na to jsem jeste nemel zaludek.

Tak jsem si napsal neco vlastniho (pro PL/SQL) s pouzitim Lexeru vygenerovanyho pomoci ANTLR.
http://sourceforge.net/p/tora/code/HEAD/tree/trunk/tora/src/parsing/tsqllexeroracle2.cc#l483

[Zopper]

Budu hádat: co řešení, že když uživatel píše, tak se nedělá parsování, ale nastoupí naopak generátor, který na dané místo zkouší vygenerovat vhodné lexémy?

[Jakub Galgonek]

Tak třeba u C/C++ pro napovídání teoreticky stačí, když je smysluplná jen část kódu od začátku až po kurzor. Na zbytku už nezáleží, takže třeba chybějící ukončovací závorky nejsou problém. V praxi se ale bude asi používat něco trochu jiného. Třeba když jsem se před lety hrabal v doxygenu, tak ten měl jen takový obecný parser, který hledal definice. Žádné gramatiky pro jednotlivé jazyky (co si tak pamatuju) tam nebyly.

[Reklama]

[astarus]

Obecne sa to vola MOF http://en.wikipedia.org/wiki/Meta-Object_Facility . Vzdy musis definovat metamodel jazyka, ktory zavisi na domene http://en.wikipedia.org/wiki/Domain-specific_language, http://en.wikipedia.org/wiki/Domain-specific_modeling_language. Ked to mas, tak relativne jednoducho pouzijes napr. v eclipse EMF http://en.wikipedia.org/wiki/Eclipse_Modeling_Framework .
Inymi slovami potrebujes model pre model jazyka, alias meta meta jazyk Takto sa da definovat vlastny jazyk, ktory doplna, umoznuje dokonca uzivatelovi definovat vlastne konstrukty v jazyku a na tie sa odvolavat. Jedna z najviac sialenych a verejnych veci je na http://d3s.mff.cuni.cz/projects/components_and_services/sofa/. Relativne bezne sa to pouziva este vo firemnych frameworkoch, popripade model based programming.

[Jakub Galgonek]

Uff, nějak nedokážu najít souvislost s původním dotazem

[Stalin]

Tu sa zmysluplnej rady nedočkáte, maximálne od študentov, ktorí náhodou minulý semester absolvovali automaty.

[Jakub Galgonek]

Kdyby člověk napsal gramatiku a nechal si ji parsovat třeba bisonem, tak je to na částečně napsaný kód nepoužitelné, bude docházet k chybám nebo k absurditám, jako například, uživatel napíše do těla nějaké funkce "{", parser si začně myslet, že všechny následující funkce jsou vnořené v současné funkci, no a nakonci souboru slavnostně dá chybu, že mu schází "}".

Pokud bys chtěl jen parsovat počáteční část souboru (po kurzor), tak by to mělo jít i s bisonem. Sice z toho kompletní syntaktický strom pochopitelně nedostaneš, ale pokud z toho chceš vydolovat jen deklarace, tak ti to vůbec nevadí.

Pokud by tě zajímaly nějaké postřehy, jak to řeší v praxi, tak se koukni třeba sem: http://wiki.eclipse.org/CDT/designs/Overview_of_Parsing

[Ivan]

C++ je zvlastni pripad, protoze se parsuje velice tezko. Nejenze pouziva preprocessor, ale navic potrebuje znat "semantiku" nekterych symbolu, aby mohl pochopit zbytek zdrojaku. "Primitivni" programovaci jazyky, jako je napridlad Java maji v tomhle ohledu velkou vyhodu. FSF se buhuzel velice dlouho branilo tomu, aby gcc generovalo nejaky metadata behem kompilovani. Spravne pochopit zdrojak v C++ bohuzel dokaze jen kompilator. Nastesti tu ale neni jen gcc ale i llvm.

A ted jedna lahudka v C++.

Kód: [Vybrat]

#if FIRST_MEANING
   template<bool B>
   class foo
   { };
#else
   static const int foo = 0;
   static const int bar = 15;
#endif

static int foobar( foo < 2 ? 1 < 1 : 0 > & bar );

Autorem je Sam Harwell z ANTLR projektu. Dalsi podobne hnusny priklad kdysi poslal Stroustrup do konference Emacsu,
kdyz se nekdo ptal jeste je mozne aby C++ mod v Emacsu fungoval korektne a jestli se da C++ parsovat v Lispu.

Myslim ze jak Visual Studio tak Eclipse CDT vyuzivaji toho, ze maji databazi symbolu z posledniho uspesneho parsovani
a to jim nejak pomaha chapat castecne rozepsany kod. Alespon u Visual Studia to funguje tak, ze vam zacne nebizet jmena metod
az potom, co je trida alespon 1x zkompilovana.