\chapter{Generátor syntaktických analyzátorů Bison}
Jedná se o program spustitlený v prostředí Linuxu a je distribuován jako 
svobodný sw pod licencí GNU GPL. Vstupem programu Bison je bezkontextová 
gramatika zapsaná v BNF formě, generátor na základě této gramatiky vygeneruje 
zdrojový kód parseru zpracovávajícího uvedenou gramatiku. 

Gramatika se skládá 
z terminálních a neterminálních symbolů, terminální symboly generuje lexikální 
analyzátor. Gramatika je popsána jednotlivými pravidly kdy na levé straně je 
vždy neterminální symbol a na pravé straně je rozklad na jednodušší konstrukce 
složené opět z neterminálních a terminálních symbolů. Každý terminální i neterminální 
symbol může mít přiřazenu sémantickou hodnotu. Každé pravidlo může mít přiřazenu 
sémantickou akci která je zavolána poté co parser rozpozná ve vstupním souboru dané 
pravidlo. Každý lex. element a pravidlo gramatiky má kromě sémantické hodnoty 
také přiřazenu informaci o umístění v souboru (Location). Informace o umístění obsahuje 
jméno souboru, řádek a sloupec na kterém symbol začíná a končí. Tyto Informace 
jsou automaticky vypočítávány při zpracování vstupního souboru parserem 
vygeneroavným Bisonem. Parser pracuje 
na principu zásobníkového automatu. Kompletní popis programu Bison je k dispozici 
viz. \cite{BisonManual}

\section{Formát vstupního souboru analyzátoru}
Vstupní soubor obsahující gramatiku jazyka má následující strukturu:
\begin{verbatim}
%{
  Úvod
%}
  deklarace
%%
  pravidla_gramatiky
%%
  Závěr
\end{verbatim}

Úvod může obsahovat deklarace typů a proměnných používaných v sémantických 
akcích, můžou zde být příkazy preprocesoru. Musí zde být deklarovaný lexikální 
analyzátor {\bf yylex} a funkce na hlášení chyb {\bf yyerror}.

Deklarační část obsahuje seznam jmen neterminálních a terminálních symbolů a 
můžou zde být určeny sémantické typy jednotlivých symbolů a definována 
priorita operátorů.

V části gramatických pravidel jsou popsána jednotlivá pravidla která 
říkají jakým způsobem zkonstruovat jednotlivé neterminální symboly z jejich 
součástí.

Závěr může obsahovat libovolný kod jazyce C(C++) typicky definice 
funkcí deklarovaných v prologu.

\section{Syntaxe pravidel gramatiky}
\begin{verbatim}
  vysledek: casti_pravidla
            ;
\end{verbatim}

Výsledek je neterminální symbol který popisuje dané pravidlo a 
{\bf casti\_pravidla}
 jsou různé terminální a neterminální symboly z nichž se skládá dané pravidlo.
Mezi každým symbolem může být zavolána sémantická akce, je ohraničena složenými 
závorkami a je popsána v jazyce C(C++). Různá pravidla která mají stejný výsledek 
mohou být vypsána samostatně nebo oddělena znakem "|".

{\bf Příklad:}
\begin{verbatim}
vyraz : vyraz '+' vyraz { cout << "toto je semanticka akce";}
  | vyraz '-' vyraz { cout << "odecteni dvou vyrazu"; }
  | faktor
  ;
\end{verbatim}

\section{Datové typy sémantických hodnot symbolů}
Pokud mají všechny symboly pouze jeden typ sémantických hodnot definuje se 
tento typ pomoci makra YYSTYPE : 
\begin{verbatim} 
  #define YYSTYPE double
\end{verbatim}

Pokud je typů více lze je definovat pomocí kolekce všech typů příkazem \%union 
nebo přiřadit zvlášt každému symbolu jeho sémantický typ. To se provede v části 
prologu u neterminálního symbolu deklarací:

\begin{verbatim}
  \%token <jmeno_typu> jmeno_neterminalniho_symbolu
\end{verbatim}

U terminálního symbolu:
\begin{verbatim}
  \%type <jmeno_typu> jmeno_terminalniho_symbolu
\end{verbatim}

\section{Přístup k sémantickým hodnotám symbolů}
V sémantické akci každého pravidla je možné přistupovat k sémantickým hodnotám 
symbolů z nichž je pravidlo sestaveno, přistupuje se k ní konstrukcí \$n 
která vrací hodnotu n-tého symbolu. K sémantické hodnotě právě konstruovaného 
pravidla se přistupuje pomocí konstrukce \$\$.

{\bf Příklad:}
\begin{verbatim}
vyraz :
    ...
    | vyraz '+' vyraz { $$ = $1 + $2; }
    ;
\end{verbatim}

\section{Rozhraní parseru}
Bison umožnuje vygenerovat zdrojový kód pouze v jazyce C nebo 
vytvořit třídu parseru v jazyce C++.

\subsection{Rozhraní v jazyce C}
Je vygenerována funkce \verb|yyparse| která po zavolání spustí syntaktickou analýzu.
Tato funkce čte neterminální symboly které dostává od lexikálního analyzátoru 
a spouští sémantické akce. Lze definovat přidání parametrů funkci které 
potom mohou být využity v sémantických akcích:
\begin{verbatim}
	%parse-param {argument-declaration}
\end{verbatim}
Lexikální analyzátor je volán funkcí \verb|yylex| která nemá žádný parametr 
a vrací identifikátor neterminálního symbolu. Sémantické hodnoty jsou 
předávány pomocí globální proměnné \verb|yylval|. Informace o umístění symbolu 
jsou také předávány pomocí globální proměnné \verb|yyloc|.
\subsection{Rozhraní v jazyce C++}
Pokud chceme vygenerovat parser v jazyce C++ je třeba mu zvolit kostru 
podle které jej vygeneruje, to se provede deklarací {\bf \%skeleton "lalr1.cc"}. 
Po spuštění Bizon vytvoří následující soubory:
\begin{itemize}
\item Position.hh , location.hh : Obsahují třídy pro určení pozice symbolů
\item Stach.hh : Přídavná třída Stach využívaná parterem
\item file.hh , file.hh : Deklarace a implementace třídy realizující parser zpracovávající zadanou gramatiku
\end{itemize}

Třída realizující parser obsahuje:
\begin{itemize}
\item Konstruktor implicitně bez parametru, parametry lze přidat deklarací: 
\item Metoda parse: spustí syntaktickou analýzu
\item Metoda set\_debug\_level( debug\_level 1): umožňuje nastavit výpis hlášení o zpracování gramatiky
\item Metoda error (const location type\& l, const std::string\& m): Hlášení 
syntaktických chyb, volá jí parser pokud narazí na chybu. Definice 
musí být dopsána uživatelem.
\end{itemize}
Rozhraní lexikálního analyzátoru:
Parser ovládá lexikální analyzátor voláním funkce \verb|yylex|. Funkce \verb|yylex| 
musí mít následující rozhraní:
\begin{verbatim}
int yylex (semantic_value_type& yylval, location_type& yyloc);
\end{verbatim}

\section{Spuštění Bisonu}
Vygenerování zdrojového kódu se provede spuštěním programu Bison:
\begin{verbatim}
bison -r all -d jmeno_souboru_s_gramatikou
\end{verbatim}
Výstupem jsou zdrojové kódy parseru popř. soubory s přídavnými třídami a také 
soubor s koncovkou .output ve kterém je výpis případných  konfliktů  a popis celého 
zásobníkového automatu s kterým parser pracuje.













