Jak se píše programovací jazyk 2: Lexer (diskuse)

Diskuse byla administrátory uzamčena.

[kralyk z abclinuxu]

Lexer je možné si napsat ručně, formou stavového automatu, který v cyklu prochází kód znak po znaku a postupně ho rozřezává a analyzuje rozřezané kousky (tokeny), aby jim přisoudil typ. Kdysi jsem něco podobného z neznalosti a z nutnosti udělal (tenkrát v D nebyl žádný lexer), když jsem si psal HTML parser, proto mi věřte, když vám tento přístup DÚRAZNĚ NEDOPORUČÍM.

S tímhle teda úplně souhlasit nemůžu. Mám zkušenost s několika lexer- nebo parser-generátory hlavně z prostředí C++ a Rustu a moje zkušenosti je taková, že na jednu stranu sice pomůžou, ale na druhou jsem vždycky musel s tím generátorem nějakým způsobem bojovat, objevovat jeho limitace a překonávat je (kolikrát složitě). (Typicky error handling je problém, ale i jiné věci.)

Naopak se poslední dobou kloním k názoru, že slušně ručně napsaný lexer / parser je kolikrát lepší. Zejména pokud má použitý programovací jazyk třeba pattern matching a/nebo jiné FP prvky, umožňuje to napsat parsery relativně velmi pěkně. Někde v šuplíku mám v Rustu ručně napsaný parser VT-102, se kterým jsem byl co do korektnosti / čitelnosti / mantainability mnohem spokojenější než s přechozími pokusy pomocí parser-generátorů. U toho odkazovaného HTML parseru mi ani tak nepřijde jako problém, že je napsaný ručně, ale spíš že ten state machine a přechody mezi stavy jsou někde ve funkčních scopech a nejsou dostatečně explicitní. Napříkad jedna možnost, jak to zpřehlednit, by mohlo být mít na to objekt, který by držel stav a například by volal pro každý stav nějakou metodu, která by jako návratovou hodnotu vracela následující stav (to je jen nápad, jsou samozřejmě i jiné cesty).

Tím nechci říct, že je potřeba všechno parsovat ručně, nicméně ruční lexer/parser bych určitě nezavrhoval.

[Bystroushaak]

Naopak se poslední dobou kloním k názoru, že slušně ručně napsaný lexer / parser je kolikrát lepší.

Souhlasím, že bude lepší z hlediska toho že ti umožní dělat víc věcí, ale nejsem spíš si nemyslím, že bude lepší z hlediska třeba udržovatelnosti, nebo například modifikovatelnosti. Dejme tomu že chceš přidat nový druh stringů třeba, něco jako raw stringy v pythonu. Jak moc toho najednou musíš přepisovat a upravovat? Nebo jsem možná jen nenašel vhodný pattern jak to dělat čitelně, hm.

[kralyk z abclinuxu]

Dejme tomu že chceš přidat nový druh stringů třeba, něco jako raw stringy v pythonu. Jak moc toho najednou musíš přepisovat a upravovat?

Myslimže zrovna ten případ přidání raw stringu složitý nebude, ale co se modifikovatelnosti obecně týče, umim si představit, že to problém minimálně v některých případech může být. Na ten ruční parser typicky potřebuješ mít dopředu známmý ten stavový automat a tím můžou změny zahýbat.

Nebo jsem možná jen nenašel vhodný pattern jak to dělat čitelně, hm.

Ten VT parser jsem strukturoval tak, že to byla dvojice interní stav a dispatch objekt. Dispatch objekt byl definovaný jinde a ten dostával 'hotová' data ve chvíli, kdy byly k dispozici (push parsing). Interní stav držel stavový enum parseru + trochu nějaká dodatečná data jako parametry escapů a podobně. Vstupem byla metoda input s parametrem bajt (VT je v podstatě streamovaný binární protokol, který je nutný parsovat bajt po bajtu), ve který se akorát podle aktuálního stavu bajt poslal do nějaké metody, ze které vypadl stav pro následující bajt.

Pro parsování textových non-streaming formátů tohle možná není až tak vhodný přístup. Budu potřebovat v dohledné době napsat parser pro textový markdown-like formát, mám to aktálně napsáno v PEGu, ale saje to, nejsem s tim spokojen. Ještě se nad tím zamyslim, jak to nejlíp strukturovat. Například mě napadá, že by se vstupní data daly rozpadnout na znaky významné pro lexing/parsing, které by parser bral jednotlivě, a shluky znaků nevýznamné (ie. nezpůsobující změnu stavu) by se daly zpracovávat vcelku.

