bison

(tato skolicka je dost mizerna, protoze byla jedna z prvnich)
Spis vas zmate, nez aby neco vysvetlila. Pouzitelny je asi jenom uvod, kde se zhruba dozvite co toje.
Byl bych opravdu rad kdyby nekdo napsal lepsi
Volne navazuje na skolicku o flexu


Obsah:


Co je bison?

Bison vznikl z yaccu jeho preprogramovanim a rozsirenim..to co tu budu psat bude nejspis platit i o nem protoze k rozsirenim se urcite nedostanu.. Jeho autori se snazili udelat chytry prostredek na rozpoznavani jazyku vseho druhu. vychazi to vlastne i z jmena-yacc=Yet another compiler compiler. Pokud se kouknete na konfigurace xwindows nebo dosemu nebo pustite compiler pak vezte ze to vsechno ma nasvedomi prave bison.

praci si autori vyrazne ulehcili tim ze bison nepracuje ze slovy. Kazdy prikaz je vlastne jedno pismeno. V pripade ze jsou treba viceznake prikazy musi se napred prevedst na integer hodnotami funkci yylex. Ktomu slouzi flex. Takze kdyby jste chteli udelat prekladac cecka napred je treba napsat v lexu program, ktery ze slova int udela cislo o hodnote konstanty INT. Pak je prace mnohem mnohem jednodussi a v tom spatruju silu toho navrhu.

Symboly

Tazdy znak vstupu(je to integer) je tedy token. Z nich se delaji sumboly. symboly nejsou jenom /%# jak je tomu u barvicek u borlandu ale vsechno. Symboly muzou byt terminating nebo nonterminating.

Terminal symbol je token. Nezto non terminal symbol je nekolik terminal symbolu. Taky se nazyva grouping. takze priklad pro C:
(jeste musim dodat ze rozdil mezi terminal symbolem a tokenem je v tom, ze terminal symbol nejakeho jmena muze byt reprezentovan ruznyma tokena)

je tu nekolik tokenu:
identifikatory,konstanty(ciselny,retezcovy),klicovy slova,operatory a znaminka jako zavorky atd.

V compileru cecka se tedy definujou symboly:
identifier,number,string a vsechny klicova slova operatory a zavorky
takze takhle nejak se rozdeluje ceckarskej programecek:
int - klicove slovo int

