Formálne jazyky a preklada?e

[antil kiprest]

treba napisat akym postupom (pouzitim akych pravidiel) sme sa dostali k vyslednemu vyrazu a + b - c = d * e  

EDIT: cize potrebujeme bezkontextovu gramatiku

tak skusim

a+b-c=d*e

expr -> eq [("+" | "-" | "*" ) expr]
eq -> id ["=" id]
id -> ("a" | "b" | ... | "z" )


             expr
          /    |    \
         eq   "+"   expr
        /          /   |    \
     id        eq    "-"    expr
     /        /            /   |    \
   "a"      id          eq   "*"   eq
            /         /  |  \          \
          "b"       id  "="  id         id
                   /             \          \
                "c"             "d"        "e"


heh no neviem.. len moja dedukcia z uvedeneho   

[OsamelyVlk]

1. Syntakticky analyzator so zotavenim pre jazyk LL(1): A->{Db l Ca} kde H(D) a H(C) su zname.
Urcit vstah medzi FIRST(D) a H(D) - to iste aj pre FIRST(C) a H(C)


??

toto nemam  , ale druha otazka nie je ten obr. co si postol ?
                         tretia to ani nerobme to kto neve v cvikach najde...
                         stvrta tam to je co som postol ze som k nim nasel daco v prednaskach ale nevem odpovedat z toho na tu otazku

[Mike]

             expr
          /    |    \
         eq   "+"   expr
        /          /   |    \
     id        eq    "-"    expr
     /        /            /   |    \
   "a"      id          eq   "*"   eq
            /         /  |  \          \
          "b"       id  "="  id         id
                   /             \          \
                "c"             "d"        "e"

mne vyslo tak isto 

[Mike]

ale druha otazka nie je ten obr. co si postol ?

ano

tretia to ani nerobme to kto neve v cvikach najde...

3. Pre gramatiku : retazec sa zacina "a" a konci "c" medzi nimi je aspon jedno "b" trebalo urcit prechodovy diagram, urobit konecnostavovy deterministicky  automat a aj pre ten urobit prechodovy diagram

stvrta tam to je co som postol ze som k nim nasel daco v prednaskach ale nevem odpovedat z toho na tu otazku

v ktorej prednaske to bolo ?

[OsamelyVlk]

ale druha otazka nie je ten obr. co si postol ?

ano

tretia to ani nerobme to kto neve v cvikach najde...

3. Pre gramatiku : retazec sa zacina "a" a konci "c" medzi nimi je aspon jedno "b" trebalo urcit prechodovy diagram, urobit konecnostavovy deterministicky  automat a aj pre ten urobit prechodovy diagram

stvrta tam to je co som postol ze som k nim nasel daco v prednaskach ale nevem odpovedat z toho na tu otazku

v ktorej prednaske to bolo ?

prednaska c.10. (fotky) a je to slide  c.15/18.  selekcia kodu pre skoky...

[antil kiprest]

mne vyslo tak isto  beer1

eej, parada!! 

1. Syntakticky analyzator so zotavenim pre jazyk LL(1): A->{Db l Ca} kde H(D) a H(C) su zname.
Urcit vstah medzi FIRST(D) a H(D) - to iste aj pre FIRST(C) a H(C)


??

hm vztah medzi first(D) a H(D) ??  nie je to len toto  H(D) = first(D) - E   ?

[ohen]

postfix:  a  b    c = d   e * -  +
[/quote]
ten postfix mas asi zly, = ma byt za "d", nie pred...  a b c d = e * - +

[Mike]

Este ma zaujima ten syntakticky analyzator so zotavenim pre jazyk LL(1): A->{Db l Ca} kde H(D) a H(C) su zname.

[antil kiprest]

Este ma zaujima ten syntakticky analyzator so zotavenim pre jazyk LL(1): A->{Db l Ca} kde H(D) a H(C) su zname.

void A(symset K){

check(HD | b | HC | a | K);

while(sym& (HD | HC)){
   if(sym & HD){
   D(HD | b | HC | a | K );
   if(sym == b)
      getsymbol();
   else
      error(HD | b | HC |a| K);
   }
   if(sym & HC){
   C(HD | b |HC | a | K);
   if(sym == a)
        getsymbol();
   else
       error(HD| b |HC |a |K);

   check(HD | b | HC |a| K);
   }
}


nejak takto??
]

[ludko]

No snazil som sa to nejako zosumarizovat co zatial sa tu vypracovala + este som nasiel jeden vypracovany variant

tak tu je zip.ko

Ak este mate niektore otazky vypracovane co tam niesu tak by ste to mohli doplnit a re-uploadnut ...

...

http://www.edisk.sk/sk/stahni/77239/testy.zip_606.73KB.html

[ohen]

Este ma zaujima ten syntakticky analyzator so zotavenim pre jazyk LL(1): A->{Db l Ca} kde H(D) a H(C) su zname.

myslym, ze skor takto, opravte ma ak sa mylim:

