summaryrefslogtreecommitdiff
path: root/miniany/doc/zserge.com_blog_cucu-part2.html
diff options
context:
space:
mode:
Diffstat (limited to 'miniany/doc/zserge.com_blog_cucu-part2.html')
-rw-r--r--miniany/doc/zserge.com_blog_cucu-part2.html575
1 files changed, 575 insertions, 0 deletions
diff --git a/miniany/doc/zserge.com_blog_cucu-part2.html b/miniany/doc/zserge.com_blog_cucu-part2.html
new file mode 100644
index 0000000..83661f7
--- /dev/null
+++ b/miniany/doc/zserge.com_blog_cucu-part2.html
@@ -0,0 +1,575 @@
+<!DOCTYPE html>
+<html lang="en-US">
+ <head><script src="//archive.org/includes/analytics.js?v=cf34f82" type="text/javascript"></script>
+<script type="text/javascript">window.addEventListener('DOMContentLoaded',function(){var v=archive_analytics.values;v.service='wb';v.server_name='wwwb-app210.us.archive.org';v.server_ms=2019;archive_analytics.send_pageview({});});</script>
+<script type="text/javascript" src="https://web-static.archive.org/_static/js/bundle-playback.js?v=t1Bf4PY_" charset="utf-8"></script>
+<script type="text/javascript" src="https://web-static.archive.org/_static/js/wombat.js?v=txqj7nKC" charset="utf-8"></script>
+<script>window.RufflePlayer=window.RufflePlayer||{};window.RufflePlayer.config={"autoplay":"on","unmuteOverlay":"hidden"};</script>
+<script type="text/javascript" src="https://web-static.archive.org/_static/js/ruffle.js"></script>
+<script type="text/javascript">
+ __wm.init("http://web.archive.org/web");
+ __wm.wombat("http://zserge.com:80/blog/cucu-part2.html","20160508094511","http://web.archive.org/","web","https://web-static.archive.org/_static/",
+ "1462700711");
+</script>
+<link rel="stylesheet" type="text/css" href="https://web-static.archive.org/_static/css/banner-styles.css?v=S1zqJCYt" />
+<link rel="stylesheet" type="text/css" href="https://web-static.archive.org/_static/css/iconochive.css?v=qtvMKcIJ" />
+<!-- End Wayback Rewrite JS Include -->
+
+ <meta charset="UTF-8"/>
+ <title>cucu: a compiler you can understand (2/3)</title>
+ <meta content="Compilers is fun. Want to write your own one?" name="description"/>
+ <meta content="Serge Zaitsev" name="author"/>
+ <meta content="IE=edge" http-equiv="X-UA-Compatible"/>
+ <meta content="width=device-width" name="viewport"/>
+ <link href="http://web.archive.org/web/20160508094511/http://zserge.com/rss.xml" rel="alternate" title="RSS" type="application/rss+xml"/>
+ <link href="blog/cucu-part2.html" rel="canonical"/> <!-- OpenGraph data -->
+ <meta content="cucu: a compiler you can understand (2/3)" property="og:title"/>
+ <meta content="article" property="og:type"/>
+ <meta content="blog/cucu-part2.html" property="og:url"/>
+ <meta content="http://web.archive.org/web/20160508094511im_/http://zserge.com/logo.png" property="og:image"/>
+ <meta content="Compilers is fun. Want to write your own one?" property="og:description"/>
+ <meta content="en_US" property="og:locale"/> <!-- Twitter card data -->
+ <meta content="summary" name="twitter:card"/>
+ <meta content="@zsergo" name="twitter:site"/> <!-- Fonts -->
+ <link href="//web.archive.org/web/20160508094511cs_/http://fonts.googleapis.com/css?family=Merriweather:900,900italic,300,300italic" rel="stylesheet" type="text/css"/>
+ <link href="//web.archive.org/web/20160508094511cs_/http://fonts.googleapis.com/css?family=Roboto+Mono:100,200,300,400,400italic,700,700italic&amp;subset=latin,latin-ext" rel="stylesheet" type="text/css"/> <!-- Styles -->
+ <link href="/web/20160508094511cs_/http://zserge.com/styles.css" rel="stylesheet" type="text/css"/> <!-- Favicons -->
+ <link href="/web/20160508094511im_/http://zserge.com/favicon.ico" rel="shortcut icon"/>
+ <link href="/web/20160508094511im_/http://zserge.com/favicon.128.png" rel="apple-touch-icon-precomposed"/>
+ </head>
+ <body><!-- BEGIN WAYBACK TOOLBAR INSERT -->
+<script>__wm.rw(0);</script>
+<div id="wm-ipp-base" lang="en" style="display:none;direction:ltr;">
+<div id="wm-ipp" style="position:fixed;left:0;top:0;right:0;">
+<div id="donato" style="position:relative;width:100%;">
+ <div id="donato-base">
+ <iframe id="donato-if" src="https://archive.org/includes/donate.php?as_page=1&amp;platform=wb&amp;referer=http%3A//web.archive.org/web/20160508094511/http%3A//zserge.com/blog/cucu-part2.html"
+ scrolling="no" frameborder="0" style="width:100%; height:100%">
+ </iframe>
+ </div>
+</div><div id="wm-ipp-inside">
+ <div id="wm-toolbar" style="position:relative;display:flex;flex-flow:row nowrap;justify-content:space-between;">
+ <div id="wm-logo" style="/*width:110px;*/padding-top:12px;">
+ <a href="/web/" title="Wayback Machine home page"><img src="https://web-static.archive.org/_static/images/toolbar/wayback-toolbar-logo-200.png" srcset="https://web-static.archive.org/_static/images/toolbar/wayback-toolbar-logo-100.png, https://web-static.archive.org/_static/images/toolbar/wayback-toolbar-logo-150.png 1.5x, https://web-static.archive.org/_static/images/toolbar/wayback-toolbar-logo-200.png 2x" alt="Wayback Machine" style="width:100px" border="0" /></a>
+ </div>
+ <div class="c" style="display:flex;flex-flow:column nowrap;justify-content:space-between;flex:1;">
+ <form class="u" style="display:flex;flex-direction:row;flex-wrap:nowrap;" target="_top" method="get" action="/web/submit" name="wmtb" id="wmtb"><input type="text" name="url" id="wmtbURL" value="http://zserge.com/blog/cucu-part2.html" onfocus="this.focus();this.select();" style="flex:1;"/><input type="hidden" name="type" value="replay" /><input type="hidden" name="date" value="20160508094511" /><input type="submit" value="Go" />
+ </form>
+ <div style="display:flex;flex-flow:row nowrap;align-items:flex-end;">
+ <div class="s" id="wm-nav-captures" style="flex:1;">
+ <a class="t" href="/web/20160508094511*/http://zserge.com/blog/cucu-part2.html" title="See a list of every capture for this URL">16 captures</a>
+ <div class="r" title="Timespan for captures of this URL">27 Oct 2012 - 20 Sep 2022</div>
+ </div>
+ <div class="k">
+ <a href="" id="wm-graph-anchor">
+ <div id="wm-ipp-sparkline" title="Explore captures for this URL" style="position: relative">
+ <canvas id="wm-sparkline-canvas" width="725" height="27" border="0"></canvas>
+ </div>
+ </a>
+ </div>
+ </div>
+ </div>
+ <div class="n">
+ <table>
+ <tbody>
+ <!-- NEXT/PREV MONTH NAV AND MONTH INDICATOR -->
+ <tr class="m">
+ <td class="b" nowrap="nowrap"><a href="http://web.archive.org/web/20160402090213/http://zserge.com:80/blog/cucu-part2.html" title="02 Apr 2016"><strong>Apr</strong></a></td>
+ <td class="c" id="displayMonthEl" title="You are here: 09:45:11 May 08, 2016">MAY</td>
+ <td class="f" nowrap="nowrap"><a href="http://web.archive.org/web/20220920105319/https://zserge.com/blog/cucu-part2.html" title="20 Sep 2022"><strong>Sep</strong></a></td>
+ </tr>
+ <!-- NEXT/PREV CAPTURE NAV AND DAY OF MONTH INDICATOR -->
+ <tr class="d">
+ <td class="b" nowrap="nowrap"><a href="http://web.archive.org/web/20160402090213/http://zserge.com:80/blog/cucu-part2.html" title="09:02:13 Apr 02, 2016"><img src="https://web-static.archive.org/_static/images/toolbar/wm_tb_prv_on.png" alt="Previous capture" width="14" height="16" border="0" /></a></td>
+ <td class="c" id="displayDayEl" style="width:34px;font-size:22px;white-space:nowrap;" title="You are here: 09:45:11 May 08, 2016">08</td>
+ <td class="f" nowrap="nowrap"><a href="http://web.archive.org/web/20220920105319/https://zserge.com/blog/cucu-part2.html" title="10:53:19 Sep 20, 2022"><img src="https://web-static.archive.org/_static/images/toolbar/wm_tb_nxt_on.png" alt="Next capture" width="14" height="16" border="0" /></a></td>
+ </tr>
+ <!-- NEXT/PREV YEAR NAV AND YEAR INDICATOR -->
+ <tr class="y">
+ <td class="b" nowrap="nowrap"><a href="http://web.archive.org/web/20150405230948/http://zserge.com:80/blog/cucu-part2.html" title="05 Apr 2015"><strong>2015</strong></a></td>
+ <td class="c" id="displayYearEl" title="You are here: 09:45:11 May 08, 2016">2016</td>
+ <td class="f" nowrap="nowrap"><a href="http://web.archive.org/web/20220920105319/https://zserge.com/blog/cucu-part2.html" title="20 Sep 2022"><strong>2022</strong></a></td>
+ </tr>
+ </tbody>
+ </table>
+ </div>
+ <div class="r" style="display:flex;flex-flow:column nowrap;align-items:flex-end;justify-content:space-between;">
+ <div id="wm-btns" style="text-align:right;height:23px;">
+ <span class="xxs">
+ <div id="wm-save-snapshot-success">success</div>
+ <div id="wm-save-snapshot-fail">fail</div>
+ <a id="wm-save-snapshot-open" href="#" title="Share via My Web Archive" >
+ <span class="iconochive-web"></span>
+ </a>
+ <a href="https://archive.org/account/login.php" title="Sign In" id="wm-sign-in">
+ <span class="iconochive-person"></span>
+ </a>
+ <span id="wm-save-snapshot-in-progress" class="iconochive-web"></span>
+ </span>
+ <a class="xxs" href="http://faq.web.archive.org/" title="Get some help using the Wayback Machine" style="top:-6px;"><span class="iconochive-question" style="color:rgb(87,186,244);font-size:160%;"></span></a>
+ <a id="wm-tb-close" href="#close" style="top:-2px;" title="Close the toolbar"><span class="iconochive-remove-circle" style="color:#888888;font-size:240%;"></span></a>
+ </div>
+ <div id="wm-share" class="xxs">
+ <a href="/web/20160508094511/http://web.archive.org/screenshot/http://zserge.com/blog/cucu-part2.html"
+ id="wm-screenshot"
+ title="screenshot">
+ <span class="wm-icon-screen-shot"></span>
+ </a>
+ <a href="#" id="wm-video" title="video">
+ <span class="iconochive-movies"></span>
+ </a>
+ <a id="wm-share-facebook" href="#" data-url="http://web.archive.org/web/20160508094511/http://zserge.com:80/blog/cucu-part2.html" title="Share on Facebook" style="margin-right:5px;" target="_blank"><span class="iconochive-facebook" style="color:#3b5998;font-size:160%;"></span></a>
+ <a id="wm-share-twitter" href="#" data-url="http://web.archive.org/web/20160508094511/http://zserge.com:80/blog/cucu-part2.html" title="Share on Twitter" style="margin-right:5px;" target="_blank"><span class="iconochive-twitter" style="color:#1dcaff;font-size:160%;"></span></a>
+ </div>
+ <div style="padding-right:2px;text-align:right;white-space:nowrap;">
+ <a id="wm-expand" class="wm-btn wm-closed" href="#expand" onclick="__wm.ex(event);return false;"><span id="wm-expand-icon" class="iconochive-down-solid"></span> <span class="xxs" style="font-size:80%;">About this capture</span></a>
+ </div>
+ </div>
+ </div>
+ <div id="wm-capinfo" style="border-top:1px solid #777;display:none; overflow: hidden">
+ <div id="wm-capinfo-notice" source="api"></div>
+ <div id="wm-capinfo-collected-by">
+ <div style="background-color:#666;color:#fff;font-weight:bold;text-align:center">COLLECTED BY</div>
+ <div style="padding:3px;position:relative" id="wm-collected-by-content">
+ <div style="display:inline-block;vertical-align:top;width:50%;">
+ <span class="c-logo" style="background-image:url(https://archive.org/services/img/alexacrawls);"></span>
+ Organization: <a style="color:#33f;" href="https://archive.org/details/alexacrawls" target="_new"><span class="wm-title">Alexa Crawls</span></a>
+ <div style="max-height:75px;overflow:hidden;position:relative;">
+ <div style="position:absolute;top:0;left:0;width:100%;height:75px;background:linear-gradient(to bottom,rgba(255,255,255,0) 0%,rgba(255,255,255,0) 90%,rgba(255,255,255,255) 100%);"></div>
+ Starting in 1996, <a href="http://www.alexa.com/">Alexa Internet</a> has been donating their crawl data to the Internet Archive. Flowing in every day, these data are added to the <a href="http://web.archive.org/">Wayback Machine</a> after an embargo period.
+ </div>
+ </div>
+ <div style="display:inline-block;vertical-align:top;width:49%;">
+ <span class="c-logo" style="background-image:url(https://archive.org/services/img/alexacrawls)"></span>
+ <div>Collection: <a style="color:#33f;" href="https://archive.org/details/alexacrawls" target="_new"><span class="wm-title">Alexa Crawls</span></a></div>
+ <div style="max-height:75px;overflow:hidden;position:relative;">
+ <div style="position:absolute;top:0;left:0;width:100%;height:75px;background:linear-gradient(to bottom,rgba(255,255,255,0) 0%,rgba(255,255,255,0) 90%,rgba(255,255,255,255) 100%);"></div>
+ Starting in 1996, <a href="http://www.alexa.com/">Alexa Internet</a> has been donating their crawl data to the Internet Archive. Flowing in every day, these data are added to the <a href="http://web.archive.org/">Wayback Machine</a> after an embargo period.
+ </div>
+ </div>
+ </div>
+ </div>
+ <div id="wm-capinfo-timestamps">
+ <div style="background-color:#666;color:#fff;font-weight:bold;text-align:center" title="Timestamps for the elements of this page">TIMESTAMPS</div>
+ <div>
+ <div id="wm-capresources" style="margin:0 5px 5px 5px;max-height:250px;overflow-y:scroll !important"></div>
+ <div id="wm-capresources-loading" style="text-align:left;margin:0 20px 5px 5px;display:none"><img src="https://web-static.archive.org/_static/images/loading.gif" alt="loading" /></div>
+ </div>
+ </div>
+ </div></div></div></div><div id="wm-ipp-print">The Wayback Machine - http://web.archive.org/web/20160508094511/http://zserge.com:80/blog/cucu-part2.html</div>
+<script type="text/javascript">//<![CDATA[
+__wm.bt(725,27,25,2,"web","http://zserge.com/blog/cucu-part2.html","20160508094511",1996,"https://web-static.archive.org/_static/",["https://web-static.archive.org/_static/css/banner-styles.css?v=S1zqJCYt","https://web-static.archive.org/_static/css/iconochive.css?v=qtvMKcIJ"], false);
+ __wm.rw(1);
+//]]></script>
+<!-- END WAYBACK TOOLBAR INSERT -->
+
+ <header>
+ <nav>
+ <a class="logo" href="/web/20160508094511/http://zserge.com/">Z</a>
+ </nav>
+ <div class="empty"></div>
+ <nav>
+ <section>
+ <a href="/web/20160508094511/http://zserge.com/about.html">about</a>
+ <a href="/web/20160508094511/http://zserge.com/blog.html">posts</a>
+ </section>
+ <section>
+ <a href="http://web.archive.org/web/20160508094511/https://twitter.com/zsergo">@me</a>
+ <a href="http://web.archive.org/web/20160508094511/https://plus.google.com/u/0/+SergeZaitsev">+me</a>
+ <a href="http://web.archive.org/web/20160508094511/https://github.com/zserge">&lt;/&gt;me</a>
+ </section>
+ </nav>
+ </header>
+ <h1>cucu: a compiler u can understand (part&nbsp;2)</h1>
+
+<p>So far, we have defined language grammar and have written a lexer. In this part
+we will write a parser for our language. Before we start, we need some helper
+functions:</p>
+
+<pre><code>int peek(char *s) {
+ return (strcmp(tok, s) == 0);
+}
+
+int accept(char *s) {
+ if (peek(s)) {
+ readtok();
+ return 1;
+ }
+ return 0;
+}
+
+int expect(char *s) {
+ if (accept(s) == 0) {
+ error(&quot;Error: expected '%s'\n&quot;, s);
+ }
+}
+</code></pre>
+
+<p><code>peek()</code> returns non-zero value if the next token is equal to the given string.
+<code>accept()</code> reads the next token, if it&rsquo;s equal to the given string, otherwise it
+ returns 0. And <code>expect()</code> helps us to check language syntax.</p>
+
+<h2>the harder part</h2>
+
+<p>As you can see from the language grammar, statements and various expression
+types are strongly interconnected. It means we have to write all parser
+functions at once, keeping in mind the recursion. Let&rsquo;s go again from top
+to bottom. Here&rsquo;s our top-level compiler() functions:</p>
+
+<pre><code>static int typename();
+static void statement();
+
+static void compile() {
+ while (tok[0] != 0) { /* until EOF */
+ if (typename() == 0) {
+ error(&quot;Error: type name expected\n&quot;);
+ }
+ DEBUG(&quot;identifier: %s\n&quot;, tok);
+ readtok();
+ if (accept(&quot;;&quot;)) {
+ DEBUG(&quot;variable definition\n&quot;);
+ continue;
+ }
+ expect(&quot;(&quot;);
+ int argc = 0;
+ for (;;) {
+ argc++;
+ typename();
+ DEBUG(&quot;function argument: %s\n&quot;, tok);
+ readtok();
+ if (peek(&quot;)&quot;)) {
+ break;
+ }
+ expect(&quot;,&quot;);
+ }
+ expect(&quot;)&quot;);
+ if (accept(&quot;;&quot;) == 0) {
+ DEBUG(&quot;function body\n&quot;);
+ statement();
+ }
+ }
+}
+</code></pre>
+
+<p>It reads type name, then an identifier. If it&rsquo;s followed by a semicolon -
+it&rsquo;s a variable declaration. If it&rsquo;s followed by a paren - it&rsquo;s a function.
+Function scans function arguments one by one, and if function is not
+followed by a semicolon - it&rsquo;s a definition (function with a body), otherwise -
+it&rsquo;s just a declaration (just function name and prototype).</p>
+
+<p>Here, <code>typename()</code> is function that just skips the valid type name. We accept
+only <code>int</code> and <code>char</code> and various pointers to them (<code>char *</code>):</p>
+
+<pre><code>static int typename() {
+ if (peek(&quot;int&quot;) || peek(&quot;char&quot;)) {
+ readtok();
+ while (accept(&quot;*&quot;));
+ return 1;
+ }
+ return 0;
+}
+</code></pre>
+
+<p>The most interesting part is the <code>statement()</code> function. It parses a single
+statement, which can be a block, a local variable definition/declaration,
+a <code>return</code> statement etc. Here how it should look like:</p>
+
+<pre><code>static void statement() {
+ if (accept(&quot;{&quot;)) {
+ while (accept(&quot;}&quot;) == 0) {
+ statement();
+ }
+ } else if (typename()) {
+ DEBUG(&quot;local variable: %s\n&quot;, tok);
+ readtok();
+ if (accept(&quot;=&quot;)) {
+ expr();
+ DEBUG(&quot; :=\n&quot;);
+ }
+ expect(&quot;;&quot;);
+ } else if (accept(&quot;if&quot;)) {
+ /* TODO */
+ } else if (accept(&quot;while&quot;)) {
+ /* TODO */
+ } else if (accept(&quot;return&quot;)) {
+ if (peek(&quot;;&quot;) == 0) {
+ expr();
+ }
+ expect(&quot;;&quot;);
+ DEBUG(&quot;RET\n&quot;);
+ } else {
+ expr();
+ expect(&quot;;&quot;);
+ }
+}
+</code></pre>
+
+<p>So, if it&rsquo;s a block <code>{ .. }</code> - just read statements until end of block is met.
+If it starts with a type name - it&rsquo;s a local variable. Conditional statements
+(&ldquo;if/then/else&rdquo;) and loops are just stubs for now. Think of how you would
+implement them according to the grammar we use.</p>
+
+<p>Anyway, most of the statement contain expressions inside. So, we need to make a
+function that parses an expression. Expression parser is a recursive descent
+parser, so it&rsquo;s a number of functions that call each other recursively until
+primary expression is found. Primary expression as we can see from the grammar
+is a number (constant) or an identifier (variable or function).</p>
+
+<pre><code>static void prim_expr() {
+ if (isdigit(tok[0])) {
+ DEBUG(&quot; const-%s &quot;, tok);
+ } else if (isalpha(tok[0])) {
+ DEBUG(&quot; var-%s &quot;, tok);
+ } else if (accept(&quot;(&quot;)) {
+ expr();
+ expect(&quot;)&quot;);
+ } else {
+ error(&quot;Unexpected primary expression: %s\n&quot;, tok);
+ }
+ readtok();
+}
+
+static void postfix_expr() {
+ prim_expr();
+ if (accept(&quot;[&quot;)) {
+ expr();
+ expect(&quot;]&quot;);
+ DEBUG(&quot; [] &quot;);
+ } else if (accept(&quot;(&quot;)) {
+ if (accept(&quot;)&quot;) == 0) {
+ expr();
+ DEBUG(&quot; FUNC-ARG\n&quot;);
+ while (accept(&quot;,&quot;)) {
+ expr();
+ DEBUG(&quot; FUNC-ARG\n&quot;);
+ }
+ expect(&quot;)&quot;);
+ }
+ DEBUG(&quot; FUNC-CALL\n&quot;);
+ }
+}
+
+static void add_expr() {
+ postfix_expr();
+ while (peek(&quot;+&quot;) || peek(&quot;-&quot;)) {
+ if (accept(&quot;+&quot;)) {
+ postfix_expr();
+ DEBUG(&quot; + &quot;);
+ } else if (accept(&quot;-&quot;)) {
+ postfix_expr();
+ DEBUG(&quot; - &quot;);
+ }
+ }
+}
+
+static void shift_expr() {
+ add_expr();
+ while (peek(&quot;&lt;&lt;&quot;) || peek(&quot;&gt;&gt;&quot;)) {
+ if (accept(&quot;&lt;&lt;&quot;)) {
+ add_expr();
+ DEBUG(&quot; &lt;&lt; &quot;);
+ } else if (accept(&quot;&gt;&gt;&quot;)) {
+ add_expr();
+ DEBUG(&quot; &gt;&gt; &quot;);
+ }
+ }
+}
+
+static void rel_expr() {
+ shift_expr();
+ while (peek(&quot;&lt;&quot;)) {
+ if (accept(&quot;&lt;&quot;)) {
+ shift_expr();
+ DEBUG(&quot; &lt; &quot;);
+ }
+ }
+}
+
+static void eq_expr() {
+ rel_expr();
+ while (peek(&quot;==&quot;) || peek(&quot;!=&quot;)) {
+ if (accept(&quot;==&quot;)) {
+ rel_expr();
+ DEBUG(&quot; == &quot;);
+ } else if (accept(&quot;!=&quot;)) {
+ rel_expr();
+ DEBUG(&quot;!=&quot;);
+ }
+ }
+}
+
+static void bitwise_expr() {
+ eq_expr();
+ while (peek(&quot;|&quot;) || peek(&quot;&amp;&quot;)) {
+ if (accept(&quot;|&quot;)) {
+ eq_expr();
+ DEBUG(&quot; OR &quot;);
+ } else if (accept(&quot;&amp;&quot;)) {
+ eq_expr();
+ DEBUG(&quot; AND &quot;);
+ }
+ }
+}
+
+static void expr() {
+ bitwise_expr();
+ if (accept(&quot;=&quot;)) {
+ expr();
+ DEBUG(&quot; := &quot;);
+ }
+}
+</code></pre>
+
+<p>It&rsquo;s a big piece of code, but don&rsquo;t be afraid - it&rsquo;s really simple.
+Every function that parses expression type first tries to call a
+more prioritized expression parser. Then, if an expected operator is found -
+it calls more prioritized expression parser again. Now it has parsed both
+parts of a binary expression (like x+y, or x&amp;y, or x==y), so it can perform
+an operation and return. Some expression can be &ldquo;chained&rdquo; (like a+b+c+d), so
+we parse them with loops.</p>
+
+<p>We put debug output after every expression parser function. This will give us
+an interesting result. For example, if we parse this piece of code:</p>
+
+<pre><code>int main(int argc, char **argv) {
+ int i = 2 + 3;
+ char *s;
+ func(i+2, i == 2 + 2, s[i+2]);
+ return i &amp; 34 + 2;
+}
+</code></pre>
+
+<p>we will get this ouput:</p>
+
+<pre><code>identifier: main
+function argument: argc
+function argument: argv
+function body
+local variable: i
+ const-2 const-3 + :=
+local variable: s
+ var-func var-i const-2 + FUNC-ARG
+ var-i const-2 const-2 + == FUNC-ARG
+ var-s var-i const-2 + [] FUNC-ARG
+ FUNC-CALL
+ var-i const-34 const-2 + AND RET
+</code></pre>
+
+<p>All our expressions are written in a postfix form (instead of <code>2+3</code> it&rsquo;s <code>2 3
++</code>). This is a natural form for stack machines, when operands are placed on
+the stack, then a function called pops up the operands, processes them and puts
+the result back on the stack.</p>
+
+<p>Though it might not be an optimal architecture for most modern CPUs, which are
+register-based, it&rsquo;s still very simple and fits our compiler needs.</p>
+
+<h2>symbols</h2>
+
+<p>Ok, we are good. We&rsquo;ve got a lexer and a parser in less than 300 lines of code.
+What we need to do is to add some functions to work with the symbols (like
+variable names, or functions). A compiler should have a table of symbols to
+quickly find their addresses, so when you write &ldquo;i = 0&rdquo; - it means put zero
+into the location at address 0x1234 in RAM (if symbol &ldquo;i&rdquo; has address 0x1234 in
+memory).
+Also, when you call &ldquo;func()&rdquo; it means - jump to address 0x5678 (if symbol &ldquo;func&rdquo;
+has value of 0x5678).</p>
+
+<p>We use the following structure for symbols:</p>
+
+<pre><code>struct sym {
+ char type;
+ int addr;
+ char name[];
+};
+</code></pre>
+
+<p>Here <code>type</code> has special meaning. We use a single-letter codes to detect symbol
+type:</p>
+
+<ul>
+<li><code>L</code> - is a local variable. <code>addr</code> stores variable location on the stack</li>
+<li><code>A</code> - function argument. <code>addr</code> also stores the location on the stack</li>
+<li><code>U</code> - undefined global variable. <code>addr</code> stores absolute address in RAM.</li>
+<li><code>D</code> - defined global variable. Same as above.</li>
+</ul>
+
+<p>So far, I&rsquo;ve added two functions: <code>sym_find(char *s)</code> to find symbol by its
+name, and <code>sym_declare()</code> to add a new symbol.</p>
+
+<p>Now we&rsquo;re are ready to develop <a href="/web/20160508094511/http://zserge.com/blog/cucu-part3.html">backend architecture &rarr;</a></p>
+
+<p><em>Check <a href="/web/20160508094511/http://zserge.com/blog/cucu-part1.html">part 1</a> if you missed something</em></p>
+
+ <p>Posted on 2012-10-24</p>
+ <section class="social">
+ <section>
+ <a href="http://web.archive.org/web/20160508094511/http://www.facebook.com/share.php?u=http://zserge.com/blog/cucu-part2.html&amp;title=cucu:%20a%20compiler%20you%20can%20understand%20%282/3%29" style="background-color: #3b5997">like</a>
+ &nbsp;
+ <a href="http://web.archive.org/web/20160508094511/http://twitter.com/intent/tweet?status=cucu:%20a%20compiler%20you%20can%20understand%20%282/3%29+http://zserge.com/blog/cucu-part2.html%20via%20@zsergo" style="background-color: #41b7d8">tweet</a>
+ &nbsp;
+ <a href="http://web.archive.org/web/20160508094511/https://plus.google.com/share?url=http://zserge.com/blog/cucu-part2.html" style="background-color: #d64937">+1</a>
+ </section>
+ <section>
+ <a href="/web/20160508094511/http://zserge.com/rss.xml" style="background-color: #f26522">rss</a>
+ &nbsp;
+ <a href="http://web.archive.org/web/20160508094511/https://twitter.com/zsergo" style="background-color: #41b7d8">@me</a>
+ &nbsp;
+ <a href="http://web.archive.org/web/20160508094511/https://plus.google.com/u/0/+SergeZaitsev" style="background-color: #d64937">+me</a>
+ &nbsp;
+ <a href="http://web.archive.org/web/20160508094511/https://github.com/zserge" style="background-color: #333333">&lt;/&gt;me</a>
+ </section>
+ </section>
+ <section><div id="disqus_thread"></div><script type="text/javascript">
+var disqus_shortname='zserge';
+ (function() {
+ var dsq = document.createElement('script');
+ dsq.type = 'text/javascript';
+ dsq.async = true;
+ dsq.src = 'http://' + disqus_shortname + '.disqus.com/embed.js';
+ (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
+ })();
+ </script>
+<noscript>
+</noscript>
+
+</section>
+ <footer>
+ <p>
+ &copy;2012&ndash;2015 &middot;
+ <a href="http://web.archive.org/web/20160508094511/http://zserge.com/">Serge Zaitsev</a>
+ &middot;
+ <a href="http://web.archive.org/web/20160508094511/mailto:zaitsev.serge@gmail.com">zaitsev.serge@gmail.com</a>
+ </p>
+ </footer>
+ <script>
+ (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
+ (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
+ m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
+ })(window,document,'script','//web.archive.org/web/20160508094511/http://www.google-analytics.com/analytics.js','ga');
+ ga('create', 'UA-33644825-1', 'zserge.com');
+ ga('send', 'pageview');
+</script>
+
+
+ </body>
+</html>
+<!--
+ FILE ARCHIVED ON 09:45:11 May 08, 2016 AND RETRIEVED FROM THE
+ INTERNET ARCHIVE ON 17:21:31 Jan 12, 2024.
+ JAVASCRIPT APPENDED BY WAYBACK MACHINE, COPYRIGHT INTERNET ARCHIVE.
+
+ ALL OTHER CONTENT MAY ALSO BE PROTECTED BY COPYRIGHT (17 U.S.C.
+ SECTION 108(a)(3)).
+-->
+<!--
+playback timings (ms):
+ captures_list: 1644.92 (11)
+ exclusion.robots: 0.202
+ exclusion.robots.policy: 0.19
+ cdx.remote: 0.077
+ esindex: 0.011
+ LoadShardBlock: 231.62 (3)
+ PetaboxLoader3.datanode: 237.607 (4)
+ load_resource: 369.139
+ PetaboxLoader3.resolve: 308.525
+--> \ No newline at end of file