Yapgen - parser generator (diskuse)

[Bystroushaak]

Pěkné, dal jsem tučňáka.

[Radek Miček]

Samotný jazyk je popsán SLR(1) gramatikou, která je dostatečně silná pro popis obecného programovacího jazyka.

To znamená odstranit konflikty z gramatiky? To není příliš pohodlné, ne?

[Ivorne]

Já si ani nemyslím, že by LALR gramatiky byly z praktického hlediska o tolik silnější.

[zuzanak]

Ano to je pravda je nutné vyřešit SLR(1) konflikty vznikající v rozkladové tabulce. SLR(1) gramatika byla zvolena jako dostačující pro řešení původní úlohy v rámci které program yapgen vznikl.

[Bedňa]

Fajn len by potešil príklad z praxe.

Od té doby jsem jej párkrát využil při implementaci úkolů se kterými jsem se setkal v praxi.

[zuzanak]

Rozšířil jsem zápisek o pár příkladů z praxe.

[Bedňa]

Dík moc.

[xkucf03]

BTW: když píšeš „C/C++“, co to znamená? Umí to generovat zdroják v obou jazycích nebo to generuje C, které se dá přeložit i kompilátorem pro C++?

[zuzanak]

Třetí možnost je správně: generuje to zdrojový soubor pro kompilátor C++, kde z C++ jsou používány následující funkce, které nebyly součástí jazyka C: metody ve strukturách (třídách), reference, datový typ bool, výčtový typ, a možná některé další.

Ale to není tak důležité, protože v případě potřeby je možné vygenerovat výsledný zdrojový soubor v libovolném jazyce (dostatečně silném). Tvrdá práce: generování DFA (Deterministický Konečný Automat) a LALR tabulky je již hotová a generování C/C++ souboru je v podstatě jen export algoritmů na těmito dvěma strukturami.

Příklady vygenerovaných .cc souborů odpovídajících překladačům popsaným v kapitolce "Příklad tvorby překladače" je uveden na: 1, 2, 3.

Uvedené soubory obsahují dvě základní funkce recognize_terminal a parser_parse_source_string, které dělají všechnu práci.

[Odin1918]

Je to OT, ale proc zmizel posledni Leosuv blog? Cenzura?

[xkucf03]

To je mi dost divné. Sice nebyl nijak moc kvalitní, v podstatě o ničem, ale zápisky Miriam tu taky zůstávají (byť třeba ne na titulní stránce). A protože pod ním byly komentáře, nemohl ho běžný uživatel (jako autor) smazat. Leoš asi není běžný uživatel…

[Luboš Doležel (Doli)]

Tuhle operaci může udělat jen uživatel root. Pokusím se zjistit, co se stalo.

[Luboš Doležel (Doli)]

Bohužel jsem neviděl tu cache, ale podle logu mazání provedu uživatel číslo 1. Takže autor.

[manasekp]

Taky jsem si toho vsiml. V google cache to jeste je.

[Bystroushaak]

Cache: AbcLinuxu je stále známá značka

[xkucf03]

Ad patička:

Výhodná nabídka; Romantická kvelbená kóje v Kyjově (se záchodem!)

To je včetně toho pozemku nad tím nebo to je cena jen za díru v zemi a ty cihly? Kupuješ? Podle kabelů to vypadá, že elektřina tam je. Šlo by tam udělat datacentrum a menší kancelář. Na zahradě by se postavil stožár a bylo by

[Bystroushaak]

Kupuješ?

Spíš jsem chtěl morálně podpořit majitele v jeho originálně snaze prodat kvelbenou kóji.

[Petr Tomášek]

ani to už ne...

[Jardík]

Já bych dal nedostatečou, protože používáš "unsigned" tam, kde se hodí a je více správné použít "size_t". Např. na platformě, kde je numeric_limit<unsigned>::max() 0xffff a numeric_limit<size_t>::max() 0xffffffffffffffff, tak příliš omezuješ. Na platformě, kde je to zase naopak, zase "lžeš", protože tvrdíš, že dokážeš pracovat s něčím, co nejde naalokovat. (to, že takovou platformu neznáš, nebo že není, nikoho neomlouvá). Třeba na ČVUT v různých předmětech programování dávají nedostatečnou za jednu chybu běžně. A tohle chyba je. Ale nic si z toho nedělej, i často používané knihovny, jako je Qt, jsou plné chyb. Např. Qt tvrdí, že dokáže ze souboru do paměti načíst numeric_limit<int64_t>::max() bytů i na x86-32, přitom to neumí.

