% $Id: implementaceparser.tex,v 1.1 2007/01/18 22:20:29 jarda Exp $

\subsection{Úvod}

U zdrojových textů běžných programovacích jazyků je možné vytvářet syntaktické
analyzátory (parsery) na základě známé gramatiky. Já jsem ve své práci stál
před úkolem zpracovat soubory poměrně jednoduché struktury, ale nepříliš jasné
gramatiky. V zásadě jsem vyšel z toho, že se soubory skládají z jednoduchých
deklarací řádkového typu nebo mohou být na virtuální řádky převedeny tam, kde
jde o deklaraci např. výrazu na více fyzických řádcích a deklarace je ukončena
středníkem. Tento přístup výrazně usnadňuje následné zpracování.


\subsection{Rozhraní programu}

Program je spouštěn z příkazové řádky a výsledky vypisuje na standardní výstup. Syntaxe je
následující:

{\odstavec
./ParseInfo.py [-t \textit{formát}] \textit{seznam souborů}

Zadání formátu je nepovinné a aplikuje se na všechny soubory ze seznamu, pokud je zadáno.
Jinak jsou formáty rozpoznávány z přípony. Explicitní uvedení formátu je nutné pro zpracování
souborů s nestandardními příponami.

Příklady použití:
}

\begin{verbatim}
./ParseInfo.py s832.slif 5xp1.blif
./ParseInfo.py -t pla 5xp1.txt
\end{verbatim}

{\odstavec
Příklad výstupu:
}

\begin{verbatim}
** Benchmark file info parser **

Parsing file s832.slif

BUF count: 0
NOT count: 25
Outputs count: 19
OR count: 64
NAND count: 54
NOR count: 66
Gates count: 287
Inputs count: 19
DFF count: 0
AND count: 78
\end{verbatim}

\subsection{Volba lexikálního analyzátoru}

Vzhledem k tomu, že jsem zvolil programovací jazyk Python, musel jsem vycházet
z prostředků, které tento programovací jazyk má k dispozici. A různých prostředků
existuje celá řada, počínaje jednoduchými lexikálními analyzátory až po komplexní
systémy typu ANTLR. Nakonec jsem zvolil modul pro lexikální analýzu s názvem Plex.
Výhodou Plexu je jeho snadno srozumitelná, syntaxe, kterou v následujícím textu
ukáži na příkladu. Kód lexikálního analyzátoru vytvořeného pomocí nástroje Plex
není vygenerovaný, ale každá změna v definici syntaxe se okamžitě projeví, což
koresponduje s konceptem interpretovaných jazyků typu Python. Lexikální analyzátor
vytvořený pomocí Plexu rovněž vykazoval poměrně slušný výkon v porovnání s některými
jinými testovanými alternativami.

\subsection{Analýza souboru}

{\odstavec
Analýza probíhá pomocí instance třídy BenchmarkFileParser, která využívá
lexikální analyzátor vytvořený metodou createScanner(). Lexikální analyzátor
je instancí třídy LinesProducingScanner(), která generuje symboly pro jednotlivé
neprázdné řádky. Lexikální analyzátor si lze představit jako funkci A, jejíž parametry
jsou vstupní soubor F a lexikon L a výstupem je posloupnost řádků symbolů S:

S = A(F, L)
}

\subsection{Příklad definice lexikonu}

\begin{verbatim}
self.lexicon = Lexicon([
    (Str('#') + Rep(AnyBut('\n')), ScannerConstants.T_COMMENT,),
    (Str('.inputs'), ScannerConstants.T_INPUTS,),
    (Str('.outputs'), ScannerConstants.T_OUTPUTS,),
    (Str('.names'), ScannerConstants.T_NAMES,),
    ScannerConstants.R_NEWLINE,
    ScannerConstants.R_IGNORE_SPACES_AND_TABS,
    ScannerConstants.R_TOKEN,
])
\end{verbatim}



\clearpage
\subsection{Hierarchie tříd}

Pro bližší objasnění fungování parseru ukážu UML diagram základních použitých tříd:

\begin{figure}[h]
\includegraphics[width=150mm]{Python_classes}
\caption{Základní třídy analyzátoru}
\label{fig:parser}
\end{figure}

Pro každý formát je definována samostatná podtřída třídy BenchmarkFileParser. Tato podtřída
analyzuje řádky získané z instance třídy LinesProducingScanner, která vytváří řádky symbolů
na základě zadané instance třídy Lexicon().

\subsection{Využití dynamických vlastností jazyka Python pro flexibilní podporu formátů}

Program využívá možnosti dynamického sestavování názvů tříd a dynamického importu pomocí následujícího
kódu:

\begin{verbatim}
# get the format ID
benchmarkFormat = Constants.EXT_TO_BENCHMARK_FORMAT[lowerCaseName]

# get the internal format name
internalBenchmarkFormatName = Constants.INTERNAL_BENCHMARK_FORMAT_NAME[benchmarkFormat]

# construct module name from the prefix and internal format name
parserModuleName = Constants.BENCHMARK_FILE_PARSER_MODULE_PREFIX 
    + internalBenchmarkFormatName

# import the module
parserModule = __import__(parserModuleName)

# construct the class name
parserClassName = Constants.BENCHMARK_FILE_PARSER_CLASS_PREFIX 
    + internalBenchmarkFormatName