V případě tvého tinySelfu ten rply vypadá IMHO v pohodě. Ačkoli zatím neznám tu interakci s parserem a taky nezmiňuješ, jak dobře reportuje syntaktické chyby.

[Bystroushaak]

V případě tvého tinySelfu ten rply vypadá IMHO v pohodě. Ačkoli zatím neznám tu interakci s parserem a taky nezmiňuješ, jak dobře reportuje syntaktické chyby.

Je to docela v pohodě, ale jak jsem psal, už jsem tam taky narazil, když jsem chtěl parsovat (| code), což prostě asi tenhle druh parseru vůbec nedá. Bude o tom víc příští díl zase za týden.

[kralyk z abclinuxu]

Je to docela v pohodě, ale jak jsem psal, už jsem tam taky narazil, když jsem chtěl parsovat (| code), což prostě asi tenhle druh parseru vůbec nedá. Bude o tom víc příští díl zase za týden.

Moje intuice je, že tím přidáním toho (| code) se z gramatiky jazyka stává context-sensitive gramatika, protože když budeš mít (| xxx) versus (| xxx | yyy), tak to xxx se parsuje jinými pravidly v závislosti na tom, jestli pak následuje '|', nebo ')'.

rply neznám, ale vypadá to, že je založen na EBNF a (E)BNF ti context-sensitive jazyk skutečně nezparsuje, umí jen context-free gramatiky. Ale dají se dělat všelijaké triky, viz např. co v podobné situaci dělá python.

Disclaimer: Neudělal jsem si rigorózní analýzu té gramatiky a nezkusil aplikovat Pumping lema a/nebo Ogden's lema, takže můžu kecat, jsou to jen dva centy.

[Bystroushaak]

rply neznám, ale vypadá to, že je založen na EBNF a (E)BNF ti context-sensitive jazyk skutečně nezparsuje, umí jen context-free gramatiky. Ale dají se dělat všelijaké triky, viz např. co v podobné situaci dělá python.

Jo, k tomu jsem taky dospěl.

Disclaimer: Neudělal jsem si rigorózní analýzu té gramatiky a nezkusil aplikovat Pumping lema a/nebo Ogden's lema, takže můžu kecat, jsou to jen dva centy.

Já jsem parsery nikdy nestudoval, tak jsem to prostě udělal jak to šlo. Upřímně nemám moc tušení co s tím dělat, mrknu na to co jsi linkoval.

Co se týče chybových hlášek, tak ty jsem zatím neřešil vůbec, s tím že na to bude čas pokud z toho někdy něco bude, neboť nemá smysl zabít rok psaním parseru, když to pak zahodíš jako hračku co tě už omrzela.

[kralyk z abclinuxu]

Co se týče chybových hlášek, tak ty jsem zatím neřešil vůbec, s tím že na to bude čas pokud z toho někdy něco bude, neboť nemá smysl zabít rok psaním parseru, když to pak zahodíš jako hračku co tě už omrzela.

To je dobrá poznámka a ve stejném duchu bych asi neřešil tu syntaxi (| code) , pokud ti ta syntaxe (|| code) napřijde nějak výrazně debilní. Ono když to člověk s těmi convenience syntaxemi přežene, tak se mu pak taky může stát, že ten jazyk vůbec parsovat nepůjde

No nic, už tě nechám žít a počkám na další díl...

[Bystroushaak]

To je dobrá poznámka a ve stejném duchu bych asi neřešil tu syntaxi (| code) , pokud ti ta syntaxe (|| code) napřijde nějak výrazně debilní.

Ono to má řešení přes (code), což třeba v Selfu funguje. Bohužel jsem se ale rozhodl tuhle syntaxi znásilnit pro prioritizaci zpráv a unfucknout to není úplně triviální. Sice vím jak na to, ale hodina co jsem tomu věnoval nestačila.

No nic, už tě nechám žít a počkám na další díl...

Náhodou super, já to dělám +- naslepo, tzn nečetl jsem žádné knihy jak ‚se to má dělat‘ ani jsem to neměl na VŠ, takže každá rada dobrá.