[Bystroushaak]

A poslal jsi patch?

Jak jde jinak život?

[zuzanak]

Nepochybně máš pravdu, bohužel jsem si zvykl používat základní datové typy tak, že počítám s platností následujících tvrzení:

sizeof(void *)        == sizeof(long unsigned)
sizeof(int)           == 4
sizeof(unsigned)      == 4
sizeof(char)          == 1
sizeof(long long int) == 8
sizeof(float)         == 4
sizeof(double)        == 8

A až narazím na platformu, na které to nebude platit, tak si budu trhat vlasy a vzpomenu si na tebe.

[Jardík]

sizeof(void *) == sizeof(long unsigned)

Tohle třeba neplatí na Windows, teda né že mi Windows není ukradenej, ale stejně. Pro nějaké takové prasárničky typu pointer na číslo existuje (u)intptr_t.

sizeof(unsigned) == 4

S tímhle nepochodíš na různých mikroprocesorech. Na těch "hloupých" typu atmega, to je např. 2.

sizeof(char) == 1

Tohle platí vždycky. Ať už má char 8 nebo 256 bitů, pořád to 1 byte, protože byte je totéž co char.

[vlastikroot]

Je neco spatnyho na tom, ze vubec nepouzivam size_t a vsechny velikosti mam pevne omezene napr. uint8_t nebo int64_t a naprosto ignoruju architekturu? Mam porad trochu problem s endianness, ale jinak se muzu spolehnout, ze bude kod fungovat vsude stejne (hlavne na 8bit AVR).

Uplne jsem ale prestal pouzivat packed struktury, to je zlo.

[Jardík]

Pokud program běží na ne-POSIX systému či nějaké té zvláštní architektuře, tak tvé číselné typy nemusí existovat. Chceš-li zaručit kompatibilitu, měl bys použít (u)int_leastN_t typ (kde N je těch 8, 16, 32, 64), které musí existovat a zároveň jsou to nejmenší typy, které mohou nabývat požadovaných hodnot, mohou ale nabývat i více, takže je třeba maskovat některé bitové operace. Popř. jejich fast verze, které jsou "rychlé", ale nejsou nejmenší. Na platformách, kde např. existuje uint8_t bude uint_least8_t stejný typ jako uint8_t. Na POSIX systémech uint8_t existovat bude (protože ty vyžadují 8bit char).

Ano, packed struktury jsou zlo. Proto je lepší rozvrhnout prvky od největšího po nejmenší, tak aby nevznikaly zbytečné paddingy. Taky je ale dobré u větších struktur uvažovat cacheline procesoru a nerozhazovat často používané prvky na různá místa a dělat kompromisy.

[Bedňa]

Takže navrhuješ overovanie typov podľa architektúry, alebo pretekanie premenných podľa architektúry?

[Jardík]

Proč? Potřebuju-li velikost něčeho co rvu do paměti, vím, že size_t pro to stačí. Potřebuju-li něco s nějakou minimální velikostí, použiju jeden z (u)int_leastN_t typů, pro ukládání bytů použiju char/unsigned char (popř. uint_least8_t, nebo dokonce uint8_t pokud jsem si 100% pokuď vyžaduju 8bit char a tento požadavek uvedu někde třeba v dokumentaci). A nebo použiju i ty základní typy, unsigned má garanci (2^16-1) a více, size_t taky, unsigned long long má garanci (2^64-1), atd, stačí si najít minimální rozsahy a použít typ, co se hodí nejvíce k danému účelu. Konstanty v limits.h (popř climits) lze použít i pro podmíněnou kompilaci, nevidím problém v tom je použít, k tomu přeci jsou.

[vlastikroot]

A co kdyz nemam vubec problem s minimalni velikosti, ale potrebuju presne urcite nasobky 8bitu? Napr. kdyz zpracovavam HW udaje a potrebuju 1:1 bitovou reprezentaci. Nebo treba kdyz rozebiram a skladam sitove pakety.

Taky moc se mi nelibi, ze bych vsude psal uint_least32_t misto uint32_t, je to delsi zapis a neprinasi funkcionalitu ani prehlednost.

