Gramatiky v IT

[Qeek]

No mě by právě spíš zajímalo, jestli někdo ví o skutečně existujících aplikacích, kde to opravdu funguje. Fantazírovat můžem o lecčems a moc v tom nevidím smysl

v Unity3D je (podle https://www.diva-portal.org/smash/get/diva2:832913/FULLTEXT01.pdf) možné použít L-systémy (DBKG, https://cs.wikipedia.org/wiki/L-syst%C3%A9m) ke generování rostlin.

Samozřejmě se s gramatikami potkává člověk každý den (jen o tom neví), protože každý stavový protokol je možné vyjádřit regulární gramatikou. Takže i TCP je aplikovaná gramatika v praxi.

[Reklama]

[balki]

Vite co? Prestanme se bavit o tech neshopnych. Nejsou nijak zajimavi.

Že se s nimi pracuje v překladačích, to asi všichni víme a většinu z nás to asi nechává celkem chladnými, protože překladač nikdy navážno dělat nebudem. Existují nějaké jiné příklady z praxe? Třeba jánevím nějaké zpracování signálů elegantně vyřešené pomocí nějaké gramatiky? Něco, čím by se i normální smrtelník mohl inspirovat a říct si "Ha! Tohle taky musím někde použít!"?

Regulerna gramatika - stavovy automat.  Ked mas malo pamate a potrebujes menit program v zariadeni, implementujes ho vseobecne ako stavovy automat. Osobne som to pouzival na sledovanie stavu TCP-IP komunikacie a na regulovanie ventilov. Uplne easy vec. Mas nejaky stav, dojde nejaky vstup, prepnes na iny stav. Wow vec? Pouziva sa to v riadeni dopravy.

Bezkontextovu gramatiku som zatial pouzival len na sledovanie parovania udalosti, ci nedochadza k zlym stavom. (Zasobnikovy automat, alias pushdown automata)

Asi som uviedol dost nudne veci, ale pri niektore problemy je vhodne modelovat ako gramatiky, zjednodusi sa program, aj jeho formalne overovanie.

Z wow veci viem akurat, ze sa to pouziva v genetike a v lingvstike.

[Ivan]

Že se s nimi pracuje v překladačích, to asi všichni víme a většinu z nás to asi nechává celkem chladnými, protože překladač nikdy navážno dělat nebudem. Existují nějaké jiné příklady z praxe? Třeba jánevím nějaké zpracování signálů elegantně vyřešené pomocí nějaké gramatiky? Něco, čím by se i normální smrtelník mohl inspirovat a říct si "Ha! Tohle taky musím někde použít!"?

Nemusis zrovna psat prekladac, abys' potreboval napsat parser nejakeho programovaciho jazyka. Vsechny nastroje jako je Eclipse Xtext, SonarQube, OpenGrok musel nekdo vytvorit. Anebo alespon jejich pluginy.

Priklad z praxe. Mas rozsahly projekt v nejakem polo-mrtvem pocitacovem jazyce, a potrebujes zjistit, ke kterym tabulkam v databazi pristupuje. Muzes to vsechno precist "rucne" anebo si na ty zdrojaky napises parser.

Napsat parser neni az tak tezky, jsou na to ruzne generatory. A vysledek je efektivnejsi nez si rict "pouzijeme jako programovaci jazyk XML", anebo "pouzijeme pro dotazavaci DSL jazyk podmnozinu javascriptu".

Tady muzes videt kolik parseru je volne k dispozici pro ANTLR https://github.com/antlr/grammars-v4.

[Mirek Prýmek]

Samozřejmě se s gramatikami potkává člověk každý den (jen o tom neví), protože každý stavový protokol je možné vyjádřit regulární gramatikou. Takže i TCP je aplikovaná gramatika v praxi.

Tohle je (zde rozšířený) klam, že jestliže jde X modelovat pomocí Y, tak samotná existence X je důkazem užitečnosti Y.

Je dost možný, že evidenci došlých faktur jde popsat pomocí pojmů hinduistické filosofie. Přesto to v praxi nikdo nedělá, čili naléhavost problému evidence došlých faktur není (sama o sobě) důkazem užitečnosti hinduistické filosofie.

[Qeek]

K původní otázce:

jen by mě zajímalo, čím jsou BG zvláštní, že se pro tuto úlohu hodí

IMO fakt, který k tomu přispívá nejvíce je, že BKG je nejjednodušší gramatika, která umožňuje párovat závorky.

Pokud nakoukneme do světa moderních prog. jazyků, tak dokonce zjistíš, že jich je spousta kontextových. Příklady kontextových jazyků: C, Java, JavaScript, Python, Ruby.  C++ je dokonce Turingovsky úplný (díky šablonám a od C++11 constexpr funkcím).

Tohle je (zde rozšířený) klam, že jestliže jde X modelovat pomocí Y, tak samotná existence X je důkazem užitečnosti Y.

Obecně máte pravdu. V případě nějakého stavového protokolu se gramatika může hodit pro jeho popis a na základě této gramatiky provést verifikaci (např. dokázat, že neexistuje takový stav, který by zapříčinil deadlock).

[Reklama]

[Mirek Prýmek]

V případě nějakého stavového protokolu se gramatika může hodit pro jeho popis a na základě této gramatiky provést verifikaci (např. dokázat, že neexistuje takový stav, který by zapříčinil deadlock).

No, to už je jiná. Ovšem na tohle se, AFAIK, gramatiky běžně nepoužívají.

P.S. Mimochodem, to, že je regulární gramatika ekvivalentní stavovému automatu, neznamená, že když na něco použiju stavový automat, tak jsem použil gramatiku. (Regulární) gramatika a stavový automat jsou dvě různé věci.

[Ivan Nový]

V případě nějakého stavového protokolu se gramatika může hodit pro jeho popis a na základě této gramatiky provést verifikaci (např. dokázat, že neexistuje takový stav, který by zapříčinil deadlock).

No, to už je jiná. Ovšem na tohle se, AFAIK, gramatiky běžně nepoužívají.

P.S. Mimochodem, to, že je regulární gramatika ekvivalentní stavovému automatu, neznamená, že když na něco použiju stavový automat, tak jsem použil gramatiku. (Regulární) gramatika a stavový automat jsou dvě různé věci.

Na základě gramatiky lépe zkontrolujete co ten regulární automat dělá. Jinak i regulární výrazy jsou zápisem pravidel regulární gramatiky.

[Mirek Prýmek]

Na základě gramatiky lépe zkontrolujete co ten regulární automat dělá.

Nevím. Mně přijde intuitivně srozumitelnější zápis stavového automatu.

Jinak i regulární výrazy jsou zápisem pravidel regulární gramatiky.

A?

[Ivan Nový]

Na základě gramatiky lépe zkontrolujete co ten regulární automat dělá.

Nevím. Mně přijde intuitivně srozumitelnější zápis stavového automatu.

Jinak i regulární výrazy jsou zápisem pravidel regulární gramatiky.

A?

No rozhodně na základě dvaceti pravidel si uděláte lepší představu o přijímaném regulárním jazyku, než na základě 150 ifů zanořených do sebe. Proto taky jsou regulární výrazy tak populární.

No a vidíte, že myšlení na úrovni vytváření gramatiky běžně používáte, když prohledáváte řetězce pomocí regulárních výrazů.

[Mirek Prýmek]

No rozhodně na základě dvaceti pravidel si uděláte lepší představu o přijímaném regulárním jazyku, než na základě 150 ifů zanořených do sebe. Proto taky jsou regulární výrazy tak populární.

Proč bych měl stavový automat zapisovat pomocí zanořených ifů?! Běžně se zapisuje takhle:



Můžete k tomuhle automatu napsat příslušnou gramatiku, schválně co bude zřetelnější a bude se nad tím snadněji přemýšlet

No a vidíte, že myšlení na úrovni vytváření gramatiky běžně používáte, když prohledáváte řetězce pomocí regulárních výrazů.

A tvrdil jsem snad opak?!

[Ivan Nový]

No rozhodně na základě dvaceti pravidel si uděláte lepší představu o přijímaném regulárním jazyku, než na základě 150 ifů zanořených do sebe. Proto taky jsou regulární výrazy tak populární.

Proč bych měl stavový automat zapisovat pomocí zanořených ifů?! Běžně se zapisuje takhle:



Můžete k tomuhle automatu napsat příslušnou gramatiku, schválně co bude zřetelnější a bude se nad tím snadněji přemýšlet

No a vidíte, že myšlení na úrovni vytváření gramatiky běžně používáte, když prohledáváte řetězce pomocí regulárních výrazů.

A tvrdil jsem snad opak?!

No ale ten obrázek je de facto grafický zápis pravidel gramatiky. To jste se trochu střelil do nohy.

[Mirek Prýmek]

No ale ten obrázek je de facto grafický zápis pravidel gramatiky. To jste se trochu střelil do nohy.

OMG! Je to de facto zápis gramatiky, protože pro ten automat existuje regulární gramatika. Ale tohle je prostě automat. Automat je automat a gramatika je gramatika.

[Ivan Nový]

No ale ten obrázek je de facto grafický zápis pravidel gramatiky. To jste se trochu střelil do nohy.

OMG! Je to de facto zápis gramatiky, protože pro ten automat existuje regulární gramatika. Ale tohle je prostě automat. Automat je automat a gramatika je gramatika.

A co je pro vás srozumitelnější, OFF -> turn off OFF, ... nebo [['turn off', 1, 1],['turn off', 2,1],...]] s čím pracujete ve své mysli, s pravidlem, nebo snad se seznamem? Z hlediska programu je výhodnější seznam, z hlediska víry v to, co dělá automat, je lepší gramatika.

[Mirek Prýmek]

Z hlediska programu je výhodnější seznam, z hlediska víry v to, co dělá automat, je lepší gramatika.

Ve složitější gramatice ani rychle nepoznáte, jestli se stroj někdy zastaví. Ale jinak víru vám neberu. Hare Krsna!

[Ivan Nový]

Z hlediska programu je výhodnější seznam, z hlediska víry v to, co dělá automat, je lepší gramatika.

Ve složitější gramatice ani rychle nepoznáte, jestli se stroj někdy zastaví. Ale jinak víru vám neberu. Hare Krsna!

To jednoduše nepoznáte v ničem. Tak v tom není rozdíl, mezi seznamem a gramatikou.