void A(symset K){

check (HD | HC | K); <- "b", "a" by som nedaval, lebo je tam switch a nic za D a C sa nevykona, ak tam jedna z tych dvoch mnozin nebude

while((sym) & (HD | b | HC | a)){

  check(HD | HC | K); 
  switch (sym){

   case HD: D(HD | b | HC | a | K );
   if(sym == b)
      getsymbol();
   else
      error(HD | b | HC |a| K);   <- neviem ci ma vyznam error
 
   case HC: C(HD | b |HC | a | K);
   if(sym == a)
        getsymbol();
   else
       error(HD| b |HC |a |K);   <- to iste, neviem ci ma vyznam error

   check(HD | b | HC |a| K);
   }
}



]

[antil kiprest]

ok, este mi zopar veci zo zotavenia nie je jasne, takze otazka do plena:

A -> X [a Y] {Z}

A(symbolset K){

X(a | HY | HZ | K);

check(a| HZ | K);

if(sym == a ) {
   getsymbol();
   Y(HZ | K);
}

check(HZ | K);
while (sym & (HZ)){
   Z(HZ |K);
   check(HZ | K);
}


}

hned hore v check(a | HZ | K);  nema byt HY pretoze sa Y v [a Y] vyskytuje az za a, cise je tam if a tak dalej... s tym suhlasim, aj z prednasok mi to takto vyplynulo..

ale ako je to s volanim X(a | HZ | HY | K); ?? ma alebo nema tam byt HY ?  ma zmysel ze sa bude zotavovat na Y, ked nenajde v retazci 'a' ?

co si o tom myslite?

[antil kiprest]

a ohen, mas pravdu s tym checkom, tam nemaju byt 'a' a 'b'
ten switch som s nepochopitelnych dovodou nahradil ifmy    proste chyba okej,   ale errory vyznam urcite maju... ved predsa ked cakas 'a' vyifujes to a zistis ze tam nie je, tak je to chyba, a vypises error

[antil kiprest]

dalej otazka 3. Upravte bezkontext gramatiku  A-> abC | a{B} na LL(1). Pre upravenu gramatiku spravit syntakticky analyzator pomocou procedur Check a Error.

ten prevod tu uz bol, cize  A -> a (bC | {B})

a synt anal

void A(symset K){

if(sym == a)
   getsymbol();
else
   error(b | HB | K);

check(b | HB | K);

switch (sym){
   case b:
       getsymbol();
       C(K);
       break;
   case HB:
       while(sym & HB){
           B(HB | K);
           check(HB | K);
       }
       break;
   default:                    //tu ma zmiatlo to ze v tej alternative moze nastat aj prazdna vetva, cize case HD nastane len ak tam bude
       if(!(sym & K))         //aspon jedno volanie B ale ak by to bol koniec retazca, tak by ten klasicky default vypisal error,
           error(K);           //co by nebolo korektne... jedine co ma napadlo ako osetrenie je takato podmienka.. nazory??
}

}

[elros]

ok, este mi zopar veci zo zotavenia nie je jasne, takze otazka do plena:

A -> X [a Y] {Z}

A(symbolset K){

X(a | HY | HZ | K);

check(a| HZ | K);

if(sym == a ) {
   getsymbol();
   Y(HZ | K);
}

check(HZ | K);
while (sym & (HZ)){
   Z(HZ |K);
   check(HZ | K);
}


}

hned hore v check(a | HZ | K);  nema byt HY pretoze sa Y v [a Y] vyskytuje az za a, cise je tam if a tak dalej... s tym suhlasim, aj z prednasok mi to takto vyplynulo..

ale ako je to s volanim X(a | HZ | HY | K); ?? ma alebo nema tam byt HY ?  ma zmysel ze sa bude zotavovat na Y, ked nenajde v retazci 'a' ?

co si o tom myslite?

Jasne, to HY nema byt ani tam
Sorry som si to vtedy nevsimol, ze to tam mam

[elros]

       break;
   default:                    //tu ma zmiatlo to ze v tej alternative moze nastat aj prazdna vetva, cize case HD nastane len ak tam bude
       if(!(sym & K))         //aspon jedno volanie B ale ak by to bol koniec retazca, tak by ten klasicky default vypisal error,
           error(K);           //co by nebolo korektne... jedine co ma napadlo ako osetrenie je takato podmienka.. nazory??
}

}

Tam do toho defaultu daj len break; , lebo ano, moze nastat aj prazdna vetva, cize error nie je namieste. Do toho switcha uz vdaka tomu checku pred nim nepride nic co tam nema ist, cize ta podmienka v defaulte by bola zbytocna ajtak.

[antil kiprest]

       break;
   default:                    //tu ma zmiatlo to ze v tej alternative moze nastat aj prazdna vetva, cize case HD nastane len ak tam bude
       if(!(sym & K))         //aspon jedno volanie B ale ak by to bol koniec retazca, tak by ten klasicky default vypisal error,
           error(K);           //co by nebolo korektne... jedine co ma napadlo ako osetrenie je takato podmienka.. nazory??
}

}

