add dvisvgm4ht module to compile correctly shemes in html docs
[T7] / docs / main.tex
1 \documentclass{article}
2
3 \ifdefined\HCode
4   \def\pgfsysdriver{dvisvgm4ht/pgfsys-dvisvgm4ht.def}
5  \fi
6
7 \usepackage[square,numbers]{natbib}
8 \bibliographystyle{unsrtnat}
9
10 \usepackage{hyperref}
11
12 \usepackage{tikz}
13 \usetikzlibrary{chains,matrix,graphs,scopes,decorations.shapes,arrows,shapes}
14 \tikzset{
15   nonterminal/.style={
16     % The shape:
17     rectangle,
18     % The size:
19     minimum size=6mm,
20     % The border:
21     very thick,
22     draw=red!50!black!50,
23     % The filling:
24     top color=white,
25     bottom color=red!50!black!20,
26   },
27   terminal/.style={
28     % The shape:
29     rounded rectangle,
30     minimum size=6mm,
31     % The rest
32     very thick,draw=black!50,
33     top color=white,bottom color=black!20,
34     font=\ttfamily},
35   instruction/.style={
36     % The shape:
37     rectangle,
38     minimum size=6mm,
39     % The rest
40     draw=white,
41     top color=white,bottom color=white},
42   skip loop/.style={to path={-- ++(0,#1) -| (\tikztotarget)}}
43 }
44 {
45   \tikzset{terminal/.append style={text height=1.5ex,text depth=.25ex}}
46   \tikzset{nonterminal/.append style={text height=1.5ex,text depth=.25ex}}
47   \tikzset{instruction/.append style={text height=1.5ex,text depth=.25ex}}
48 }
49
50 \listfiles
51
52 \title{T7 compiler manual}
53 \author{Nicolas Mauger}
54 \date{\today}
55
56 \begin{document}
57     \maketitle
58
59     \newpage
60
61     \begin{abstract}
62             T7 is a project started in August 2018 originally written by Nicolas Mauger.
63             It's a step-by-step approach to compiler development mostly based on the books
64             \textit{Compiler Design In C \cite{CompilerDesignInC}} and \textit{Systematic Software
65             Development Using VDM \cite{VDMdevelopment}}. \\
66             All documents in this project are subject to the CeCILL license. You should have receive a
67             copy of the CeCILL free software license agreement version 2.1 along with this program and
68             documents; if not, please visit
69             \href{http://www.cecill.info/licences/Licence_CeCILL_V2.1-en.txt}{www.cecill.info} or send
70             an email at \href{mailto:nicolas@mauger.cafe}{nicolas@mauger.cafe}.
71     \end{abstract}
72
73     \tableofcontents
74
75         \section{Basic concepts and naive implementation}
76         Our very first compiler is split in three parts : a lexical analyzer (see \texttt{lex.*}
77         files), a parser (see \texttt{parse.*} files) and a code generator.
78
79             \subsection{Short lexical analyzer}
80             The lexical analyzer will simply \textit{tokenize} all the sources and translates all
81             the lexemes\footnote{A lexeme is a sequence of characters in the source program that
82             matches the pattern for a token and is identified by the lexical analyzer as an instance
83             of that token.} into a simple computable representation. Their representations will be
84             easier to parse.
85
86             \subsection{Our very first parser}
87             We start by parsing simple arithmetical operation. First we decompose statements in four
88             simple syntax who can be found in any basic programmation langague who accept
89             arethmetical operation. Moreover, expressions, terms and actors can be used recursively:
90             expression contains terms which contain factors which contain expressions...etc. At this
91             step we can already catch error if the operation does not respect theirs following
92             syntax schemes.
93
94             \begin{figure}[!ht] % Statment syntax
95             \label{fig:statmentSyntax}
96             \centering
97 \begin{tikzpicture}[point/.style={coordinate},>=stealth',thick,draw=black!50,
98                     tip/.style={->,shorten >=0.007pt},every join/.style={rounded corners},
99                     hv path/.style={to path={-| (\tikztotarget)}},
100                     vh path/.style={to path={|- (\tikztotarget)}},
101                     text height=1.5ex,text depth=.25ex]
102   \matrix[ampersand replacement=\&,column sep=4mm] {
103     \node (statment) [instruction] {\textbf{statement}};                    \&
104     \node (p1)  [point]  {}; \&  \node (p1a)   [point]       {};           \&
105     \node (p2)  [point]  {}; \&  \node (expr1) [nonterminal] {expression}; \&
106     \node (p3)  [point]  {}; \&  \node (dot)   [terminal]    {;};          \&
107     \node (p4)  [point]  {}; \&  \node (p4a)   [point]       {};           \&
108     \node (p5)  [point]  {}; \&  \node (p5a)   [point]       {};           \\
109   };
110
111   { [start chain]
112     \chainin (statment)[];
113     \chainin (p1);
114     \chainin (p1a)    [join,join=with p4a by {skip loop=-11mm,tip}];
115     \chainin (p2)     [join];
116     \chainin (expr1)  [join=by tip];
117     \chainin (p3)     [join];
118     \chainin (dot)    [join=by tip];
119     \chainin (p4)     [join];
120     \chainin (p4a)    [join];
121     \chainin (p5)     [join];
122     \chainin (p5a)    [join=by tip];
123   }
124 \end{tikzpicture}
125             \end{figure}
126
127             \begin{figure}[!ht] % Expression syntax
128             \label{fig:expressionSyntax}
129             \centering
130 \begin{tikzpicture}[point/.style={coordinate},>=stealth',thick,draw=black!50,
131                     tip/.style={->,shorten >=0.007pt},every join/.style={rounded corners},
132                     hv path/.style={to path={-| (\tikztotarget)}},
133                     vh path/.style={to path={|- (\tikztotarget)}},
134                     text height=1.5ex,text depth=.25ex]
135   \matrix[ampersand replacement=\&,column sep=4mm] {
136     \node (expression) [instruction] {\textbf{expression}};         \&
137     \node (p1)  [point]  {}; \&  \node (p1a)  [point]       {};     \&
138     \node (p2)  [point]  {}; \&  \node (term1)[nonterminal] {term}; \&
139     \node (p3)  [point]  {}; \&  \node (plus) [terminal]    {$+$};  \&
140     \node (p4)  [point]  {}; \&  \node (term2)[nonterminal] {term}; \&
141     \node (p5)  [point]  {}; \&  \node (p5a)  [point]       {};     \\
142   };
143
144   { [start chain]
145     \chainin (expression)[];
146     \chainin (p1);
147     \chainin (p1a)    [join];
148     \chainin (p2)     [join];
149     \chainin (term1)  [join=by tip];
150     \chainin (p3)     [join,join=with p5 by {skip loop=-11mm,tip}];
151     \chainin (plus)   [join=by tip];
152     \chainin (p4)     [join];
153     \chainin (term2)  [join=by tip];
154     \chainin (p5)     [join];
155     \chainin (p5a)    [join=by tip];
156   }
157 \end{tikzpicture}
158             \end{figure}
159             \begin{figure}[!ht] % Term syntax
160             \label{fig:TermSyntax}
161             \centering
162 \begin{tikzpicture}[point/.style={coordinate},>=stealth',thick,draw=black!50,
163                     tip/.style={->,shorten >=0.007pt},every join/.style={rounded corners},
164                     hv path/.style={to path={-| (\tikztotarget)}},
165                     vh path/.style={to path={|- (\tikztotarget)}},
166                     text height=1.5ex,text depth=.25ex]
167   \matrix[ampersand replacement=\&,column sep=4mm] {
168     \node (expression) [instruction] {\textbf{term}};                \&
169     \node (p1)  [point]  {}; \&  \node (p1a)  [point]       {};           \&
170     \node (p2)  [point]  {}; \&  \node (factor1)[nonterminal] {factor}; \&
171     \node (p3)  [point]  {}; \&  \node (times) [terminal]    {$*$};          \&
172     \node (p4)  [point]  {}; \&  \node (factor2)[nonterminal] {factor}; \&
173     \node (p5)  [point]  {}; \&  \node (p5a)  [point]       {};           \&
174     \node (p6)  [point]  {}; \&  \node (p6a)  [point]       {};           \\
175   };
176
177   { [start chain]
178     \chainin (expression)[];
179     \chainin (p1);
180     \chainin (p1a)     [join];
181     \chainin (p2)      [join];
182     \chainin (factor1) [join=by tip];
183     \chainin (p3)      [join,join=with p5a by {skip loop=-11mm,tip}];
184     \chainin (times)   [join=by tip];
185     \chainin (p4)      [join];
186     \chainin (factor2) [join=by tip];
187     \chainin (p5)      [join];
188     \chainin (p5a)     [join];
189     \chainin (p6)      [join=by tip];
190   }
191 \end{tikzpicture}
192             \end{figure}
193             \begin{figure}[!ht] % Factor syntax
194             \label{fig:FactorSyntax}
195             \centering
196 \begin{tikzpicture}[point/.style={coordinate},>=stealth',thick,draw=black!50,
197                     tip/.style={->,shorten >=0.01pt},every join/.style={rounded corners},
198                     hv path/.style={to path={-| (\tikztotarget)}},
199                     vh path/.style={to path={|- (\tikztotarget)}},
200                     text height=1.5ex,text depth=.25ex]
201
202   \matrix[ampersand replacement=\&,column sep=4mm] {
203     % First row:
204     \node (factor) [instruction] {\textbf{factor}};                  \&
205     \node (p1)  [point]  {}; \&  \node (p1a)    [point]    {};       \&
206     \node (p2)  [point]  {}; \&  \node (number) [terminal] {number}; \&
207     \node (p3)  [point]  {}; \&  \node (p3a)    [point]    {};       \\
208     % Empty space
209     \& \& \&  \&                                                     \\
210     % Second row:
211     \& \& \& \node (LP)  [terminal]{$($}; \&
212     \node (ex) [nonterminal]{expression}; \& \node (RP) [terminal]{$)$}; \\
213   };
214
215   { [start chain]
216     \chainin (factor)[];
217     \chainin (p1)      ;
218     \chainin (p1a)   [join];
219     \chainin (p2)    [join];
220     { [start branch=ex]
221         \chainin (LP) [join=by {vh path,tip}];
222         \chainin (ex) [join=by tip];
223         \chainin (RP) [join=by tip];
224         \chainin (p3) [join=by {hv path,tip}];
225     }
226     \chainin (number)[join=by tip];
227     \chainin (p3)    [join];
228     \chainin (p3a)   [join=by tip];
229   }
230
231 \end{tikzpicture}
232             \end{figure}
233
234             \subsection{The code generator}
235             The parse tree created in the previous step can be simply used by a different program to
236             generate code. But most of the modern compiler, the code generation is a part of parse
237             process. Indeed, the parse tree created can be used to create an intermediate language,
238             like a super-assembly, to perform specific tasks like optimisation, compression and
239             platform specific binary generation. This is this intermediate language method how will
240             be used in T7.
241
242 \bibliography{main}
243 \end{document}