1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
|
<!DOCTYPE html>
<!-- saved from url=(0058)https://norasandler.com/2018/04/10/Write-a-Compiler-8.html -->
<html lang="en"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>C Compiler, Part 8: Loops</title>
<meta name="description" content="This is the eighth post in a series. Read part 1 here.">
<link rel="stylesheet" href="./C Compiler, Part 8_ Loops_files/main.css">
<link rel="canonical" href="https://norasandler.com/2018/04/10/Write-a-Compiler-8.html">
<link rel="alternate" type="application/rss+xml" title="Nora Sandler" href="https://norasandler.com/feed.xml">
</head>
<body>
<header class="site-header" role="banner">
<div class="wrapper">
<a class="site-title" href="https://norasandler.com/">Nora Sandler</a>
<nav class="site-nav">
<input type="checkbox" id="nav-trigger" class="nav-trigger">
<label for="nav-trigger">
<span class="menu-icon">
<svg viewBox="0 0 18 15" width="18px" height="15px">
<path fill="#424242" d="M18,1.484c0,0.82-0.665,1.484-1.484,1.484H1.484C0.665,2.969,0,2.304,0,1.484l0,0C0,0.665,0.665,0,1.484,0 h15.031C17.335,0,18,0.665,18,1.484L18,1.484z"></path>
<path fill="#424242" d="M18,7.516C18,8.335,17.335,9,16.516,9H1.484C0.665,9,0,8.335,0,7.516l0,0c0-0.82,0.665-1.484,1.484-1.484 h15.031C17.335,6.031,18,6.696,18,7.516L18,7.516z"></path>
<path fill="#424242" d="M18,13.516C18,14.335,17.335,15,16.516,15H1.484C0.665,15,0,14.335,0,13.516l0,0 c0-0.82,0.665-1.484,1.484-1.484h15.031C17.335,12.031,18,12.696,18,13.516L18,13.516z"></path>
</svg>
</span>
</label>
<div class="trigger">
<a class="page-link" href="https://norasandler.com/about/">About</a>
<a class="page-link" href="https://norasandler.com/archive/">Archive</a>
<a class="page-link" href="https://github.com/nlsandler">Github</a>
<a href="https://norasandler.com/feed.xml"><img id="rss" height="20" width="20" src="./C Compiler, Part 8_ Loops_files/rss.png"></a>
</div>
</nav>
</div>
</header>
<main class="page-content" aria-label="Content">
<div class="wrapper">
<article class="post h-entry" itemscope="" itemtype="http://schema.org/BlogPosting">
<header class="post-header">
<h1 class="post-title p-name" itemprop="name headline">C Compiler, Part 8: Loops</h1>
<p class="post-meta">
<time class="dt-published" datetime="2018-04-10T19:00:00+00:00" itemprop="datePublished">Apr 10, 2018
</time></p>
</header>
<div class="post-content e-content" itemprop="articleBody">
<p><em>This is the eighth post in a series. Read part 1 <a href="https://norasandler.com/2017/11/29/Write-a-Compiler.html">here</a>.</em></p>
<p>In this post we’re going to add loops! Now we’ll finally be able to compile FizzBuzz…except we won’t, because we can’t call printf yet. Still, it’s progress!</p>
<p>If you’ve been following along, note that there was a mistake in <a href="https://norasandler.com/2018/03/14/Write-a-Compiler-7.html">the last post</a>. Make sure you read the “Deallocating Variables” section and update your compiler to pass the new stage 7 tests before you start on stage 8.</p>
<p>As usual, accompanying tests are <a href="https://github.com/nlsandler/write_a_c_compiler">here</a>.</p>
<h1 id="part-8-loops">Part 8: Loops</h1>
<p>In this post we’re implementing what the <a href="http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf">C11 standard</a> calls iteration statements; if you want to refer to the standard itself, they’re in section 6.8.5. There are a few different iteration statements:</p>
<h3 id="for-loops"><code class="language-plaintext highlighter-rouge">for</code> loops</h3>
<p>First, some terminology. I’m going to call the three parts of a <code class="language-plaintext highlighter-rouge">for</code> loop header the <em>initial clause</em>, <em>controlling expression</em>, and <em>post-expression</em>, as in:</p>
<div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="c1">// initial clause</span>
<span class="n">i</span> <span class="o"><</span> <span class="mi">10</span><span class="p">;</span> <span class="c1">// controlling expression</span>
<span class="n">i</span> <span class="o">=</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span> <span class="c1">// post-expression</span>
<span class="p">)</span> <span class="p">{</span>
<span class="c1">// do something</span>
<span class="p">}</span>
</code></pre></div></div>
<p><code class="language-plaintext highlighter-rouge">for</code> loops come in two flavors: one where the initial statement is a variable declaration, and one where it’s just an expression.</p>
<p>Flavor #1:</p>
<div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="mi">10</span><span class="p">;</span> <span class="n">i</span> <span class="o">=</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
<span class="c1">// do something</span>
<span class="p">}</span>
</code></pre></div></div>
<p>Flavor #2:</p>
<div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="kt">int</span> <span class="n">i</span><span class="p">;</span>
<span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="mi">10</span><span class="p">;</span> <span class="n">i</span> <span class="o">=</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
<span class="c1">//do something</span>
<span class="p">}</span>
</code></pre></div></div>
<p>One interesting thing about <code class="language-plaintext highlighter-rouge">for</code> loops is that any of the expressions in the loop header can be empty:</p>
<div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">for</span> <span class="p">(;;)</span> <span class="p">{</span>
<span class="c1">//do something</span>
<span class="p">}</span>
</code></pre></div></div>
<p>But if the controlling expression is empty, the compiler needs to replace it with a constant nonzero expression<sup id="anchor1"><a href="https://norasandler.com/2018/04/10/Write-a-Compiler-8.html#fn1">1</a></sup>.
So the example above is equivalent to:</p>
<div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">for</span> <span class="p">(;</span><span class="mi">1</span><span class="p">;)</span> <span class="p">{</span>
<span class="c1">//do something</span>
<span class="p">}</span>
</code></pre></div></div>
<h3 id="while-and-do-loops"><code class="language-plaintext highlighter-rouge">while</code> and <code class="language-plaintext highlighter-rouge">do</code> Loops</h3>
<p>There’s not a whole lot to say about these.</p>
<div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">while</span> <span class="p">(</span><span class="n">i</span> <span class="o"><</span> <span class="mi">10</span><span class="p">)</span> <span class="p">{</span>
<span class="n">i</span> <span class="o">=</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div></div>
<div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">do</span> <span class="p">{</span>
<span class="n">i</span> <span class="o">=</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
<span class="p">}</span> <span class="k">while</span> <span class="p">(</span><span class="n">i</span> <span class="o"><</span> <span class="mi">10</span><span class="p">);</span> <span class="c1">// <- the semicolon is required!</span>
</code></pre></div></div>
<h3 id="break-and-continue"><code class="language-plaintext highlighter-rouge">break</code> and <code class="language-plaintext highlighter-rouge">continue</code></h3>
<p><code class="language-plaintext highlighter-rouge">break</code> and <code class="language-plaintext highlighter-rouge">continue</code> aren’t loops, but they always appear inside loops, so it makes sense to add them now<sup id="anchor2"><a href="https://norasandler.com/2018/04/10/Write-a-Compiler-8.html#fn2">2</a></sup>. The C11 standard calls them “jump statements” and defines them in section 6.8.6.</p>
<p>A <code class="language-plaintext highlighter-rouge">break</code> statement inside a loop causes execution to jump to the end of the loop:</p>
<div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">while</span> <span class="p">(</span><span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
<span class="k">break</span><span class="p">;</span> <span class="c1">// go to end of loop</span>
<span class="p">}</span>
<span class="c1">// break statement will go here</span>
</code></pre></div></div>
<p>A <code class="language-plaintext highlighter-rouge">continue</code> statement causes execution to jump to the end of the loop body – immediately before the post expression in a for loop.</p>
<div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="mi">10</span><span class="p">;</span> <span class="n">i</span> <span class="o">=</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
<span class="k">if</span> <span class="p">(</span><span class="n">i</span> <span class="o">%</span> <span class="mi">2</span><span class="p">)</span>
<span class="k">continue</span><span class="p">;</span>
<span class="c1">// do something</span>
<span class="c1">//continue statement will jump here</span>
<span class="p">}</span>
</code></pre></div></div>
<p>In the example above, the loop will execute ten times, but only “do something” for odd values of i.</p>
<h3 id="null-statements">Null statements</h3>
<p>Sort of like you can have null expressions in a <code class="language-plaintext highlighter-rouge">for</code> loop, you can also have null statements<sup id="anchor3"><a href="https://norasandler.com/2018/04/10/Write-a-Compiler-8.html#fn3">3</a></sup>:</p>
<div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="kt">int</span> <span class="n">a</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">;</span> <span class="c1">// does nothing</span>
<span class="k">return</span> <span class="n">a</span><span class="p">;</span>
</code></pre></div></div>
<p>Null statements don’t really have anything to do with loops, but they share a common feature with the expressions in a for loop: they’re both defined in terms of optional expressions in the standard. Since we need to support optional expressions in for loops, it’s pretty easy to add support for null expressions too.</p>
<p>As usual, we’ll update the lexing, parsing, and code generation passes, in order.</p>
<h2 id="lexing">Lexing</h2>
<p>We’re adding five (!) keywords in this post: <code class="language-plaintext highlighter-rouge">for</code>, <code class="language-plaintext highlighter-rouge">do</code>, <code class="language-plaintext highlighter-rouge">while</code>, <code class="language-plaintext highlighter-rouge">break</code>, and <code class="language-plaintext highlighter-rouge">continue</code>.
Here’s all our tokens so far:</p>
<ul>
<li><code class="language-plaintext highlighter-rouge">{</code></li>
<li><code class="language-plaintext highlighter-rouge">}</code></li>
<li><code class="language-plaintext highlighter-rouge">(</code></li>
<li><code class="language-plaintext highlighter-rouge">)</code></li>
<li><code class="language-plaintext highlighter-rouge">;</code></li>
<li><code class="language-plaintext highlighter-rouge">int</code></li>
<li><code class="language-plaintext highlighter-rouge">return</code></li>
<li>Identifier <code class="language-plaintext highlighter-rouge">[a-zA-Z]\w*</code></li>
<li>Integer literal <code class="language-plaintext highlighter-rouge">[0-9]+</code></li>
<li><code class="language-plaintext highlighter-rouge">-</code></li>
<li><code class="language-plaintext highlighter-rouge">~</code></li>
<li><code class="language-plaintext highlighter-rouge">!</code></li>
<li><code class="language-plaintext highlighter-rouge">+</code></li>
<li><code class="language-plaintext highlighter-rouge">*</code></li>
<li><code class="language-plaintext highlighter-rouge">/</code></li>
<li><code class="language-plaintext highlighter-rouge">&&</code></li>
<li><code class="language-plaintext highlighter-rouge">||</code></li>
<li><code class="language-plaintext highlighter-rouge">==</code></li>
<li><code class="language-plaintext highlighter-rouge">!=</code></li>
<li><code class="language-plaintext highlighter-rouge"><</code></li>
<li><code class="language-plaintext highlighter-rouge"><=</code></li>
<li><code class="language-plaintext highlighter-rouge">></code></li>
<li><code class="language-plaintext highlighter-rouge">>=</code></li>
<li><code class="language-plaintext highlighter-rouge">=</code></li>
<li><code class="language-plaintext highlighter-rouge">if</code></li>
<li><code class="language-plaintext highlighter-rouge">else</code></li>
<li><code class="language-plaintext highlighter-rouge">:</code></li>
<li><code class="language-plaintext highlighter-rouge">?</code></li>
<li><strong><code class="language-plaintext highlighter-rouge">for</code></strong></li>
<li><strong><code class="language-plaintext highlighter-rouge">while</code></strong></li>
<li><strong><code class="language-plaintext highlighter-rouge">do</code></strong></li>
<li><strong><code class="language-plaintext highlighter-rouge">break</code></strong></li>
<li><strong><code class="language-plaintext highlighter-rouge">continue</code></strong></li>
</ul>
<h4 id="-task">☑ Task:</h4>
<p>You know the drill here.</p>
<h2 id="parsing">Parsing</h2>
<p>We’re adding six kinds of statements: <code class="language-plaintext highlighter-rouge">do</code> loops, <code class="language-plaintext highlighter-rouge">while</code> loops, the two different kinds of <code class="language-plaintext highlighter-rouge">for</code> loop, <code class="language-plaintext highlighter-rouge">break</code> and <code class="language-plaintext highlighter-rouge">continue</code>.
We’re also changing the <code class="language-plaintext highlighter-rouge">Exp</code> statement; its argument is now optional, so we can use it to represent null statements.
Now we can construct a null statement in the AST like this:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>null_exp = Exp(None)
</code></pre></div></div>
<p>The initial expression and post-expression in a <code class="language-plaintext highlighter-rouge">for</code> loop are also optional.</p>
<p>Here’s the updated definition of statements in the AST, with new and changed parts bolded:</p>
<pre>statement = Return(exp)
<b> | Exp(exp option)</b>
| Conditional(exp, statement, statement option) // exp is controlling condition
// first statement is 'if' block
// second statement is optional 'else' block
| Compound(block_item list)
<b> | For(exp option, exp, exp option, statement) // initial expression, condition, post-expression, body
| ForDecl(declaration, exp, exp option, statement) // initial declaration, condition, post-expression, body
| While(expression, statement) // condition, body
| Do(statement, expression) // body, condition
| Break
| Continue</b>
</pre>
<p>Note that our AST lets <code class="language-plaintext highlighter-rouge">break</code> and <code class="language-plaintext highlighter-rouge">continue</code> statements appear outside of loops, even though that’s illegal; we’ll catch that error during code generation, not parsing.</p>
<p>The trickiest part of the grammar here is dealing with optional expressions. I dealt with this by defining an <code class="language-plaintext highlighter-rouge"><exp-option></code> symbol:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code><exp-option> ::= <exp> | ""
</code></pre></div></div>
<p>Once we’ve added that, updating the grammar for statements is pretty easy:</p>
<pre><statement> ::= "return" <exp> ";"
<b> | <exp-option> ";"</b>
| "if" "(" <exp> ")" <statement> [ "else" <statement> ]
| "{" { <block-item> } "}
<b> | "for" "(" <exp-option> ";" <exp-option> ";" <exp-option> ")" <statement>
| "for" "(" <declaration> <exp-option> ";" <exp-option> ")" <statement>
| "while" "(" <exp> ")" <statement>
| "do" <statement> "while" "(" <exp> ")" ";"
| "break" ";"
| "continue" ";"</b>
</pre>
<p>If you’re wondering why there’s a semicolon after the initial <code class="language-plaintext highlighter-rouge"><exp-option></code> in the first <code class="language-plaintext highlighter-rouge">for</code> rule, but not after the initial <code class="language-plaintext highlighter-rouge"><declaration></code> in the second one, it’s because the rule for <code class="language-plaintext highlighter-rouge"><declaration></code> also includes a semicolon.</p>
<p>Parsing <code class="language-plaintext highlighter-rouge"><exp-option></code> isn’t entirely straightforward, because the empty string is not actually a token. I dealt with this by looking ahead to see if the next token was a close paren (after a post-expression) or a semicolon (after a statement, post-expression or controlling condition). If it was, the expression was empty; if not, not. I think this approach violates some formalisms about context-free grammars and LL parsers: in order to parse an <code class="language-plaintext highlighter-rouge"><exp-option></code> symbol, you may have to look at a token that comes <em>after</em> that symbol.
This isn’t actually a problem, but if it bothers you, you can refactor the grammar to avoid it:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code><exp-option-semicolon> ::= <exp> ";" | ";"
<exp-option-close-paren> ::= <exp> ")" | ")"
<statement> ::= ...
| <exp-option-semicolon> // null statement
| "for" "(" <declaration> <exp-option-semicolon> <exp-option-close-paren> ")" <statement>
...
</code></pre></div></div>
<p>Note that there’s a discrepancy here between the grammar and the AST definition; the grammar allows controlling expressions in <code class="language-plaintext highlighter-rouge">for</code> loops to be empty, but the AST doesn’t. That’s because, as I mentioned earlier, an empty controlling expression needs to be replaced with a nonzero constant. So our approach to parsing controlling expressions in <code class="language-plaintext highlighter-rouge">for</code> loops will look something like this:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>match parse_optional_exp(controlling_expression) with
| Some e -> e
| None -> Const(1) // construct a constant nonzero expression
</code></pre></div></div>
<p>You could do this during the code generation stage instead of the parsing stage, if you wanted.</p>
<h4 id="-task-1">☑ Task:</h4>
<p>Update parsing to succeed on all valid stage 1-8 examples, and fail on all invalid stage 8 examples whose names start with <code class="language-plaintext highlighter-rouge">syntax_err</code>.</p>
<h2 id="code-generation">Code Generation</h2>
<h3 id="null-statements-1">Null Statements</h3>
<p>Don’t emit any assembly for null statements. Easy!</p>
<h3 id="while-loops"><code class="language-plaintext highlighter-rouge">while</code> loops</h3>
<p>Given a <code class="language-plaintext highlighter-rouge">while</code> loop like this:</p>
<div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">while</span> <span class="p">(</span><span class="n">expression</span><span class="p">)</span>
<span class="n">statement</span>
</code></pre></div></div>
<p>we can describe its control flow like this:</p>
<ol>
<li>Evaluate <code class="language-plaintext highlighter-rouge">expression</code>.</li>
<li>If it’s false, jump to step 5.</li>
<li>Execute <code class="language-plaintext highlighter-rouge">statement</code>.</li>
<li>Jump to step 1.</li>
<li>Finish.</li>
</ol>
<p>I won’t show you the exact assembly you need to generate here; by now you know enough to figure it out yourself.
The main thing is labeling steps 1 and 5, so when we need a jump instruction we have somewhere to jump to.
It’s worth noting that the loop body is a new scope, and you need to reset your <code class="language-plaintext highlighter-rouge">current_scope</code> set accordingly.</p>
<h3 id="do-loops"><code class="language-plaintext highlighter-rouge">do</code> Loops</h3>
<p>These are basically the same as <code class="language-plaintext highlighter-rouge">while</code> loops; just evaluate the expression after the statement.</p>
<h3 id="for-loops-1"><code class="language-plaintext highlighter-rouge">for</code> loops</h3>
<p>Given a <code class="language-plaintext highlighter-rouge">for</code> loop like this:</p>
<div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">for</span> <span class="p">(</span><span class="n">init</span><span class="p">;</span> <span class="n">condition</span><span class="p">;</span> <span class="n">post</span><span class="o">-</span><span class="n">expression</span><span class="p">)</span>
<span class="n">statement</span>
</code></pre></div></div>
<p>we can break it down in the same way as <code class="language-plaintext highlighter-rouge">while</code> loops above:</p>
<ol>
<li>Evaluate <code class="language-plaintext highlighter-rouge">init</code>.</li>
<li>Evaluate <code class="language-plaintext highlighter-rouge">condition</code>.</li>
<li>If it’s false, jump to step 7.</li>
<li>Execute <code class="language-plaintext highlighter-rouge">statement</code>.</li>
<li>Execute <code class="language-plaintext highlighter-rouge">post-expression</code>.</li>
<li>Jump to step 2.</li>
<li>Finish.</li>
</ol>
<p>The init and post-expression might be empty, in which case we just don’t emit any assembly for steps 1 and 5. Note that a <code class="language-plaintext highlighter-rouge">for</code> loop, including the header, is a block with its own scope, and the <em>body</em> of the <code class="language-plaintext highlighter-rouge">for</code> loop is <em>also</em> a block. That means you can have code like this:</p>
<div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">100</span><span class="p">;</span> <span class="c1">// scope 1</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="mi">10</span><span class="p">;</span> <span class="n">i</span> <span class="o">=</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{</span> <span class="c1">// scope 2 - variable i shadows previous i</span>
<span class="kt">int</span> <span class="n">i</span><span class="p">;</span> <span class="c1">//scope 3 - this variable i shadows BOTH previous i's</span>
<span class="p">}</span>
</code></pre></div></div>
<p>The main gotcha here is that you need to pop the variable declared in <code class="language-plaintext highlighter-rouge">init</code> off the stack
when you exit the block, just like you needed to handle deallocating other variables in the last post.</p>
<h3 id="break-and-continue-1"><code class="language-plaintext highlighter-rouge">break</code> and <code class="language-plaintext highlighter-rouge">continue</code></h3>
<p>We can implement each of these with a single <code class="language-plaintext highlighter-rouge">jmp</code> instruction – the trick is just figuring out where to jump <em>to</em>. A break statement “terminates execution of the smallest enclosing <code class="language-plaintext highlighter-rouge">switch</code> or iteration statement,” so we want to jump to the point right after the loop<sup id="anchor4"><a href="https://norasandler.com/2018/04/10/Write-a-Compiler-8.html#fn4">4</a></sup>. We already have an “end of loop” label, which we jump to when the controlling condition is false; we just need to pass that label around along with the variable map, stack index and current scope.</p>
<p>We also need to pass <em>another</em> label for <code class="language-plaintext highlighter-rouge">continue</code> to refer to. <code class="language-plaintext highlighter-rouge">continue</code> “causes a jump to the loop-continuation portion of the smallest
enclosing iteration statement; that is, to the end of the loop body”<sup id="anchor5"><a href="https://norasandler.com/2018/04/10/Write-a-Compiler-8.html#fn5">5</a></sup> – that’s step 4 in the <code class="language-plaintext highlighter-rouge">while</code> loop or step 5 in the <code class="language-plaintext highlighter-rouge">for</code> loop above.</p>
<p>Unlike the stack index, variable map and so forth, the jump and continue labels can be null, if you’re not inside a loop. Hitting a <code class="language-plaintext highlighter-rouge">break</code> or <code class="language-plaintext highlighter-rouge">continue</code> statement when these labels are null should, of course, cause an error.</p>
<p>At this point, I was passing enough arguments around that I defined a <code class="language-plaintext highlighter-rouge">Context</code> type and wrapped it all up in that. You may want to do something similar, but you don’t have to.</p>
<h2 id="up-next">Up Next</h2>
<p>In the <a href="https://norasandler.com/2018/06/27/Write-a-Compiler-9.html">next post</a> we’re going to implement a pretty fundamental concept: <strong>function calls</strong>. I don’t know about you but I am VERY EXCITED for function calls. See you then!</p>
<p><em>If you have any questions, corrections, or other feedback, you can <a href="mailto:nora@norasandler.com">email me</a> or <a href="https://github.com/nlsandler/write_a_c_compiler/issues">open an issue</a>.</em></p>
<div class="footnote">
<p><sup id="fn1">1</sup>
See section 6.8.5.3 of the C11 standard.<a href="https://norasandler.com/2018/04/10/Write-a-Compiler-8.html#anchor1">↩</a></p>
</div>
<div class="footnote">
<p><sup id="fn2">2</sup>
<code class="language-plaintext highlighter-rouge">break</code> can also appear in <code class="language-plaintext highlighter-rouge">switch</code> statements, but we haven’t added those yet.<a href="https://norasandler.com/2018/04/10/Write-a-Compiler-8.html#anchor2">↩</a></p>
</div>
<div class="footnote">
<p><sup id="fn3">3</sup>
C11 standard, section 6.8.3. <a href="https://norasandler.com/2018/04/10/Write-a-Compiler-8.html#anchor3">↩</a></p>
</div>
<div class="footnote">
<p><sup id="fn4">4</sup>
C11 standard, section 6.8.6.3.<a href="https://norasandler.com/2018/04/10/Write-a-Compiler-8.html#anchor4">↩</a></p>
</div>
<div class="footnote">
<p><sup id="fn5">5</sup>
C11 standard, section 6.8.6.2.<a href="https://norasandler.com/2018/04/10/Write-a-Compiler-8.html#anchor5">↩</a></p>
</div>
</div><a class="u-url" href="https://norasandler.com/2018/04/10/Write-a-Compiler-8.html" hidden=""></a>
</article>
</div>
</main>
<footer class="site-footer">
<div class="wrapper">
<div class="footer-col-wrapper">
<div class="footer-col footer-col-1">
<div class="rc-scout" data-scout-rendered="true"><p class="rc-scout__text"><i class="rc-scout__logo"></i> Want to become a better programmer? <a class="rc-scout__link" href="https://www.recurse.com/scout/click?t=8f520efbc4be09fb83a71920f53a07b7">Join the Recurse Center!</a></p></div><script async="" defer="" src="./C Compiler, Part 8_ Loops_files/loader.js"></script>
</div>
</div>
<div class="footer-col-wrapper">
<div class="footer-col footer-col-1">
© 2023 Nora Sandler.
</div>
</div>
</div>
</footer>
<script async="" src="./C Compiler, Part 8_ Loops_files/scout-176be16681a03cbddd686f3cc96694d3aab338ea5cb65452f83d989309810528.js"></script><style class="rc-scout__style" type="text/css">.rc-scout {
display: block;
padding: 0;
border: 0;
margin: 0;
}
.rc-scout__text {
display: block;
padding: 0;
border: 0;
margin: 0;
height: 100%;
font-size: 100%;
}
.rc-scout__logo {
display: inline-block;
padding: 0;
border: 0;
margin: 0;
width: 0.85em;
height: 0.85em;
background: no-repeat center url('data:image/svg+xml;utf8,%3Csvg%20xmlns%3D%22http%3A%2F%2Fwww.w3.org%2F2000%2Fsvg%22%20viewBox%3D%220%200%2012%2015%22%3E%3Crect%20x%3D%220%22%20y%3D%220%22%20width%3D%2212%22%20height%3D%2210%22%20fill%3D%22%23000%22%3E%3C%2Frect%3E%3Crect%20x%3D%221%22%20y%3D%221%22%20width%3D%2210%22%20height%3D%228%22%20fill%3D%22%23fff%22%3E%3C%2Frect%3E%3Crect%20x%3D%222%22%20y%3D%222%22%20width%3D%228%22%20height%3D%226%22%20fill%3D%22%23000%22%3E%3C%2Frect%3E%3Crect%20x%3D%222%22%20y%3D%223%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%233dc06c%22%3E%3C%2Frect%3E%3Crect%20x%3D%224%22%20y%3D%223%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%233dc06c%22%3E%3C%2Frect%3E%3Crect%20x%3D%226%22%20y%3D%223%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%233dc06c%22%3E%3C%2Frect%3E%3Crect%20x%3D%223%22%20y%3D%225%22%20width%3D%222%22%20height%3D%221%22%20fill%3D%22%233dc06c%22%3E%3C%2Frect%3E%3Crect%20x%3D%226%22%20y%3D%225%22%20width%3D%222%22%20height%3D%221%22%20fill%3D%22%233dc06c%22%3E%3C%2Frect%3E%3Crect%20x%3D%224%22%20y%3D%229%22%20width%3D%224%22%20height%3D%223%22%20fill%3D%22%23000%22%3E%3C%2Frect%3E%3Crect%20x%3D%221%22%20y%3D%2211%22%20width%3D%2210%22%20height%3D%224%22%20fill%3D%22%23000%22%3E%3C%2Frect%3E%3Crect%20x%3D%220%22%20y%3D%2212%22%20width%3D%2212%22%20height%3D%223%22%20fill%3D%22%23000%22%3E%3C%2Frect%3E%3Crect%20x%3D%222%22%20y%3D%2213%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%23fff%22%3E%3C%2Frect%3E%3Crect%20x%3D%223%22%20y%3D%2212%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%23fff%22%3E%3C%2Frect%3E%3Crect%20x%3D%224%22%20y%3D%2213%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%23fff%22%3E%3C%2Frect%3E%3Crect%20x%3D%225%22%20y%3D%2212%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%23fff%22%3E%3C%2Frect%3E%3Crect%20x%3D%226%22%20y%3D%2213%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%23fff%22%3E%3C%2Frect%3E%3Crect%20x%3D%227%22%20y%3D%2212%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%23fff%22%3E%3C%2Frect%3E%3Crect%20x%3D%228%22%20y%3D%2213%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%23fff%22%3E%3C%2Frect%3E%3Crect%20x%3D%229%22%20y%3D%2212%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%23fff%22%3E%3C%2Frect%3E%3C%2Fsvg%3E');
}
.rc-scout__link:link, .rc-scout__link:visited {
color: #3dc06c;
text-decoration: underline;
}
.rc-scout__link:hover, .rc-scout__link:active {
color: #4e8b1d;
}
</style></body></html>
|
