.[ ČeskéHry.cz ].
LL(x) gramatiky -> vyhodnocovani zleva
Jdi na stránku 1, 2  Další
 
odeslat nové téma   Odpovědět na téma    Obsah fóra České-Hry.cz -> Obecné
Zobrazit předchozí téma :: Zobrazit následující téma  
Autor Zpráva
Yossarian



Založen: 28. 07. 2007
Příspěvky: 274
Bydliště: Šalingrad

PříspěvekZaslal: 12. září 2007, 17:42:56    Předmět: LL(x) gramatiky -> vyhodnocovani zleva Odpovědět s citátem

Zdravim, sice to moc nesouvisi s hrami, ale snad mi nekdo pomuze:
mam LL(n) ( kde n je aktualne 4.. ) gramatiku, s nasledujicim pravidlem:
kód:

E: F '->' E
E: F
F: text

kde '->' a text jsou terminaly

ktera mi vyhodnoti:
a->b->c->d jako (a->(b->(c->d)))
coz ovsem nechci, ale v pripade ze bych gramatiku prepsal na
kód:

E: E '->' F
E: F
F: text

ktera by (teoreticky) mela vyhodnocovat vyraz zleva, a ne zprava,
tak se u LL gramatiky logicky zaseknu na left-recursion..

jde tento problem pomoci LL(x) nejak resit, nebo zpusob vyhodnocovani vychazi primo z gramatiky a musel bych pouzit nejakou jinou?
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
Marty



Založen: 28. 07. 2007
Příspěvky: 20

PříspěvekZaslal: 12. září 2007, 18:14:39    Předmět: Odpovědět s citátem

Sakra to je hrozny jak to clovek vsechno zapomina Smile . Tak jsem zapatral na wiki a ano je to dano gramatikou, proto se taky jmenuje LL. Prvni L znama text se cte z leva, druhe L gramatika vytvari levou derivaci tzn. to co jsi napsal a->b->c->d jako (a->(b->(c->d))). Takze pokud to chces opacne asi budes muset pouzit LR gramatiku. Coz je v podstate ta druha co jsi napsal, protoze LR gramatice leva rekurze nevadi Smile

Jen doufam ze jsem neco nenapsal blbe Very Happy
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
johnnash



Založen: 30. 07. 2007
Příspěvky: 80

PříspěvekZaslal: 12. září 2007, 18:20:35    Předmět: Odpovědět s citátem

Nevim co je tvym cilem, a pokud by slo o vyhodnocovani jenom takhle jednoduchych vyrazu tak bych zkusil precedencni syntaktickou analyzu.
Je pomerne jednoducha a umi toho jakz takz dost.
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
MD



Založen: 29. 07. 2007
Příspěvky: 437
Bydliště: Praha

PříspěvekZaslal: 12. září 2007, 20:11:55    Předmět: Re: LL(x) gramatiky -> vyhodnocovani zleva Odpovědět s citátem

co takhle?:
kód:

E: FG
G: ->FG
G: prazdne slovo
F: text

Neni to sice uplne opacne uzavorkovani, ale pri zpracovani G bys mel mit to, co potrebujes.
_________________
- play with objects - www.krkal.org -
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
Yossarian



Založen: 28. 07. 2007
Příspěvky: 274
Bydliště: Šalingrad

PříspěvekZaslal: 13. září 2007, 18:06:15    Předmět: Re: LL(x) gramatiky -> vyhodnocovani zleva Odpovědět s citátem

MD napsal:
co takhle?:
kód:

E: FG
G: ->FG
G: prazdne slovo
F: text

Neni to sice uplne opacne uzavorkovani, ale pri zpracovani G bys mel mit to, co potrebujes.
bohuzel, nepovedlo se mi to zpracovat.


takto: ja v podstate LL(x) gramatiku nepotrebuju. pouzil jsem ji, protoze sem si pro ni nasel pomerne kvalitni parser a generator c++ kodu. problematika gramatik je na to, abych si napsal parser vlastni, pro me prilis slozita, a mezi znamymi resenimi sem nasel jenom yacc/bison pro LALR(1), a jetPAG, ktery nyni pouzivam, ale evidentne neresi muj problem Sad

nenapsal/nepouzil nekdo z vas nekdy gramaticky parser (googloval jsem, ale moc jich neexistuje) vhodny pro parsovani c-like jazyku, a nebyl by mi ochoten poradit, jak se k nejakemu takovemu dostat?
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
Manox



Založen: 30. 07. 2007
Příspěvky: 140
Bydliště: Brno

PříspěvekZaslal: 13. září 2007, 18:22:49    Předmět: Odpovědět s citátem

Delali jsme na FIT komplet cely prekladac pro jazyk podobny C

kód:
func suma a, b is int : int : <<
  result = a+b;
>>
 
func prog : <<
vars a is int;
  Print("\nZadej cislo 1: ")
  a = readInt();
  Print("Zadej cislo 2: ")
  a = suma(a, readInt());
  Print("Vysledek souctu je: " + str(a) + "\n")
>>
   

