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