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
|
Zaslal: 12. září 2007, 17:42:56 Předmět: LL(x) gramatiky -> vyhodnocovani zleva |
|
|
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 |
|
|
Marty
Založen: 28. 07. 2007 Příspěvky: 20
|
Zaslal: 12. září 2007, 18:14:39 Předmět: |
|
|
Sakra to je hrozny jak to clovek vsechno zapomina . 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
Jen doufam ze jsem neco nenapsal blbe |
|
Návrat nahoru |
|
|
johnnash
Založen: 30. 07. 2007 Příspěvky: 80
|
Zaslal: 12. září 2007, 18:20:35 Předmět: |
|
|
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 |
|
|
MD
Založen: 29. 07. 2007 Příspěvky: 437 Bydliště: Praha
|
Zaslal: 12. září 2007, 20:11:55 Předmět: Re: LL(x) gramatiky -> vyhodnocovani zleva |
|
|
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 |
|
|
Yossarian
Založen: 28. 07. 2007 Příspěvky: 274 Bydliště: Šalingrad
|
Zaslal: 13. září 2007, 18:06:15 Předmět: Re: LL(x) gramatiky -> vyhodnocovani zleva |
|
|
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
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 |
|
|
Manox
Založen: 30. 07. 2007 Příspěvky: 140 Bydliště: Brno
|
Zaslal: 13. září 2007, 18:22:49 Předmět: |
|
|
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 |
|
|
Augi
Založen: 28. 07. 2007 Příspěvky: 782 Bydliště: Čerčany
|
Zaslal: 13. září 2007, 18:51:59 Předmět: |
|
|
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 |
|
|
Yossarian
Založen: 28. 07. 2007 Příspěvky: 274 Bydliště: Šalingrad
|
Zaslal: 13. září 2007, 19:13:35 Předmět: |
|
|
manox: ja uz kompiler v podstate mam, jenze ted sem pridal podporu pro objekty a nestacil sem se divit
augi: ze by c# bylo LL(1) se mi nezda. nicmene diky za radu, podivam se na to |
|
Návrat nahoru |
|
|
Augi
Založen: 28. 07. 2007 Příspěvky: 782 Bydliště: Čerčany
|
Zaslal: 13. září 2007, 19:23:17 Předmět: |
|
|
No už to je pár let zpátky, tak možná melu kraviny 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 |
|
|
Peta
Založen: 28. 07. 2007 Příspěvky: 154 Bydliště: V prvnim patre hned vedle koupelny.
|
Zaslal: 13. září 2007, 19:53:57 Předmět: |
|
|
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 |
|
|
MD
Založen: 29. 07. 2007 Příspěvky: 437 Bydliště: Praha
|
Zaslal: 13. září 2007, 19:56:19 Předmět: |
|
|
Jestli je C# skutecne LL(1), to si netroufam odhadnout, ale urcite se da celkem jednoduse analyzovat shora dolu ala LL(1) 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 |
|
|
MD
Založen: 29. 07. 2007 Příspěvky: 437 Bydliště: Praha
|
Zaslal: 13. září 2007, 20:05:16 Předmět: Re: LL(x) gramatiky -> vyhodnocovani zleva |
|
|
Yossarian napsal: |
a jetPAG, ktery nyni pouzivam, ale evidentne neresi muj problem |
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 |
|
|
Augi
Založen: 28. 07. 2007 Příspěvky: 782 Bydliště: Čerčany
|
Zaslal: 13. září 2007, 20:31:51 Předmět: |
|
|
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 |
|
Návrat nahoru |
|
|
MD
Založen: 29. 07. 2007 Příspěvky: 437 Bydliště: Praha
|
Zaslal: 13. září 2007, 20:41:56 Předmět: |
|
|
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 |
|
|
Augi
Založen: 28. 07. 2007 Příspěvky: 782 Bydliště: Čerčany
|
Zaslal: 13. září 2007, 21:08:15 Předmět: |
|
|
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ě |
|
Návrat nahoru |
|
|
|