Tam do toho defaultu daj len break; , lebo ano, moze nastat aj prazdna vetva, cize error nie je namieste. Do toho switcha uz vdaka tomu checku pred nim nepride nic co tam nema ist, cize ta podmienka v defaulte by bola zbytocna ajtak.

vidis, to ma nenapadlo, jake jednoduche fajn, diks

[antil kiprest]

X -> A[B|C] E 

X(symbolset K){

A(HB | HC | HE | K);

check(HB| HC | HE | K);

if(sym in (HB or HC) ) {
   switch(symbol){
      case HB: B(HE| K); break;
      case HC: C(HE| K); break;
      default: error(HE | K);break;               //nie je tento error zbytocny??
   }
}

E(K);

}

[Mike]

Tak ako ma byt ten priklad spravne ?

dalej otazka 3. Upravte bezkontext gramatiku  A-> abC | a{B} na LL(1). Pre upravenu gramatiku spravit syntakticky analyzator pomocou procedur Check a Error.

ten prevod tu uz bol, cize  A -> a (bC | {B})

[antil kiprest]

Tak ako ma byt ten priklad spravne ?

dalej otazka 3. Upravte bezkontext gramatiku  A-> abC | a{B} na LL(1). Pre upravenu gramatiku spravit syntakticky analyzator pomocou procedur Check a Error.

ten prevod tu uz bol, cize  A -> a (bC | {B})

no ja myslim ze toto je OK :

void A(symset K){

if(sym == a)
   getsymbol();
else
   error(b | HB | K);

check(b | HB | K);

switch (sym){
   case b:
       getsymbol();
       C(K);
       break;
   case HB:
       while(sym & HB){
           B(HB | K);
           check(HB | K);
       }
       break;
   default: break;     
}

}

[ohen]

a ohen, mas pravdu s tym checkom, tam nemaju byt 'a' a 'b'
ten switch som s nepochopitelnych dovodou nahradil ifmy    proste chyba okej,   ale errory vyznam urcite maju... ved predsa ked cakas 'a' vyifujes to a zistis ze tam nie je, tak je to chyba, a vypises error

na tie errory som sa pytal, lebo som si nebol isty...  a ohladom toho HY co si pisal predtym by to aj mna zaujimalo... ci pri X ma byt zahrnute HY. dobra poznamka

[antil kiprest]

este by som sa vratil k tomuto A->{Db l Ca}


void A(symset K){

check (HD | HC | K);

while((sym) & (HD | HC )){    //tu by tiez nemaly byt 'a' ani 'b' myslim, switch nepusti

  check(HD | HC | K);             //tymto checkom si nie som isty..  jeden taky je uz pred while a navyse podmienka wo while zarucuje ze by zbehol bez
                                           //  chyby.. taze je asi zbytocny
  switch (sym){

   case HD: D(HD | b | HC | K );   //tu by malo byt 'b' ale nie 'a', pretoze 'b' v tejto vetve nasleduje ale 'a' je zase az sa switchom
   if(sym == b)
      getsymbol();
   else
      error(HD | HC | K);        //tu opat nema zmysel 'a' ani 'b'
 
   case HC: C(HD |HC | a | K);     //tu je to naopak, cize  'b' nie, 'a' ano
   if(sym == a)
        getsymbol();
   else
       error(HD| HC |K);     //tu opat nema zmysel 'a' ani 'b'

   check(HD | HC | K);    /a tento chcek by mal byt ten isty ako pred while
   }
}


co myslite??

[antil kiprest]

a ohen, mas pravdu s tym checkom, tam nemaju byt 'a' a 'b'
ten switch som s nepochopitelnych dovodou nahradil ifmy    proste chyba okej,   ale errory vyznam urcite maju... ved predsa ked cakas 'a' vyifujes to a zistis ze tam nie je, tak je to chyba, a vypises error

na tie errory som sa pytal, lebo som si nebol isty...  a ohladom toho HY co si pisal predtym by to aj mna zaujimalo... ci pri X ma byt zahrnute HY. dobra poznamka

HY tam nema byt, uz to bolo zodpovedane

[antil kiprest]

a este k tej istej ulohe podotazka urcit vstah medzi FIRST(D) a H(D) - to iste aj pre FIRST(C) a H(C)

any suggestions??

mne to pride ako toto: H(D) = FIRST(D) - e (prazdny symbol)   .. ale nie som si isty ci je rec o tomto

[antil kiprest]

3. Pre gramatiku : retazec sa zacina "a" a konci "c" medzi nimi je aspon jedno "b"
trebalo urcit prechodovy diagram, urobit konecnostavovy deterministicky  automat a aj pre ten urobit prechodovy diagram

viem ze je to banalna otazka, ale nejak si to presne nepamatam, k tomu DKA staci toto?