[Jardík]

A co kdyz nemam vubec problem s minimalni velikosti, ale potrebuju presne urcite nasobky 8bitu? Napr. kdyz zpracovavam HW udaje a potrebuju 1:1 bitovou reprezentaci. Nebo treba kdyz rozebiram a skladam sitove pakety.

Na platformě, kde neexistuje 8bit typ toho nedocílíte a musíte použít typ větší (a třeba z něho použít jen 8 bitů, to je na vás) a na platformě, kde existuje, tak ho použijete. A když ho vyžadujete, tak není problém otestovat, jestli je nadefinováno nějaké UINTN_MAX makro a kydnout tam #error s vysvětlením proč a co, než nechat kompilaci selhat na nějaké chybě, která třeba nic neřekne potenciálnímu "kompilovači" vašeho kódu. A jestli se vám zdají jména dlouhé, tak použijte kratší, jazyk k tomu poskytuje prostředky (typedef, using).

[vlastikroot]

Na jake platforme neexistuje 8bit? Da se k takove realne dostat jako obycejny smrtelnik?

[Luboš Doležel (Doli)]

Mám pocit, že tohle má jen 16bitový datový typ (je v tom nějaký Analog Devices DSP), takže i ASCII stringy mají 16 bitů na znak. Portoval jsem z toho kód na Android a bylo to někdy docela peklo.

[vlastikroot]

DSP bych do toho nepocital, to by me nikdy nenapadlo, ze by muj kod mohl bezet na DSP. Je urcen pouze pro MCU a CPU.

[deda.jabko]

Na platformě, kde neexistuje 8bit typ toho nedocílíte a musíte použít typ větší (a třeba z něho použít jen 8 bitů, to je na vás) a na platformě, kde existuje, tak ho použijete.

Toto je naprosto absurdni situace, ktera by mohla nastat v drevnich dobach pocitacu typu PDP-XY, kdy jeste nebyl byte obecne prijatou jednotkou pro ulozeni informace a velikost slova byla definovana moznostmi hardwaru.

Napr. architektura SPARC nebo treba JVM pracuji interne s 32bitovyma hodnotama a jen pri praci s pameti vyuzivaji typy s mensim rozsahem... a nikomu to vetsi problemy necini, protoze prekladac se o to postara sam.

[Jardík]

Jde hlavně o překladač, ano. Klidně bych teď mohl napsat C kompilátor (kdybych měl čas), který na x86 bude mít 16bit char a váš kód tam pak klekne na obskurní chybě, protože je tu váš předpoklad, že máte 8bit char, který však nikde neuvedete a nikde ho nevynucujete, popř. neuvede jiný předpoklad, který ho implikuje (třeba POSIX).

[vlastikroot]

Na takovej kompilator se muzu vykaslat. U nekterych projektu kaslu i na ten microsofti.

[xkucf03]

kdybych měl čas

Čemu se teď vlastně věnuješ? Nechceš se někdy rozepsat v blogu?

[Jardík]

Věnuju se úvaze o důvodu mého bytí. Věnuju se opakováním, že nemám na nic čas, přitom vůbec nic nedělám. Momentálně to mám disassemblerovanou binárku jedný hry, skládám z toho zdrojový kód v C++. Pak tu překládám bytecode z lua skriptů zpět na skripty, který musí dát opět schodný bytecode. No a tímhle trávím celý den, a proto nemám na nic čas. Taky jsem potřeboval jít k doktorovi, protože mám zánět předkožky (asi mi to tam začíná hnít, protože neprovozuji pohlavní styk), ale nemám na něj. Takže si dvacetkrát denně omývám bimbase a doufám, že to zmizí. A když ne, tak mi asi upadne.

[Jardík]

A pořád uvažuji, co mám jít dělat. Pořád si nevím rady jak a kde si najít práci. Já se ani nemám jít kam podívat, na cestu daleko nemám a do tří hodin pěšky toho tu moc není (3+3 hodiny cesta, 8 hodin práce a 8 hodin spánek, 1 hodina snídaně a výprava do práce, 1 hodina mytí a příprava na spánek = 24hod).

[Jardík]

Jó a ještě mám pořád problém s tím varletem, to taky zlobí. A pak ještě začíná bolet ten zub, jak mám 2 roky vypadlou plombu.