takhle mela vypadat syntax, mam k nemu i gramatiku, ale nevim, jestli je tohle ta spravna finalni verze, mela by byt LL(1)



kód:
S ? startovací symbol
E ? prázdný řetězec


S ? global <dek>
S ? func <funkce>
S ? func prog : <deklarace> <telo>
<funkce> ? ID <dek> : <typ> <deklarace> <telo>
<deklarace> ? VARS <dek>
<deklarace> ? E
<dek> ? ID <dalsiID> is <typ> <dalsidek>
<dalsiID> ? , ID <dalsiID>
<dalsiID> ? E
<dalsidek> ? ; <dek>
<dalsidek> ? E
<typ> ? int
<typ> ? string
<typ> ? void


<telo> ? << <prikaz> >>
<prikaz> ? E
<prikaz> ? if ( <vyraz> ) <prikaz> <else> endif <prikaz>
<else> ? else <prikaz>
<else> ? E
<prikaz> ? while ( <vyraz> ) <prikaz> wend <prikaz>
<prikaz> ? ID ( <vyraz> <dalsivyraz> ) <prikaz>
<dalsivyraz> ?  , <vyraz>
<dalsivyraz> ? E
<prikaz> ? Str (? ID ?) <prikaz>
<prikaz> ? ReadStr() <prikaz>
<prikaz> ? ReadInt() <prikaz>
<prikaz> ? Print (? ID ?) <prikaz>
<prikaz> ? ID = <vyraz> ; <prikaz>



<vyraz> ? <vyraz> || <vyraz1>
<vyraz> ? <vyraz1>
<vyraz1> ? <vyraz1> && <vyraz2>
<vyraz1> ? <vyraz2>
<vyraz2> ? not <vyraz3>
<vyraz2> ? <vyraz3>
<vyraz3> ? <vyraz3> = = <vyraz4>
<vyraz3> ? <vyraz3> <> <vyraz4>
<vyraz3> ? <vyraz4>
<vyraz4> ? <vyraz4> > <vyraz5>
<vyraz4> ? <vyraz4> >= <vyraz5>
<vyraz4> ? <vyraz4> < <vyraz5>
<vyraz4> ? <vyraz4> =< <vyraz5>
<vyraz4> ? <vyraz5>
<vyraz5> ? <vyraz5> + <vyraz6>
<vyraz5> ? <vyraz5> - <vyraz6>
<vyraz5> ? <vyraz6>
<vyraz6> ? <vyraz6> * <vyraz7>
<vyraz6> ? <vyraz6> mod <vyraz7>
<vyraz6> ? <vyraz6> div <vyraz7>
<vyraz6> ? <vyraz7>
<vyraz7> ? - <vyraz8>
<vyraz7> ? <vyraz8>
<vyraz8> ? ( <vyraz> )
<vyraz8> ? int
<vyraz8> ? string
<vyraz8> ? ID


a parser byl samozrejme casti ulohy, takze jsem ho psal ja, ale je to nekolik let zpatky a je napsany desnym stylem
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
Augi



Založen: 28. 07. 2007
Příspěvky: 782
Bydliště: Čerčany

PříspěvekZaslal: 13. září 2007, 18:51:59    Předmět: Odpovědět s citátem

Já jsem v rámci jedný semestrální práce napsal parser C# - výsledkem byla kostra dokumentace (takže jsem neřešil vnitřky metod). Ale vycházel jsem z gramatiky C#, kterou vydal Microsoft a v pohodě jsem to jako LL(1) implementoval a myslím, že by to šlo celý udělat jako LL(1). Tak co třeba zkusit mrknout na tu gramatiku C# a zkusit se inspirovat?
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
Yossarian



Založen: 28. 07. 2007
Příspěvky: 274
Bydliště: Šalingrad

PříspěvekZaslal: 13. září 2007, 19:13:35    Předmět: Odpovědět s citátem

manox: ja uz kompiler v podstate mam, jenze ted sem pridal podporu pro objekty a nestacil sem se divit Smile
augi: ze by c# bylo LL(1) se mi nezda. nicmene diky za radu, podivam se na to Smile
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
Augi



Založen: 28. 07. 2007
Příspěvky: 782
Bydliště: Čerčany

PříspěvekZaslal: 13. září 2007, 19:23:17    Předmět: Odpovědět s citátem

No už to je pár let zpátky, tak možná melu kraviny Wink Ale určitě jsem to implementovat klasickym rekurzivnim sestupem. Jestli jsem to dobře pochopil, tak se Ti nechce implementovat parser, ale implementace rekurzivního sestupu z pravidel gramatiky je fakt primitivní...
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
Peta



Založen: 28. 07. 2007
Příspěvky: 154
Bydliště: V prvnim patre hned vedle koupelny.

PříspěvekZaslal: 13. září 2007, 19:53:57    Předmět: Odpovědět s citátem

Ja jsem zase dělal interpret C++, taky rekurzivní sestup, LL(1) gramatika. Takže imho to půjde udělat určitě, jak říká Augi.