main(x) - identifikator,zavorka,identifikator,)
{ - oteviraci_zavorka
 return x;/*keyword return,identifier,,strednik
} - zaviraci zavorka
no a ted jsou v cecku groupingy:
expresion,statement,declaration a function definition tyhle casti asi kazdej zna z errorovych hlasek. Jsou to tedy nonterminal symboly

abych pro jistotu vysvetlil vyznam priklad:
po function definition je declaration a potom statement(zacina {) v nem jsou expresion-treba to x ale x+x ja taky expresion pro kazdej takovejhle nonterminal symbol musime napsat pravidla, jak se dela takze pisem neco jako statement se zklada z klicoveho slova return,expresion a stredniku. Samozdrejme popis takovych pravidel zrovna pro cecko uz neni takova hracka ale videl jsem zdrojaky a neni to zas tak zly. Pravidla(rule) muzou byt rekurzivni atd...on si to bison nejak prebere. Muzeme nadofinovat start symbol-napriklad v cecku start symbol nebude expresion protoze program 1+1 je blbost

pravidla

kzdej nonterminal symbol dostane jmeno-pro expresion muzeme pouzit expr atd.. pouzivaji se maly pismena.
Terminal symboly jsou tokeny a pisou se velkejma-treba INTEGER a mame tu taky terminal symbol error. Asi kazdej vi co dela. taky pro terminal symbol se daji pouzit pismena treba `a` to ma vyhodu ze se nemusi definovat..vetsinou se to pouziva pro `+` `-` a ostatni jednoznakovy veci

priklad pro return:
return se pise return(hodnota nebo vyraz=expresion) ; tedy:

stmt:   RETURN expr ';'
tedy jsme z returnu udelali statement..

Sematic value

Treba cislo v parseru prevedeme na NUMBER ale kam hodit jeho hodnotu? od toho jsou tu sematic values samozdrejme ze tyto hodnoty se daji pridelovat i jinym symbolum a groupingum tak jak to protrebuje program..hodi se to treba pro kalkulator no ted jsem popsal pravidla a zacnem kodovat..

kazde pravidlo muze mit akci..asi jako v Makefilu kde se neco provede (treba vygeneruje kod v compileru nebo vypocte v calculatoru) to jsou Sematic actions..vysledna sematic value se uklada do $$ parametry jsou $1...$n priklad pro normalni +

expr: expr `+` expr { $$=$1+$3 }
;
a skvrna od tresni je pryc! uz scitame... no a ted priklad:
 bizoni program je rozdelenej na:
 %{
  Normalni ceckovsky deklarace
 %}
  Bisonsky deklarace-tady si nedefinujete tokeny-NUM atd..
 %%
  Pravidla(rules)
 %%
 sem se dava jako u flexe dalsi ceckarskej kod-treba main
 %%
 v dokumentaci jsem nasel kalkulacku na polsou notaci tak se budu drzet
 jejich 
 kodu:
 %{
 #define YYSTYPE double - do ceho se maji ukladat cisla-typ pro sematic
 values
 #include  - no coment
 %% - zde zacinaji definice bisona
 
 %token NUM - tak tady si defijeme token pro cisla-jinej nepotrebujeme
 
 %% - tady jsou vlastni jazykovy pravidla
 input:
    | inout line
 ;
 
 line:  '\n'
   | exp '\n' {printf("vysledek:%g",$1); -kdyz se narazi na novou radku vysat
 ;
 
 exp: NUM {$$=$1;} ?*co delat z cislama*/
   | exp exp '+' {$$=$1+$1;} /*takhle se daji udelat vsechna znaminka
   | exp 'n { $$ =-$1; } /*unarni minus je tedy znak n*/
 ;
 
 .....konec prikladu
| znamena or-tedy nejaka jina cesta jak definovat grouping takze zirejte
expresion je cislo-prvni definice
expresion je expresion expresion cislo-druha definice-to je rpn format>BR> kdyz chceme secist dve cisla napisem 1 2 + a visledek je 3
no samozdrejea kdyz dame 1 2 + 3 + napred se vyhodnoti prvni expresion a pak druha. To znamena ze mame funkcni kalkulacku(samozdrejme po dodani -/*) takze tu mame groupingy:exp line a input.

line je jedna radka a sklada se z expresion a \n
input je bud nic(nic za :) nebo input a radka-takze vlastne libovolny pocet radek..pakne ne?

no a ted musime udelat parsera..sel by lehce ve flexu ale v manualu je rovnou a nechci tu tvorit neco novyho co kdyby tam byla buga samozrejme ze pravidla z | se daji napsat i oddelene(poznamka) takze lexikal-yylex

#include 
yylex()
{ int c;
  /*tato funkce se zavola vzdycky kdyz prekladac gramatiky je zvedavej na 
dalsi token*/
  /*preskocit mezery*/
  while(((c=getchar()) == ' ' || c == '\t')
   ;
  /*ted cisla*/
  if(c=='.' || isdigit(c)) {
   ungetc(c,stdin);
   scanf("%lf",&yyval);/*pozor tam se ulozila sematicka hodnota cisla*/
   return NUM;
  }
  /*konec fajlu*/
  if(c==EOF) return 0;
  /*no ted jednoznakej token-nic jinyho to uz bejt nemuze*/
  return c;
}
jednoduchy ne? a uz to pocita! jenom to sputit
main()
{
  yyparse();
}
a vybombit chybicky
yyerror(s)
  char *s;
{ printf("sorry vole error:%s"n);
}
ted to zkompilujsem:
bison .y
a mame fajlik .tab.c
gcc .tab.c -lm
a jedeme..novy maple na svete

a ted to nejlepsi:prestala se vam libit rpn? tak udelame normalni! do bison deklaraci-tam kde se delaji tokeny pripiseme smer vyhodnocovani:

%left '+' '-' 
%left je jako %token ale asociativni doleva
ale treba ^(umocnovani jde doprava)
%right `^` 
do definice expresionu napiseme znaminka pekne podle prirority:
 | exp '+' exp {$$ = $1 + $3;}
to uz je normalni pocitani ne? no a pridelame bloky v zavorkach
 | '(' exp ')' {$$=$2;}
trosku podivnou definici unarniho minusu-nebudu pitvat
 | '-' exp %prec {$$ = -$1;}
a je tu plne funkcni kalkulacka ze vsim...samozdrejme pridat funkce by bylo hracku..jenom by se asi yylex muselo udelat ve flexovi Zdrojaky se vejdou na stranku a jsou plne funkci,odolny vuci chybam,prehledne dobre navrzene..proste bison :)

u takovyho konfiguracniho fajlu je to samozdrejme mnohem jednodusi.. proste ve lexovy casti slova rozdelame na konstanty a tady naplnime nejaky ty promeny cislama...proste hracka kouknete se treba do dosemu

vic infa je samozdrejme v prikazu info v linuxu


Tento soubor je soucasti rozsahle sbirky skolicek na http://www.ucw.cz/~hubicka/skolicky

Take si muzete prohlidnout jeji puvodni textovou podobu

Nebo mi mailnout na hubicka@aru.cas.cz

Copyright (C) Jan Hubicka 1995