Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: logix 11. 05. 2017, 18:06:34
-
Ahoj, mám zvídavou otázku: Proč se v IT používají v překladačích bezkontextové gramatiky (ze škály formální hierarchie)? Nedělám v IT, gramatiky znám z kursu logiky (v rámci studia filosofie jazyka), neznám tedy historický kontext, jen by mě zajímalo, čím jsou BG zvláštní, že se pro tuto úlohu hodí. Návazná otázka by pak byla, jakou časovou složitost má v překladačích v IT parsing, vzhledem k tomu, že bekontextový parsing s omezujícími podmínkami je NP-těžký.
-
Typicky se pouzivaji ne obecne ale deterministicke bezkontextove jazyky. Je to dobry kompromis mezi jednoduchosti a deskriptivnosti. Na parsing se typicky pouziva nejaka varianta LALR parseru s linearni casovou slozitosti. Viz https://en.wikipedia.org/wiki/LALR_parser .
-
Ahoj, mám zvídavou otázku: Proč se v IT používají v překladačích bezkontextové gramatiky (ze škály formální hierarchie)? Nedělám v IT, gramatiky znám z kursu logiky (v rámci studia filosofie jazyka), neznám tedy historický kontext, jen by mě zajímalo, čím jsou BG zvláštní, že se pro tuto úlohu hodí. Návazná otázka by pak byla, jakou časovou složitost má v překladačích v IT parsing, vzhledem k tomu, že bekontextový parsing s omezujícími podmínkami je NP-těžký.
Protože existují efektivní algoritmy k jejich využívání. Navíc se programovací jazyk při jeho návrhu dá upravit tak, aby bezkontextové gramatice odpovídal. K jejich implementaci obvykle stačí zásobníkový automat a regulární automat k výběru pravidla. Dříve omezujícím faktorem bývala paměť a rychlost procesoru. Proto se hledaly metody efektivního překladu. Výhodou je taky sémantická jednoznačnost interpretace jazykových konstrukcí, která umožňuje automatizovat konstrukci překladače a optimalizace i testování.
Z praktického hlediska je pěkné když máte nějakou gramatiku a automat, který ji přijímá, ale to nestačí, potřebujete jistotu, že ten zkonstruovaný automat přijímá právě jen řetězce dané gramatiky a ne jiné. U BG se dokazování a testování dá zase automatizovat.
-
Ahoj, mám zvídavou otázku: Proč se v IT používají v překladačích bezkontextové gramatiky (ze škály formální hierarchie)? Nedělám v IT, gramatiky znám z kursu logiky (v rámci studia filosofie jazyka), neznám tedy historický kontext, jen by mě zajímalo, čím jsou BG zvláštní, že se pro tuto úlohu hodí. Návazná otázka by pak byla, jakou časovou složitost má v překladačích v IT parsing, vzhledem k tomu, že bekontextový parsing s omezujícími podmínkami je NP-těžký.
Protože existují efektivní algoritmy k jejich využívání. Navíc se programovací jazyk při jeho návrhu dá upravit tak, aby bezkontextové gramatice odpovídal. K jejich implementaci obvykle stačí zásobníkový automat a regulární automat k výběru pravidla. Dříve omezujícím faktorem bývala paměť a rychlost procesoru. Proto se hledaly metody efektivního překladu. Výhodou je taky sémantická jednoznačnost interpretace jazykových konstrukcí, která umožňuje automatizovat konstrukci překladače a optimalizace i testování.
Z praktického hlediska je pěkné když máte nějakou gramatiku a automat, který ji přijímá, ale to nestačí, potřebujete jistotu, že ten zkonstruovaný automat přijímá právě jen řetězce dané gramatiky a ne jiné. U BG se dokazování a testování dá zase automatizovat.
BG je O(n**3), to není moc efektivní.
-
@zboj
A nemá LL i LR parser spíše lineární náročnost? Ovšem kubickou má CYK, Earley.
-
@zboj
A nemá LL i LR parser spíše lineární náročnost? Ovšem kubickou má CYK, Earley.
Má, ale znělo to jako obecně o BG.
-
Gramatiky v IT? To je taková ta věc, která se učí na VŠ, kde následně se vyprodukuje student, co neovládá ani GIT?
-
Gramatiky v IT? To je taková ta věc, která se učí na VŠ, kde následně se vyprodukuje student, co neovládá ani GIT?
Vy asi budete polír :-))) Je vidět, že IT je už obor v produktivním věku :-)))
-
Gramatiky v IT? To je taková ta věc, která se učí na VŠ, kde následně se vyprodukuje student, co neovládá ani GIT?
Vy asi budete polír :-))) Je vidět, že IT je už obor v produktivním věku :-)))
No nevím, pořád mi přijde jako nezralý obor.
-
teorie je hezka vec. ale tak v praxi vzdy narazi.
bud narazi na limity technologie a teorie bude tvrdit, ze neco nejde zatim co praxe pouzije kategorii pseudo-reseni, ktera v realu vypada jako "zazrak"
nebo narazi na limity reimplementace treba jako tridy rekurzi a dusledky neprenositelnosti mezi kompilatory ve vyhodnocovani poradi parametru funkci.
atd. v realu si nakonec reknes: k cemu to je? k ...
-
Tak moje praktická zkušenost: na MFF mě tenhle předmět fakt bavil a věnoval jsem tomu docela dost času. Uplynulo pár let a potřeboval jsem napsat parser na takový jeden "ne-úplně-specifikovaný" jazyk (popis časových intervalů). I vrhnul jsem se na Lex/yacc (v pythoním provedení). Pak jsem svedl nelítostný boj s těmi různými shift-reduce konflikty... který jsem nakonec spíš prohrál....
No a pak jsem narazil na parsery ve stylu "parsec" a nějak už nemám moc chuť nějakou gramatiku řešit....
-
Tak moje praktická zkušenost: na MFF mě tenhle předmět fakt bavil a věnoval jsem tomu docela dost času. Uplynulo pár let a potřeboval jsem napsat parser na takový jeden "ne-úplně-specifikovaný" jazyk (popis časových intervalů). I vrhnul jsem se na Lex/yacc (v pythoním provedení). Pak jsem svedl nelítostný boj s těmi různými shift-reduce konflikty... který jsem nakonec spíš prohrál....
No a pak jsem narazil na parsery ve stylu "parsec" a nějak už nemám moc chuť nějakou gramatiku řešit....
Na MFF v tomto ohledu byly nejlepší přednášky Martina Plátka, dával na čtení doma články v azbuce, ale jinak se probíraly věci, co sám vymyslel.
-
@zboj @andy
Jo to je pravda, já zase používám než klasický přístup PEG gramatiku, která se dá implementovat podobným přístupem jako je parsec.
-
Gramatiky v IT? To je taková ta věc, která se učí na VŠ, kde následně se vyprodukuje student, co neovládá ani GIT?
Copak GIT, ale my neměli ani kurzy Wordu! Představte si, VŠ IT a absolventi nevědí kolikátá položka v kterém menu je "Uložit jako"!
-
Gramatiky v IT? To je taková ta věc, která se učí na VŠ, kde následně se vyprodukuje student, co neovládá ani GIT?
Copak GIT, ale my neměli ani kurzy Wordu! Představte si, VŠ IT a absolventi nevědí kolikátá položka v kterém menu je "Uložit jako"!
Ja sa hanbim, som absolvent vysokej skoly a neovladam total commander ani photoshop. Vo worde tiez ikonky hladam. Dokonca poznam jednoho, co nevie nakreslit uml diagram v malovani.
Ja si myslim, ze malovani by mal byt zakladny predmet. A dalsi predmet prepinace a programovanie v awk-u.
-
Gramatiky v IT? To je taková ta věc, která se učí na VŠ, kde následně se vyprodukuje student, co neovládá ani GIT?
No jak sam vidite, jsou lide, kterym ani znalosti k uspechu nepomohou. To ale neznamena, ze schopni lide ty znalosti nedokazi pouzit k zajimavym vecem. Vite co? Prestanme se bavit o tech neshopnych. Nejsou nijak zajimavi.
-
Vite co? Prestanme se bavit o tech neshopnych. Nejsou nijak zajimavi.
To zní rozumně! Víte někdo o nějakém konkrétním příkladu něčeho fakt zajímavého, o nějakém konkrétním praktickém problému, který někdo elegantně vyřešil pomocí nějaké gramatiky?
Ž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!"?
-
Vite co? Prestanme se bavit o tech neshopnych. Nejsou nijak zajimavi.
To zní rozumně! Víte někdo o nějakém konkrétním příkladu něčeho fakt zajímavého, o nějakém konkrétním praktickém problému, který někdo elegantně vyřešil pomocí nějaké gramatiky?
Ž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!"?
Co takhle staré dobré NLP?
-
Co takhle staré dobré NLP?
To je jednak pořád v podstatě z oblasti překladačů :) a navíc, nejsou nejnovější pokroky v NLP spíš tažené "soft" metodami jako jsou ty různé deep learningy apod.? Nebo je to jenom mediálně zajímavější, tak se o tom laik spíš dozví a ve skutečnosti je progress spíš v té oblasti "formálního" NLP (jako třeba překlad přes TIL, co se dělá v Brně, apod.)?
Mě by spíš docela zajímaly nějaké neotřelé aplikace gramatik - nějaké jánevím, třeba generativní vytváření 3D scén ve hrách pomocí nějakých vychytaných pokročilých L-systémů nebo tak něco, co by bylo fakt zajímavý, poučný, inspirativní...
-
Co takhle staré dobré NLP?
To je jednak pořád v podstatě z oblasti překladačů :) a navíc, nejsou nejnovější pokroky v NLP spíš tažené "soft" metodami jako jsou ty různé deep learningy apod.? Nebo je to jenom mediálně zajímavější, tak se o tom laik spíš dozví a ve skutečnosti je progress spíš v té oblasti "formálního" NLP (jako třeba překlad přes TIL, co se dělá v Brně, apod.)?
Mě by spíš docela zajímaly nějaké neotřelé aplikace gramatik - nějaké jánevím, třeba generativní vytváření 3D scén ve hrách pomocí nějakých vychytaných pokročilých L-systémů nebo tak něco, co by bylo fakt zajímavý, poučný, inspirativní...
Pokrok jde pomalými kroky, ale neřekl bych, že to je z oblasti překladačů, protože tam není fáze generování (krom MT), ale spíše konverze do nějaké logické formy (typicky nějaký fragment FOL promíchaný s λ-kalkulem nebo logika vyššího řádu sémanticky omezená na předchozí). Přitom v této doméně je zajímavá ne ta Chomského gramatika jako taková, ale právě ta logika kolem.
A pokud jde o přepisovací systémy, tak v NLP se používá Knuth-Bendixův algoritmus (nebo nějaká jeho obdoba) právě pro řešení těch logických formulí (prostě word problem nad jazykovými termy). Právě ta souhra gramatik a omezujících podmínek je zajímavá, zvlášť když člověk nechá bokem angličtinu a zkusí třeba jen češtinu (opravdu zajímavé to je při analýze jazyků jako adygejština nebo kečuánština nebo grónština, protože tam je jedno slovo klidně celá věta, takže syntaktický strom je jen jeden vrchol a celý význam je v té omáčce kolem). A to nezmiňuju aktuální větné členění ;)
-
Význam gramatik vzroste s rozvojem právě těch měkkých metod deep learningu.
Gramatiky se budou používat ke generování trénovacích dat. Postupným zařazováním pravidel umožňují automaticky generovat vzory s různými aspekty cílového jazyka. Proces učení může pak být dynamický a evoluční.
Gramatiky umožní, že v situaci, kdy ztratíte kontrolu nad procesem učení stroje, získáte kontrolu nad tím, co se stroj bude učit.
-
A pokud jde o přepisovací systémy
Ani ne, spíš mi šlo o nějaký aha moment - něco, nad čím bych si řekl "no ti jsou ale vykutálení, že tohle udělali pomocí gramatiky, to by mě nenapadlo!" Překlad adygejštiny není myslím úplně příklad problému, který by tady moc lidí trápil ;)
Gramatiky se budou používat ke generování trénovacích dat.
Budou, budou... To mi připomnělo:
v budoucnosti se bude umění s technikou tak nějak harmonicky doplňovat – lyrickoepické verše pomohou při chemizaci likvidační praxe – periodická soustava prvků pomůže rozvoji impresionismu – na každém technickém výrobku bude zvláštní ploška, vyhrazená pro účinný estetický vjem – komíny atomových elektráren budou pomalovány našimi nejlepšími krajináři – dvacet tisíc mil pod mořem budou čítárny přístupné všem – diferenciální rovnice se budou psát ve verších – na střechách cyklotronů budou divadla malých forem – a v nich se budou recitovat diferenciální rovnice – tak nějak lidsky, ne?
:)
Navíc, není to trochu zvláštní nápad, učit stroj rozpoznávat něco, co umím strojem generovat? Nemáme dostatek korpusů? (Nic o tom nevím, možná jsem úplně mimo, ale tohle mě teda nijak neohromilo ;) )
-
A pokud jde o přepisovací systémy
Ani ne, spíš mi šlo o nějaký aha moment - něco, nad čím bych si řekl "no ti jsou ale vykutálení, že tohle udělali pomocí gramatiky, to by mě nenapadlo!" Překlad adygejštiny není myslím úplně příklad problému, který by tady moc lidí trápil ;)
Gramatiky se budou používat ke generování trénovacích dat.
Budou, budou... To mi připomnělo:
v budoucnosti se bude umění s technikou tak nějak harmonicky doplňovat – lyrickoepické verše pomohou při chemizaci likvidační praxe – periodická soustava prvků pomůže rozvoji impresionismu – na každém technickém výrobku bude zvláštní ploška, vyhrazená pro účinný estetický vjem – komíny atomových elektráren budou pomalovány našimi nejlepšími krajináři – dvacet tisíc mil pod mořem budou čítárny přístupné všem – diferenciální rovnice se budou psát ve verších – na střechách cyklotronů budou divadla malých forem – a v nich se budou recitovat diferenciální rovnice – tak nějak lidsky, ne?
:)
Navíc, není to trochu zvláštní nápad, učit stroj rozpoznávat něco, co umím strojem generovat? Nemáme dostatek korpusů? (Nic o tom nevím, možná jsem úplně mimo, ale tohle mě teda nijak neohromilo ;) )
Gramatiky jsou z definice (a principu věci) o jazycích. Od bagru taky nebudu čekat aha moment na scéně v opeře. Dostatečné aha je myslím obsažené třeba v monadických parserech, ale to už zase klouže k matematice.
-
Gramatiky jsou z definice (a principu věci) o jazycích. Od bagru taky nebudu čekat aha moment na scéně v opeře.
Tak třeba to generování 3D objektů moc o jazycích není, že jo... a výsledky má pěkný. Co třeba generovat pomocí něčeho podobnýho levely v hrách? Nejenom grafiku, ale i questy? (gramatika mi zaručí, že mají nějakou "hratelnou" strukturu)
-
@zboj
Gramatiky nejsou jen o jazycích, ale mohou sloužit k popisu diskrétních závislostí. Viz zde http://www.stat.ucla.edu/~sczhu/papers/Reprint_Grammar.pdf
-
@zboj
Gramatiky nejsou jen o jazycích, ale mohou sloužit k popisu diskrétních závislostí. Viz zde http://www.stat.ucla.edu/~sczhu/papers/Reprint_Grammar.pdf
To je hezké, ale už stochastické. Jinak ano, gramatiky typu 0 slouží ke všemu, co zvládne Turingův stroj.
-
Gramatiky jsou z definice (a principu věci) o jazycích. Od bagru taky nebudu čekat aha moment na scéně v opeře.
Tak třeba to generování 3D objektů moc o jazycích není, že jo... a výsledky má pěkný. Co třeba generovat pomocí něčeho podobnýho levely v hrách? Nejenom grafiku, ale i questy? (gramatika mi zaručí, že mají nějakou "hratelnou" strukturu)
Nejenom hratelnou, ale i dynamickou, když budete on-line sledovat reakce hráčů a podle nich hodnotit použitá pravidla, může být průběh hry generován na základě reakce hráčů. Gramatika se může za běhu hry měnit, hra se bude učit.
-
Nejenom hratelnou, ale i dynamickou, když budete on-line sledovat reakce hráčů a podle nich hodnotit použitá pravidla, může být průběh hry generován na základě reakce hráčů. Gramatika se může za běhu hry měnit, hra se bude učit.
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 :)
-
Gramatiky jsou z definice (a principu věci) o jazycích. Od bagru taky nebudu čekat aha moment na scéně v opeře.
Tak třeba to generování 3D objektů moc o jazycích není, že jo... a výsledky má pěkný. Co třeba generovat pomocí něčeho podobnýho levely v hrách? Nejenom grafiku, ale i questy? (gramatika mi zaručí, že mají nějakou "hratelnou" strukturu)
Když se bavíme o generování, tak stojí za zmínku, že jakákoliv struktura rysů ve spojení s gramatikou s omezujícími podmínkami jde převést na BG. Tady si pak dovedu představit generování třeba krajin podle lidsky čitelného zadání.
-
Nejenom hratelnou, ale i dynamickou, když budete on-line sledovat reakce hráčů a podle nich hodnotit použitá pravidla, může být průběh hry generován na základě reakce hráčů. Gramatika se může za běhu hry měnit, hra se bude učit.
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 :)
"Arabské jaro" vyvolané strojově organizovanými manipulacemi na Twitteru.
-
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.
-
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.
-
Ž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.
-
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.
-
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).
-
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.
-
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.
-
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?
-
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ů.
-
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:
(https://www.gamedev.net/uploads/monthly_06_2013/ccs-209764-0-84996300-1370053229.jpg)
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 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:
(https://www.gamedev.net/uploads/monthly_06_2013/ccs-209764-0-84996300-1370053229.jpg)
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.
-
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.
-
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.
-
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!
-
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.
-
To jednoduše nepoznáte v ničem. Tak v tom není rozdíl, mezi seznamem a gramatikou.
V grafu mi stačí kouknout, jestli existuje cesta z počátečního stavu do akceptujícího. To vidím celkem hned i na složitějším grafu. Najít cestu od rytíře k princezně je standardní kvíz pro pětileté děti. V gramatice to na první pohled vidět není, člověk si musí projít všechny cesty, protože rychle nevidí, které jsou slepé. A to ani nemluvím o tom, že gramatika nemusí být zadaná v normální formě. To pak ani nejste schopný rychle posoudit, jestli je gramatika regulární nebo ne.
Nicméně, jestli se vám s gramatikami pracuje líp než s grafem přechodové funkce, tak vám to neberu, dělejte si to jak chcete. Klidně i z důvodu vroucí lásky k mocné Kálí, to je vaše věc. Když vám to někdo zaplatí... :)
-
To jednoduše nepoznáte v ničem. Tak v tom není rozdíl, mezi seznamem a gramatikou.
V grafu mi stačí kouknout, jestli existuje cesta z počátečního stavu do akceptujícího. To vidím celkem hned i na složitějším grafu. Najít cestu od rytíře k princezně je standardní kvíz pro pětileté děti. V gramatice to na první pohled vidět není, člověk si musí projít všechny cesty, protože rychle nevidí, které jsou slepé. A to ani nemluvím o tom, že gramatika nemusí být zadaná v normální formě. To pak ani nejste schopný rychle posoudit, jestli je gramatika regulární nebo ne.
Nicméně, jestli se vám s gramatikami pracuje líp než s grafem přechodové funkce, tak vám to neberu, dělejte si to jak chcete. Klidně i z důvodu vroucí lásky k mocné Kálí, to je vaše věc. Když vám to někdo zaplatí... :)
V grafu, který má třeba několik tisíc uzlů? Ale nepovídejte.
-
To jednoduše nepoznáte v ničem. Tak v tom není rozdíl, mezi seznamem a gramatikou.
V grafu mi stačí kouknout, jestli existuje cesta z počátečního stavu do akceptujícího. To vidím celkem hned i na složitějším grafu. Najít cestu od rytíře k princezně je standardní kvíz pro pětileté děti. V gramatice to na první pohled vidět není, člověk si musí projít všechny cesty, protože rychle nevidí, které jsou slepé. A to ani nemluvím o tom, že gramatika nemusí být zadaná v normální formě. To pak ani nejste schopný rychle posoudit, jestli je gramatika regulární nebo ne.
Nicméně, jestli se vám s gramatikami pracuje líp než s grafem přechodové funkce, tak vám to neberu, dělejte si to jak chcete. Klidně i z důvodu vroucí lásky k mocné Kálí, to je vaše věc. Když vám to někdo zaplatí... :)
V grafu, který má třeba několik tisíc uzlů? Ale nepovídejte.
Gramatiky jsou mnohem přehlednější u vyšších typů, protože jakmile se k automatu přidá zásobník, už není na první pohled vidět nic. U regulárních jazyků to asi bude případ od případu, takže pravdu máte (částečně) oba ;)
Ono vůbec jedna věc je zápis pro lidi a druhá pro počítač, taková BG s omezujícímí podmínkami se dá ekvivalentně zapsat jedním jediným pravidel (s hromadou podmínek), ale normální člověk tak nic implementovat nebude (aspoň doufám).
-
To jednoduše nepoznáte v ničem. Tak v tom není rozdíl, mezi seznamem a gramatikou.
V gramatice to na první pohled vidět není, člověk si musí projít všechny cesty, protože rychle nevidí, které jsou slepé. A to ani nemluvím o tom, že gramatika nemusí být zadaná v normální formě. To pak ani nejste schopný rychle posoudit, jestli je gramatika regulární nebo ne.
Nicméně, jestli se vám s gramatikami pracuje líp než s grafem přechodové funkce, tak vám to neberu, dělejte si to jak chcete. Klidně i z důvodu vroucí lásky k mocné Kálí, to je vaše věc. Když vám to někdo zaplatí... :)
Finta je v tom, ze ze tohle za tebe udela kazdy rozumny tool, ktery z te gramatiky generuje zdrojaky.
Popr. ti IDE prevede tu gramatiku na graf (klikaci).
PS: gramatika se preci jenom udrzuje mnohem snaz, nez definice prechodove fce.
-
V grafu, který má třeba několik tisíc uzlů? Ale nepovídejte.
Pokud by ten graf měl nekolik tisíc uzlů, tak by ta gramatika měla k desítce tisíc pravidel (z jednoho uzlu půjde zepár hran žejo). Poud budu brát 40 řádků na stránku, tak to máme někde kolem 2 až 3 tisíc stránek pravidel gramatiky. Tam jistě půjde tu cestu najít snadno :))))
-
Popr. ti IDE prevede tu gramatiku na graf (klikaci).
A proc by to dělal? Že by proto, že graf je přehlednější? :)))
-
U regulárních jazyků to asi bude případ od případu, takže pravdu máte (částečně) oba ;)
Nemáme, protože řeč je čistě o regulárních automatech/gramatikách :)
-
2 až 3 tisíc stránek
Pardon: set, ne tisíc
-
U regulárních jazyků to asi bude případ od případu, takže pravdu máte (částečně) oba ;)
Nemáme, protože řeč je čistě o regulárních automatech/gramatikách :)
...které explicitně zmiňuju. Nicméně taky se to dá říct tak, že pravdu nemáte ani jeden :)
-
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.
Gramatika je generativna, automat je akceptacny. Gramatikou sa opisuju mozne vstupy pre ten automat.
-
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.
Gramatika je generativna, automat je akceptacny. Gramatikou sa opisuju mozne vstupy pre ten automat.
Blbost, gramatika může být rekognoskativní (sic!) a automat generovat, to s tím vůbec nesouvisí.
-
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.
Gramatika je generativna, automat je akceptacny. Gramatikou sa opisuju mozne vstupy pre ten automat.
Blbost, gramatika může být rekognoskativní (sic!) a automat generovat, to s tím vůbec nesouvisí.
No, ak myslite, lol. Tak ok. Uz rozumiem, preco mam taky vysoky plat. Ano, niektore automaty mozu byt aj generativne, napriklad taky turingac, alebo LBA, ale akceptacnu gramatiku som este jakziv nevidel. (Kedze gramatika je opis a nie algoritmus) "Blbost" hovorte, viete komu ...
-
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.
Gramatika je generativna, automat je akceptacny. Gramatikou sa opisuju mozne vstupy pre ten automat.
Blbost, gramatika může být rekognoskativní (sic!) a automat generovat, to s tím vůbec nesouvisí.
No, ak myslite, lol. Tak ok. Uz rozumiem, preco mam taky vysoky plat. Ano, niektore automaty mozu byt aj generativne, napriklad taky turingac, alebo LBA, ale akceptacnu gramatiku som este jakziv nevidel. (Kedze gramatika je opis a nie algoritmus) "Blbost" hovorte, viete komu ...
Akceptační gramatika == PEG, je ji možno implementovat tak, že jde o zápis gramatiky a zároveň akceptační automat.
rule = Sequence(OneOrMore(Char('A')), Optional(Char('B'))) # rule => A*B?
ast = rule.parse(text)
-
Akceptační gramatika == PEG, je ji možno implementovat tak, že jde o zápis gramatiky a zároveň akceptační automat.
rule = Sequence(OneOrMore(Char('A')), Optional(Char('B'))) # rule => A*B?
ast = rule.parse(text)
Ah, vypinam root-a idem robit radsej nieco uzitocne. Tu to nema cenu.
-
Akceptační gramatika == PEG, je ji možno implementovat tak, že jde o zápis gramatiky a zároveň akceptační automat.
rule = Sequence(OneOrMore(Char('A')), Optional(Char('B'))) # rule => A*B?
ast = rule.parse(text)
Ah, vypinam root-a idem robit radsej nieco uzitocne. Tu to nema cenu.
Tak například funkce, nebo konstruktor objektu OneOrMore je pravidlo a zároveň část automatu, protože 'fyzicky' opakuje provádění či akceptaci pravidla, které do ní vložíte. Zároveň je to část automatu, a zároveň sémanticky vyjadřuje část pravidla. Nemáte zde zřetelně odděleno co je gramatika a co je automat, který ji přijímá, protože ten automat skládáte rovnou z pravidel gramatiky. Uvedené pravidlo OneOrMore z hlediska gramatiky je metasymbol, z hlediska automatu je to jasně definovaná akce nad stavy automatu (pravidly), a to, proveď pravidlo alespoň jednou dokud platí.
Co je na tom nesrozumitelného.
-
Co je na tom nesrozumitelného.
Když člověk mluví do dubu, tak je nesrozumitelné všechno.
-
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.
Gramatika je generativna, automat je akceptacny. Gramatikou sa opisuju mozne vstupy pre ten automat.
Blbost, gramatika může být rekognoskativní (sic!) a automat generovat, to s tím vůbec nesouvisí.
No, ak myslite, lol.
Na Slovensku se může říkat IT odborník někomu, kdo netuší, co to je Postův problém? Wow :o
-
Na Slovensku se může říkat IT odborník někomu, kdo netuší, co to je Postův problém? Wow :o
V cechach je expert kazdy na vsetko a vie pritom hovno.
-
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.
Gramatika je generativna, automat je akceptacny. Gramatikou sa opisuju mozne vstupy pre ten automat.
Blbost, gramatika může být rekognoskativní (sic!) a automat generovat, to s tím vůbec nesouvisí.
No, ak myslite, lol. Tak ok. Uz rozumiem, preco mam taky vysoky plat. Ano, niektore automaty mozu byt aj generativne, napriklad taky turingac, alebo LBA, ale akceptacnu gramatiku som este jakziv nevidel. (Kedze gramatika je opis a nie algoritmus) "Blbost" hovorte, viete komu ...
Akceptační gramatika == PEG, je ji možno implementovat tak, že jde o zápis gramatiky a zároveň akceptační automat.
rule = Sequence(OneOrMore(Char('A')), Optional(Char('B'))) # rule => A*B?
ast = rule.parse(text)
Aniž bych chtěl zbytečně reagovat na čobolské bláboly, hodí se poznamenat, že gramatiky obecně jsou deklarativní, a tedy vhodné pro jak generování, tak analýzu. Název generativní gramatika pochází od Chomského (jeden z těch "zlých" Židů, kterého zdejší antisemitský čobol-troll ignoruje), který sám přešel v 90. letech ke gramatikám rekognoskativním (v rámci lingvistiky se tento směr nazývá minimalismus). Automaty jsou pochopitelně stejně tak generativní nebo rekognoskativní, což ví každý, kdo tuší něco například o regulárních výrazech.
-
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.
Gramatika je generativna, automat je akceptacny. Gramatikou sa opisuju mozne vstupy pre ten automat.
Blbost, gramatika může být rekognoskativní (sic!) a automat generovat, to s tím vůbec nesouvisí.
No, ak myslite, lol. Tak ok. Uz rozumiem, preco mam taky vysoky plat. Ano, niektore automaty mozu byt aj generativne, napriklad taky turingac, alebo LBA, ale akceptacnu gramatiku som este jakziv nevidel. (Kedze gramatika je opis a nie algoritmus) "Blbost" hovorte, viete komu ...
Akceptační gramatika == PEG, je ji možno implementovat tak, že jde o zápis gramatiky a zároveň akceptační automat.
rule = Sequence(OneOrMore(Char('A')), Optional(Char('B'))) # rule => A*B?
ast = rule.parse(text)
Aniž bych chtěl zbytečně reagovat na čobolské bláboly, hodí se poznamenat, že gramatiky obecně jsou deklarativní, a tedy vhodné pro jak generování, tak analýzu. Název generativní gramatika pochází od Chomského (jeden z těch "zlých" Židů, kterého zdejší antisemitský čobol-troll ignoruje), který sám přešel v 90. letech ke gramatikám rekognoskativním (v rámci lingvistiky se tento směr nazývá minimalismus). Automaty jsou pochopitelně stejně tak generativní nebo rekognoskativní, což ví každý, kdo tuší něco například o regulárních výrazech.
Vy si ozaj zasluzite svojho prezidenta.
-
Zboj, a poprosim linky, aj ked sa vyjadrujete ako pepanske hovado, "rekogniskativni gramatiky" ma zaujimaju.
Alebo poprosim anglicky nazov. (V normalnom nazvoslovi sa to lepsie dohladava)
-
Zboj. Netreba, uz mam relevantny dokument, stacilo napisat, ze mam starsie vedomosti. Predsa len som dlhsie od skoly A nie hned "blbost".
https://pdos.csail.mit.edu/~baford/packrat/popl04/peg-popl04.pdf