Gramatiky v IT

logix

Gramatiky v IT
« kdy: 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ý.


Santiago

Re:Gramatiky v IT
« Odpověď #1 kdy: 11. 05. 2017, 18:25:41 »
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 .

Ivan Nový

Re:Gramatiky v IT
« Odpověď #2 kdy: 11. 05. 2017, 18:29:48 »
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.



zboj

  • *****
  • 1 507
    • Zobrazit profil
    • E-mail
Re:Gramatiky v IT
« Odpověď #3 kdy: 11. 05. 2017, 19:14:46 »
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í.

Ivan Nový

Re:Gramatiky v IT
« Odpověď #4 kdy: 11. 05. 2017, 19:26:48 »
@zboj

A nemá LL i LR parser spíše lineární náročnost? Ovšem kubickou má CYK, Earley.


zboj

  • *****
  • 1 507
    • Zobrazit profil
    • E-mail
Re:Gramatiky v IT
« Odpověď #5 kdy: 11. 05. 2017, 19:28:25 »
@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.

@

Re:Gramatiky v IT
« Odpověď #6 kdy: 11. 05. 2017, 20:34:09 »
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?

Ivan Nový

Re:Gramatiky v IT
« Odpověď #7 kdy: 11. 05. 2017, 20:39:27 »
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 :-)))

zboj

  • *****
  • 1 507
    • Zobrazit profil
    • E-mail
Re:Gramatiky v IT
« Odpověď #8 kdy: 11. 05. 2017, 21:41:19 »
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.

meh

Re:Gramatiky v IT
« Odpověď #9 kdy: 11. 05. 2017, 21:54:29 »
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 ...

andy

Re:Gramatiky v IT
« Odpověď #10 kdy: 11. 05. 2017, 22:50:58 »
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....

zboj

  • *****
  • 1 507
    • Zobrazit profil
    • E-mail
Re:Gramatiky v IT
« Odpověď #11 kdy: 11. 05. 2017, 23:08:46 »
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.

Ivan Nový

Re:Gramatiky v IT
« Odpověď #12 kdy: 12. 05. 2017, 06:01:36 »
@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.

Lemming

Re:Gramatiky v IT
« Odpověď #13 kdy: 12. 05. 2017, 08:02:42 »
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"!

balki

Re:Gramatiky v IT
« Odpověď #14 kdy: 12. 05. 2017, 11:07:38 »
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.