[Bystroushaak]

rply neznám, ale vypadá to, že je založen na EBNF a (E)BNF ti context-sensitive jazyk skutečně nezparsuje, umí jen context-free gramatiky. Ale dají se dělat všelijaké triky, viz např. co v podobné situaci dělá python.

Tak jsem to četl a je to jedna z těch věcí, co mě taky napadla, tedy udělat z (| samostatný token.

Celkově jsem se nad tím zamýšlel a je možné, že časem ten parser úplně předělám. Teď to má ale nejmenší prioritu, momentálně se snažím zvednout výkon. Milion cyklů (kde podmínka je lambda/blok) mi žere požád před 3.5 vteřin a rád bych to dostal někam ke sto milisekundám; Speedups of the interpreter.

[kralyk z abclinuxu]

Tak jsem to četl a je to jedna z těch věcí, co mě taky napadla, tedy udělat z (| samostatný token.

IMHO tím si nepomůžeš, neřeší to tu ambiguitu mezi (| xxx | yyy) a (| xxx) ve chvíli, kdy je parser u xxx a neví, jakými pravidly to zparsovat.

Asi bys musel to xxx by default parsovat jako definici slotů a ve chvíli, kdy by parser narazil na konec objektu nebo non-slot syntax (tj. chybu), přidal by uměle na začátek objektu ještě jeden ten separátor a pokusil se to znovu zparsovat jako (|| code) . Ale je to poněkud hack.

[deda.jabko]

Mám zkušenost s několika lexer- nebo parser-generátory hlavně z prostředí C++ a Rustu a moje zkušenosti je taková, že na jednu stranu sice pomůžou, ale na druhou jsem vždycky musel s tím generátorem nějakým způsobem bojovat, objevovat jeho limitace a překonávat je (kolikrát složitě)

Vidim to podobne, ale hodne se mi osvedcil ANTLR, tam se mi dari vetsina veci udelat docela bezbolestne.

[Bystroushaak]

Možná se někdo pozastaví, proč je kód psaný v pythonu 2. Důvod je jednoduchý - pypy v době psaní stále ještě nepodporuje nejnovější python3 v rpython translator toolkitu. Jakmile tam bude podpora pythonu 3.6, mám v plánu kód přeportovat.

Mimochodem zrovna vyšlo Düsseldorf Sprint Report 2019, kde se píše:

Catching up with CPython 3.7/3.8 – we are planning to release 3.6 some time in the next few months and we will continue working on 3.7/3.8.

[wamba]

Tohle [a-zA-Z_]*[a-zA-Z0-9_]+ mi nějak nedává smysl, je to totéž, jak [a-zA-Z0-9_]+ ne? Nemělo by to tam být bez té hvězdičky [a-zA-Z_][a-zA-Z0-9_]+.

[kralyk z abclinuxu]

Tohle [a-zA-Z_]*[a-zA-Z0-9_]+ mi nějak nedává smysl, je to totéž, jak [a-zA-Z0-9_]+ ne? Nemělo by to tam být bez té hvězdičky [a-zA-Z_][a-zA-Z0-9_]+.

IMHO by to mělo být [a-zA-Z_][a-zA-Z0-9_]*, ten [a-zA-Z_][a-zA-Z0-9_]+ by ti nevzal jednoznakový identifikátor.

[Bystroushaak]

+1, máš pravdu. Testy s tím projdou, takže jsem to změnil na [a-z_][a-zA-Z0-9_] (viz to co psal dole Pavel).

[pc2005]

Lexer je možné si napsat ručně, formou stavového automatu, který v cyklu prochází kód znak po znaku a postupně ho rozřezává a analyzuje rozřezané kousky (tokeny), aby jim přisoudil typ.

To tak jsem psal FPGA xdlrc parser v perlu . Zároveň jsem se na tom ale učil význam položek toho xdlrc.

[Pavel Křivánek]

Omezení počátečních písmen následujících částí klíčových slov na velká písmena začíná postrádat původní smysl, jakmile může první část začínat na velké písmeno. Protože pak jde mít zprávu Put: a v uvedeném případe rovněž nevíš, jestli se jedná o novou další zprávu nebo pokračování té předchozí. Přijít ale zase o možnost začínat jména zpráv velkým písmenem, jako to má Self, je hodně velká cena. Je to tedy vlastně jen vynucená konvence (což ovšem také dává smysl).

Překvapuje mě, že nikde nevidím resend (řizený, neřízený) nebo nějakou obdobu. Tvůj jazyk ho nemá?

Používá tvůj jazyk indexování od jedničky nebo od nuly?

[Bystroushaak]

Omezení počátečních písmen následujících částí klíčových slov na velká písmena začíná postrádat původní smysl, jakmile může první část začínat na velké písmeno.

Upřímně, poslední dobou mám pocit že občas fetuju, protože jsem to omezit chtěl, ale vůbec nemám tušení proč jsem to neudělal. I tohle je ale dobrý důvod proč tyhle věci publikovat, protože více oči prostě víc vidí.

Překvapuje mě, že nikde nevidím resend (řizený, neřízený) nebo nějakou obdobu. Tvůj jazyk ho nemá?

Má, jen se dopočítává později z identifikátorů.

Používá tvůj jazyk indexování od jedničky nebo od nuly?

Od nuly.

[Bystroushaak]

Nedá mi to a musím se vskutku podivit nad anonymem, kterého neustále baví přidávat různé „vtipné“ štítky, jako třeba programování jako záškrt.

Chci jen říct, že je mi tě fakt upřímně líto. V rukou potenciál změnit svět k obrazu svému, a jediné co z tebe leze jsou štítky s „humorem“ na úrovni žáka třetí třídy. Nechtěl bych být v tvé kůži. Aspoň doufám, že tě k tomu snad tlačí okolnosti a ne třeba duševní porucha.

[_]

Tak nevím, ale přijde mi lepší dělat si z tvého článku prdel (byť infantilním způsobem), než ho brát vážně...

[tom11111]

V popisu tokenu COMMENT máš asi chybku, má začínat #, ne středníkem. A samotné slovo COMMENT není zformátováno jako nadpis. Jinak zajímavé, přečtu si i další díl :)

[Bystroushaak]

Díky za upozornění, opraveno.

[Stanislav Bohm]

O takovy hybrid Selfu/Io/Pythonu jsem se pred 10 lety take pokousel. Bohuzel vetsina dokumentace je jiz ztracena, zdrojak jsem pred nejakym casem ale zachranil:

https://github.com/spirali/kreatrix

Mel jsem i vetvi s JIT compilerem (nad libjit), ale tu uz jsem nedotlacil do masteru.

Dekuji za clanek, vyvolava to ve mne vzpominky:)

[Bystroushaak]

Zajímavé.

[_]

To muselo dát příšernou práci. A přitom taklová blbost, co?

[Bystroushaak]

<insert random meme />

[sad]

Tak tohle je docela vtipné. Jak jsi ty štítky zmínil v diskuzi, tak jsem si je prohlížel a zkoumal, jak vlastně fungují, a najednou vidím, že je máš zobrazené u zápisku. Takže ty štítky od A jsou ode mě. Sorry.

Tuhle zajímavou funkci bych z abíčka asi odstranil.

Jinak zajímavý zápisek, sice Smalltalk neumím a kompilátory se teprve učím, ale mám určitou představu, o čem tu je řeč, a docela se těším na vytvoření a vyhodnocení toho AST.

Za ty štítky se ještě jednou omlouvám, nevěděl jsem, že to tady můžeš tak super naklikat.

[Bystroushaak]

Tak tohle je docela vtipné. Jak jsi ty štítky zmínil v diskuzi, tak jsem si je prohlížel a zkoumal, jak vlastně fungují, a najednou vidím, že je máš zobrazené u zápisku. Takže ty štítky od A jsou ode mě. Sorry.

V pohodě, já už jsem to hodil do tag manageru a ten to odmázl automaticky, protože jsem je neschválil.

Jinak zajímavý zápisek, sice Smalltalk neumím a kompilátory se teprve učím, ale mám určitou představu, o čem tu je řeč, a docela se těším na vytvoření a vyhodnocení toho AST.

To se ti budou líbit další díly, ten kompilátor je sice neoptimalizovaný a relativně neefektivní (například pořád používám více-bajtové instrukce, místo abych zpackoval časté operandy do jednobajtových), ale zase se dá krásně pochopit a je to na pár řádek.