# get the parser class
parserClass = getattr(parserModule, parserClassName)
\end{verbatim}

Dynamismus získání potřebné třídy je zajištěn funkcemi \_\_import\_\_ a getattr. Tyto
metody umožňují dokonce přidávat moduly a atributy za běhu aplikace, což v tomto případě není
třeba. Výhodou zmíněného dynamismu je vynucení jednotného pojmenování modulů a tříd pro
parsery, což zajistí lepší čitelnost a udržovatelnost kódu. Pro přidání dalšího formátu je
třeba:


\begin{itemize}

\item
Vytvořit novou konstantu pro daný formát.

\item
Přidat interní název formátu.
    
\item
Vytvořit modul s názvem odpovídajícím stanovenému schématu a internímu názvu formátu,
který obsahuje třídu s názvem odpovídající stanovenému schématu a internímu názvu formátu.
        
\end{itemize}

Funkce, která se stará o vybrání správného parseru, se nemění.


\subsection{Vyřešení závislosti analyzátoru na interpreteru jazyka Python}

Interpretované jazyky přinášejí nutnost vyřešení problematiky distribuce na počítače,
kde interpreter jazyka není nainstalován. V případě jazyka Python existují dvě
řešení problému:

\begin{itemize}

\item Nainstalovat plnohodnotný interpreter.

\item Vytvořit distribuci programu se zabaleným interpreterem, pokud možno redukovaným tak,
aby zajišťoval pouze funkce našeho programu a nenesl s sebou redundantní data.
 
\end{itemize}

Zatímco první cestu lze, pokud je to z nějakého důvodu výhodné (např. distribuce Linuxu často
již obsahují interpreter Pythonu a dokonce jej používají pro základní činnosti nutné
k běhu či údržbě), pro distribuci ke koncovému uživateli, zejména na platformě MS Windows
je výhodnější vytvořit distribuci se zabaleným interpreterem. V následujícím textu
demonstruji konkrétní řešení.

\subsubsection{Vytvoření distribuce programu pomocí rozšíření py2exe}

py2exe je rozšíření standardního mechanismu pro tvoření distribučních balíčků a automatizovanou
instalaci s názvem Distutils. Po nainstalování py2exe je třeba vytvořit skript setup.py.
Jeho základní podoba pro náš program má následující podobu:

\begin{verbatim}
from distutils.core import setup
import py2exe

setup(console=['ParseInfo.py'])
\end{verbatim}

{\odstavec
Tento skript vytvoří distribuci na základě hlavního skriptu s názvem ParseInfo.py. Distribuce
se skládá ze spustitelného programu (ParseInfo.exe), interpreteru obsaženého v dynamické knihovně
(Python24.dll), modulů potřebných pro práci programu (Library.zip) a několika pomocných souborů.

Rozšíření py2exe využívá analýzu příkazů import. Dynamická stavba programu s využitím dynamických
importů tuto analýzu znesnadňuje a py2exe proto dynamické moduly vynechá. Řešením je jejich
explicitní uvedení ve skriptu setup.py:
}

\begin{verbatim}
from distutils.core import setup
import py2exe

setup(console=['ParseInfo.py'] options={'py2exe : { 'includes' : [
    'BenchmarkFileParser',
    'BenchmarkFileParser_BENCH',
    'BenchmarkFileParser_BLIF',
    'BenchmarkFileParser_KISS2',
    'BenchmarkFileParser_PLA',
    'BenchmarkFileParser_SLIF',
    'Constants',
    'LinesProducingScanner',
    'ScannerConstants',
]}})
\end{verbatim}

Po spuštění příkazu

\begin{verbatim}
python setup.py
\end{verbatim}

se vytvoří adresář dist obsahující všechny potřebné soubory. Tento způsob distribuce má dva nedostatky:

\begin{enumerate}
        
\item Nutnost hlídání přidávaných souborů, což snižuje výhody dynamické stavby programu.

\item Nekompaktnost takovéto distribuce - nutnost zabalit vzniklé soubory například do
    archivu typu zip.
    
\end{enumerate}

Automatické přidávání modulů do distribuce lze vyřešit několika způsoby. Řešení, které
zde předvedu, využívá toho, že ve skriptu setup.py lze používat běžné konstrukce jazyka Python
a pro funkci setup() připravit parametry dynamicky. Následující příklad řeší řeší jednoduše
dynamické přidávání modulů pro jednotlivé formáty. Jednotná stavba názvů modulů situaci
výrazně usnadňuje:

\begin{verbatim}
from distutils.core import setup
import py2exe
import glob

includes = [
    'BenchmarkFileParser',
    'Constants',
    'LinesProducingScanner',
    'ScannerConstants',
]

includes += [filename[:-3] for filename in glob.glob('BenchmarkFileParser_*.py')]

setup(console=['ParseInfo.py'] options={'py2exe : { 'includes' : includes}})
\end{verbatim}

V příkladu jsme s výhodou použili modul glob pro práci se seznamem souborů
vytvořeným pomocí vzoru a konstrukci 'list comprehension' a ořezání přípon souborů.

{\odstavec
Problém s kompaktností distribuce lze vyřešit použitím některého systému pro snadné
vytváření instačních programů pro platformu MS Windows, například systému Inno Setup.
Touto problematikou se zde zabývat nebudu, použití je triviální.
}

% vim:enc=iso8859-2:fenc=iso8859-2:
