cucu: a compiler you can understand (part 1)

翻訳者順:
最近いくつかのコンパイラの基本的な知識を勉強して、この英語のブログを見つけて、csdnで検索して翻訳する人がいないようで、だから私はいっそ翻訳して、どうせすべて勉強します.
原文住所:http://zserge.com/blog/cucu-part1.html
cucu:わかりやすいコンパイラ(part 1)
コンパイラについてお話ししましょう.自分でコンパイラを書くことを考えたことがありますか.
私はあなたにこれがどんなに簡単なことかを見せます!しかし、このブログの第1部は少し理論に偏っているので、辛抱強くしてほしいです.
我々の目標
CUCUは「おもちゃ」コンパイラで「おもちゃ」言語をコンパイルします.私はこのおもちゃの言語ができるだけ標準的なC言語のようになることを望んで、そのため1つの正しいCUCUプログラムは同様にCコンパイラを使ってコンパイルすることができます.もちろん、C言語全体の標準は非常に複雑で、私たちのここのCUCUが使っている文法はC言語のほんの一部にすぎません.
たとえば、ここには有効なCUCUプログラムのクリップがあります.

int cucu_strlen(char *s) {
    int i = 0;
    while (s[i]) {
        i = i + 1;
    }
    return i;
}

構文
次に、このプログラミング言語の文法を定義します.これは、コンパイラを設計するときにこの構文に依存するため、重要なステップです.
上から下まで文法を設計しましょう.私たちのソースファイルにはプログラムが含まれています.プログラムとは?経験から分かるように、プログラムは変数宣言、関数宣言、関数定義などのリストです.たとえば、次のようになります.

int func(char *s, int len); /* function declaration */
int i;                      /* variable declaration */

int func(char *s, int len) { /* function definition */
    ...
}

EBNFの形式にしてみましょう(EBNFとは何かを知らなくても大丈夫ですが、直感的に見えます):
(訳者:EBNFの詳細については参照)http://zh.wikipedia.org/wiki/%E6%89%A9%E5%B1%95%E5%B7%B4%E7%A7%91%E6%96%AF%E8%8C%83%E5%BC%8F)

<program> ::= { <var-decl> | <func-decl> | <func-def> } ;

この表現は、1つの関数が変数宣言、関数宣言、または関数定義の繰り返しシーケンスであることを示します.では、これらのいわゆる声明と定義は何なのでしょうか.下へ行きましょう.

<var-decl> ::= <type> <ident> ";"
<func-decl> ::= <type> <ident> "(" <func-args> ")" ";"
<func-def> ::= <type> <ident> "(" <func-args> ")" <func-body>
<func-args> ::= { <type> <ident> "," }
<type> ::= "int" | "char *"

したがって、変数宣言は簡単です.タイプ名に識別子を付け、C言語でよく使われているように、後にセミコロンを付けます.

int i;
char *s;

関数宣言は少し複雑ですが、まず「タイプ+識別子」で、カッコで選択的に加算できます.  <func-args>
関数のパラメータ表は、カンマで区切られたタイプ+識別子のシーケンスです.たとえば、次のようになります.

char *s, int from, int to

実際、パラメータテーブルの最後のカンマはCUCU言語では許可されていますが、必要ではありません.コードを分析するのが簡単になるためです.
言語がサポートするタイプはintとchar*のみで、識別子はアルファベット、数字、または下線の列です.
唯一説明されていないのは<func-body>です.まず、文(statements)と式(experssions)について議論する必要があります.
文は、私たちの言語で最も小さい独立した要素を指します.次は有効な文です.

/*           */
i = 2 + 3; /*      */
my_func(i); /*        */
return i; /*     */

/*          */
if (x > 0) { .. } else { .. }
while (x > 0) { .. }

式は文の一部であり、文よりも小さい.文とは異なり、式は常に値を返します.通常、式は算数予算です.例えば、文func(x[2], i + j)では、式は  x[2]  および  i+j .
そのため、上記の分析によると、

<func-body> ::= <statement>
<statement> ::= "{" { <statement> } "}"                /*     */
                | [<type>] <ident> [ "=" <expr> ] ";"  /*    */
                | "return" <expr> ";"
                | "if" "(" <expr> ")" <statement> [ "else" <statement> ]
                | "while" "(" <expr> ")" <statement>
                | <expr> ";"

以下に、CUCU言語で実行可能な式を示します.

<expr> ::= <bitwise-expr> 
           | <bitwise-expr> = <expr>
<bitwise-expr> ::= <eq-expr>
                   | <bitwise-expr> & <eq-expr>
                   | <bitwise-expr> | <eq-expr>
<eq-expr> ::= <rel-expr>
              | <eq-expr> == <rel-expr>
              | <eq-expr> != <rel-expr>
<rel-expr> ::= <shift-expr>
               | <rel-expr> < <shift-expr>
<shift-expr> ::= <add-expr>
                 | <shift-expr> << <add-expr>
                 | <shift-expr> >> <add-expr>
<add-expr> ::= <postfix-expr>
               | <add-expr> + <postfix-expr>
               | <add-expr> - <postfix-expr>
<postfix-expr> ::= <prim-expr>
                   | <postfix-expr> [ <expr> ]
                   | <postfix-expr> ( <expr> { "," <expr> } )
<prim-expr> := <number> | <ident> | <string> | "(" <expr> ")"

再帰的に定義された式に気づきましたか?さらに、これらの式では、演算子の優先度が下から上に下がることを示します.カッコと角カッコの優先度が高く、割り当ての優先度が低いです.
たとえば、構文定義、式  8>>1+1  の演算順序は  8>>(1+1)(like in)ではなく  (8>>1)+1)  >>  の優先度が低い  + .
ワードアナライザ
文法の問題を解決したら、私たちはほとんど始められません.最初のことは文法分析器を作ることです.我々のコンパイラは入力として1バイトストリームを使用し,文法解析器の役割は,後続の処理を容易にするために,このバイトストリームをより小さなシンボル(token)に分割することである.文法解析器は,後の解析器を簡略化するためにある程度の抽象を提供した.
たとえば、バイトシーケンス 「int i=2+31;」は、以下の記号に分けられます.

int
i
=
2
+
31
;

一般的な構文解析器では、1つの形態素はタイプと値からなる2元グループです.従って、上記のリストに対して、以下のような二元群<TYPE:int>,<ID:i>, <ASSIGN:=>,<NUM:2>,<PLUS:+>,<NUM:31>,<SEMI:;>が得られることがより望ましい.簡単にするために、私たちは今値によってタイプを反転しています.もちろん、これは非常に厳密ではありません.
構文解析器の主な問題は,1バイトがストリームから読み出されると,二度とリフローされないことである.したがって、1バイトを読み、このバイトを現在の記号に追加できない場合は、どうすればいいのでしょうか.このバイトをどこに保存して、現在のシンボル処理が完了してからこのバイトを処理しますか?
実際,ほとんどの文法解析器には予読のメカニズムがある.私たちの文法は簡単なので、1バイトしか必要ありません. -  nextcバッファで十分です.ストリームから読み込まれたが、現在のシンボルに追加されていないバイトを格納します.
また、ここで目を覚まさなければなりません.CUCUのコードの構文解析器で多くのグローバル変数を使用しています.これは悪い習慣だと知っていますが、すべての変数を関数パラメータとすると、このコンパイラのコードはそんなに簡潔ではありません.
文法解析器のすべてが関数です  readtok()  .アルゴリズムも簡単です

先頭のすべてのスペースをスキップ

識別子(アルファベット、数字、および下線のシーケンス)

の読み取りを試みる.

識別子ではないことが判明した場合、いくつかの演算子を読み込みます.たとえば、  &, |, <, >, =, ! .

演算子でない場合は、「...」または「....」のような文字列テキストの読み取りを試みます.

まだ失敗している場合は、コメントかもしれません.  /* ... */

失敗が続く場合は、「(」または「[」などの括弧のような文字を1バイト読み取ってみましょう.

#include <stdio.h> /* for vpritnf */
#include <stdarg.h> /* for va_list */
#include <stdlib.h> /* for exit() */
#include <ctype.h> /* for isspace, isalpha... */

#define MAXTOKSZ 256
static FILE *f; /* input file */
static char tok[MAXTOKSZ];
static int tokpos;
static int nextc;

void readchr() {
    if (tokpos == MAXTOKSZ - 1) {
        tok[tokpos] = '\0';
        fprintf(stderr, "token too long: %s
", tok);
        exit(EXIT_FAILURE);
    }
    tok[tokpos++] = nextc;
    nextc = fgetc(f);
}

void readtok() {
    for (;;) {
        while (isspace(nextc)) {
            nextc = fgetc(f);
        }
        tokpos = 0;
        while(isalnum(nextc) || nextc == '_') {
            readchr();
        }
        if (tokpos == 0) {
            while (nextc == '<' || nextc == '=' || nextc == '>'
                    || nextc == '!' || nextc == '&' || nextc == '|') {
                readchr();
            }
        }
        if (tokpos == 0) {
            if (nextc == '\'' || nextc == '"') {
                char c = nextc;
                readchr();
                while (nextc != c) {
                    readchr();
                }
                readchr();
            } else if (nextc == '/') {
                readchr();
                if (nextc == '*') {
                    nextc = fgetc(f);
                    while (nextc != '/') {
                        while (nextc != '*') {
                            nextc = fgetc(f);
                        }
                        nextc = fgetc(f);
                    }
                    nextc = fgetc(f);
                }
            } else if (nextc != EOF) {
                readchr();
            }
        }
        break;
    }
    tok[tokpos] = '\0';
}

int main() {
    f = stdin;
    nextc = fgetc(f);

    for (;;) {
        readtok();
        printf("TOKEN: %s
", tok);
        if (tok[0] == '\0') break;
    }
    return 0;
}

C言語のソースファイルをこの構文解析器の入力として使用すると、1つの記号のリストが出力され、各記号が1行ずつ出力されます.終了したら、少し休んで、2番目の部分に入りましょう.