From bbs@floyd.upol.czMon Jan 29 16:15:22 1996
Date: Wed, 6 Dec 1995 15:24:37 +0100
From: BBS Floyd <bbs@floyd.upol.cz>
To: hubicka@limax.paru.cas.cz
Subject: Skilicka #2-bison dodelana (fwd)

*** Forwarded file follows ***

Posted By: kotelnik (kotelnik) on 'Linux'
Title:     Skilicka #2-bison dodelana
Date:      Thu Nov 23 15:16:44 1995

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.

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

no a ted jak se delaji 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..
Je tu ale drobny problem..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 rulesy a zacnem kodovat..
kazda rulesa 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 <math.h> - 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
kdyz chceme secist dve cisla napisem 1 2 + a visledek je 3
no samozdrejma 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 rulesy z | se daji napsat i oddelene(poznamka)
takze lexikal-yylex
#include <ctype.h>
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 <jmeno>.y
a mame fajlik <jmeno>.tab.c
gcc <jmeno>.tab.c -lm
a jedeme..novy maple na svete

a ted to nejlepsi:prestala se vam jibit rpn? tak udelame normalni!
do bison deklaraci-tam kde se delaji tokeny pripiseme smer vyhodnocovani:
%left '+' '-' <dalsi znaminka>
%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

ps:priorite se tam rika precedence