Jinak pro ten parser - v podstatě to uděláš tak, že neterminál je nějaká funkce a přepisovací pravidla v té funkci ošéfuješ switchem. Abys to ale mohl switchovat potrebujes znat FIRST a FOLLOW kazdyho pravidla/neterminalu. Asi takhle:

E -> +TE
E -> -TE
E -> T

void E (lexel dalsiLexElem) {

switch (dalsiLexElem) {
case elemPlus
case elemMinus
....
}

}

Snad jsem to nezvrtal, po sesti hodinach uceni uz mi to fakt moc nemysli...
_________________
Když je Ti smutno, otoč se tváří ke slunci a všechny stíny padnou za Tebe.


Naposledy upravil Peta dne 13. září 2007, 19:59:19, celkově upraveno 1 krát
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
MD



Založen: 29. 07. 2007
Příspěvky: 437
Bydliště: Praha

PříspěvekZaslal: 13. září 2007, 19:56:19    Předmět: Odpovědět s citátem

Jestli je C# skutecne LL(1), to si netroufam odhadnout, ale urcite se da celkem jednoduse analyzovat shora dolu ala LL(1) Wink Slozitost syntaxe Krkal C a syntaxe C# je hodne podobna. No a kompilator jsem nakonec delal taky jednoduchym rekurzivnim sestupem. Nevyhoda toho je, ze se to da strasne jednoduse zbastlit a pak byva problem jazyk rozsirovat o nove prvky. Flex a Bison trosku prozkoumaval tangent, tak treba poradi, kdyby bylo treba.
_________________
- play with objects - www.krkal.org -
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
MD



Založen: 29. 07. 2007
Příspěvky: 437
Bydliště: Praha

PříspěvekZaslal: 13. září 2007, 20:05:16    Předmět: Re: LL(x) gramatiky -> vyhodnocovani zleva Odpovědět s citátem

Yossarian napsal:
a jetPAG, ktery nyni pouzivam, ale evidentne neresi muj problem Sad

Tohle je divny. Ten tvuj problem je uplne zakladni vec, kterou je potreba zvladnout ve vsech jazycich. Neprehlid's tam nejakou featuru?
_________________
- play with objects - www.krkal.org -
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
Augi



Založen: 28. 07. 2007
Příspěvky: 782
Bydliště: Čerčany

PříspěvekZaslal: 13. září 2007, 20:31:51    Předmět: Odpovědět s citátem

MD napsal:
Nevyhoda toho je, ze se to da strasne jednoduse zbastlit a pak byva problem jazyk rozsirovat o nove prvky.
Právě proto bych se nevydal cestou ručního psaní funkcí rekurzivního sestupu, ale udělat si utilitu, která na základě daných pravidel gramatiky (a třeba pár nějakých nastavení) vygeneruje ten kód rekurzivního sestupu. Pak by se snad dodání nějaký fičury do jazyka mělo z hlediska parseru znamenat jen změnu pravidel a přegenerování rekurzivního sestupu.
To je ale jen teorie, v praxi jsem to nikdy nedělal, ale když se nad tím rychle zamyslím, tak nevidím důvod, proč by to nemělo fungovat Wink
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
MD



Založen: 29. 07. 2007
Příspěvky: 437
Bydliště: Praha

PříspěvekZaslal: 13. září 2007, 20:41:56    Předmět: Odpovědět s citátem

Augi: Kdyz to je porad jenom teorie. V praxi se tam potom dodava (kontroluje) semantika a ta mnohdy byva slozitejsi nez syntaxe, siri se atributy nahoru dolu, volaji se obsluzne funkce... Celkem bych si rad poslechl nejakou prezentaci na konkretnim prikladu s ukazkami kodu. Mohlo by to byt zajimave srovnani. Jeden muj kolega delal kompilator, kde oba postupy zkombinoval. Bohuzel jsme si nenasli cas na to, aby mi to poradne vysvetlil.
_________________
- play with objects - www.krkal.org -
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
Augi



Založen: 28. 07. 2007
Příspěvky: 782
Bydliště: Čerčany

PříspěvekZaslal: 13. září 2007, 21:08:15    Předmět: Odpovědět s citátem

No sémantický pravidla jsem uvažoval, ale to by ta utilita musela bejt asi fakt hodně robustní, takže je fakt možná lepší ten rekurzivní sestup naprgat ručně Smile
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
Zobrazit příspěvky z předchozích:   
odeslat nové téma   Odpovědět na téma    Obsah fóra České-Hry.cz -> Obecné Časy uváděny v GMT + 1 hodina
Jdi na stránku 1, 2  Další
Strana 1 z 2

 
Přejdi na:  
Nemůžete odesílat nové téma do tohoto fóra
Nemůžete odpovídat na témata v tomto fóru
Nemůžete upravovat své příspěvky v tomto fóru
Nemůžete mazat své příspěvky v tomto fóru
Nemůžete hlasovat v tomto fóru


Powered by phpBB © 2001, 2005 phpBB Group


Vzhled udelal powermac
Styl "vykraden" z phpBB stylu MonkiDream - upraveno by rezna