🚖 🥥 🖖🏿 コンパイル。 1：レクサー 👨🏿‍✈️ 🧛🏼 🧗

私は常にプログラムのプログラムによる誕生の謎に魅了されました。残念ながら、ロシアの大学はこの興味深いトピックにほとんど注意を払っていません。私は小さな効率的なコンパイラを徐々に作成する一連の投稿を書きたいと思っています。

このシリーズの最初の投稿は、1つの小規模で閉鎖的なコミュニティで既に準備され、ベータテストされています。それにもかかわらず、私は、由緒あるhabrapublicの希望を考慮に入れて彼らを支配し続けます。

さらに投稿：

なぜコンパイラを書くのですか？
一般計画
テキスト分析
実用例
どのように機能しますか？

なぜコンパイラを書くのですか？

必要なすべてのプログラミング言語がすでに作成されているわけではありませんか？私たちの賢明な時代の誰が独自のコンパイラを書く必要があるでしょうか？

発明できるものはすべて発明されました。
--Charles H. Duell、米国特許庁長官、1899（帰属）

何だったのでしょう。そして、行われたことが行われ、太陽の下で新しいものは何もありません。
-伝道者1：9（紀元前3世紀頃）

まず、言語は常に作成および開発されています。現在人気のあるもののうち、Ruby、PHP、Java、およびC＃は私たちの記憶の中に作成され、数年前に頻繁に使用され始めました。マイクロソフトは現在、新しいF＃言語を推進しており、マイクロソフトの力を考えれば、一般的な言語の1つになる可能性もあります。
新しい言語にはまだニッチがあります。たとえば、並列プログラミングのための便利な命令型言語を考え出す試みは止まりません。

第二に、コンパイルで使用される技術（主に文法解析）には、他の多くのアプリケーションがあります。多くの場合、プログラミング言語のテキストを解析し、処理し、処理されたテキストを（同じまたは別の言語で）出力する必要がある場合、ソースからソースへの変換（リファクタリング、コードの別の言語への変換など）が必要です。。

もちろん、コンパイルは、 ~~巨大な戦闘ヒューマノイド~~ロボットのプログラミングと並行して、プログラマーにとってかなりエキゾチックな活動です。ただし、他の多くの贅沢なプログラミング趣味とは異なり、これにはすべて実用的なアプリケーションがあります。

一般計画

コンパイルプロセスは、原則として2つの主要な段階で構成されます。

ソーステキスト分析
マシンコード生成

最初の段階で、プログラムのプレゼンテーションが作成されます。これにより、さらに作業を進めるのに便利です。通常はツリーですが、まったく必要ではありません。 2番目の段階で、コンパイラーはツリーを調べて、各ノードの最終コードを生成します。

コンパイラの最も難しい部分はコードの最適化です。最初の段階では、ツリーノードのレベルで高度な最適化が実行されます（たとえば、ループが展開され、インライン関数が埋め込まれます）。 2番目の-低レベル、コマンドのフローのレベル（たとえば、特定のプロセッサのコンベヤーをより完全にロードするために、コマンドが並べ替えられます）。最適化は、伝統的に、大学のコースには決して来ません。しかし、最も単純な（コピーの除去、一定の伝播）この例では実装を試みます。

Habréの解析のトピックに関する古い投稿を見ました。しかし、作成者は一度もコードを生成することに近づいていなかったようです。

テキスト分析

初心者プログラマーがテキストパーサーを記述しようとするとき、彼の自然なアプローチは再帰的な深化です。構造体の先頭を見つけます（たとえば{ 終わりを見つけます（たとえば、同じレベルのネストで} ）。構造の内容を選択し、再帰的に解析します。

このアプローチの問題-最初に、過度の複雑さ（同じテキストの断片に沿って行き来します）; 第二に、サポートの不便さ（言語の構文はキロバイトとキロバイトの分岐コードに分散されます）。

言語構文は宣言的に定義できます。たとえば、誰もが正規表現に精通しています。すべての言語構成体に対して、それぞれの反対側にある正規表現のスタックを書くことが理想的です-プログラムツリーで作成されるべきノードの定義。「ユニバーサルパーサー」は、ある正規表現のプログラムを次々に単純に置き換え、記述に従ってノードを次々に作成します。

これらの問題の最初の問題は、テキスト内のすべての正規表現の検索を1回のパスで実行できるという事実によって解決されます。プログラム全体をメモリに保存する必要はありません。一度に1文字ずつ読み取り、その文字を処理してから忘れてください。
2つ目は、言語の集中化された正式な記述ができたことです。コードにまったく触れることなく正規表現を変更できます。また、その逆の場合、パーサーに損傷を与えることなくコードを変更します。

実用例

言及された「ユニバーサルパーサー」は、もちろん長い間実装されており、複数回使用されています。古典的な実装-lex-は、Cの各正規表現のアクション記述を受け入れます。標準のGNUユーティリティには、 lexと互換性のあるflex含まれており、これを例として使用します。（C＃、Javaなどに同様のユーティリティがあります。）

伝統的に、最初の例は電卓を書くことです：

 ％{
     #include <stdio.h>
     int reg = 0;
     char op = '+';
     int unmin = 0;
 ％}

 ％オプションメイン
 ％オプションyylineno

 %%

 [/†►/†.*\n;  //コメント
 [0-9] {int opnd = atoi（yytext）;
                   if（unmin）opnd =-opnd;  unmin = 0;
                  スイッチ（op）{
                    ケース '+'：reg + = opnd; 休憩;
                    ケース '-'：reg-= opnd; 休憩;
                    ケース '*'：reg * = opnd; 休憩;
                    ケース '/'：reg / = opnd; 休憩;
                   }
                   op = 0;
                 }
 [-+ * /] {if（op）{
                     if（* yytext == '-'）
                       unmin = 1;
                    その他{
                       printf（ "行％d \ nの予期しない演算子"、yylineno）;
                       exit（1）;
                     }
                   }その他
                     op = * yytext;
                 }
 [;] {if（op）{
                     printf（ "行％d \ nの予期しないセミコロン"、yylineno）;
                     exit（1）;
                   }
                   printf（ "=％d \ n"、reg）;
                   reg = 0;
                   op = '+';
                 }
 [\ t \ r \ n];  //空白
 。  {printf（ "行％d \ nの構文エラー"、yylineno）;  exit（1）;  }
 %%

取引市場計算機は市場からシミュレートされます。括弧なし、操作の優先度なし、端数なし。式はセミコロンで区切られ、 //から行末までコメントを挿入できます。

電卓をコンパイルして、試してみてください。

[tyomitch@home ~]$ lex 1.lex
[tyomitch@home ~]$ cc lex.yy.c
[tyomitch@home ~]$ ./a.out
2+2;
=4
2+2*2;
=8
2 + // hello
- 3
;
=-1
2 / /
Unexpected operator in line 6

コード解析

上部のタグ％{％}には、パーサーに直接コピーされるコードがあります。 3つの変数を宣言します：中間結果のreg （ "register"）、型指定された操作のop 、およびunmin操作の記号の後にマイナスが入力されたフラグ。
%option mainは、標準main （ stdinからEOFを読み取る）に満足していることを示し%option main 。 %option yylinenoは、入力テキストの現在の行番号が格納されるパーサーにint yylineno変数を作成します。これは診断メッセージに役立ちます。
%%は、宣言領域を実際の言語規則領域から分離します
各ルールでは、regexpが左側に、Cコードが右側に記述されています。最初の正規表現では、コードは空です。つまりこのような構成（およびこれはコメント）は、単に無視されます。同様に、最後から2番目のルールは、認識された構成要素間のスペースと改行を無視するように規定しています。
2番目のルールでは、 yytext変数を使用します。これは、正規表現（この場合はオペランド番号）に一致するテキストを格納します
3番目のルール-プログラムのテキストでのエラー処理の例（メッセージのテキストでyylinenoを使用します）
ルールは、最初から最後まで、表示される順序で試行されます。一致するものがない場合、パーサーは現在の文字を単にstdoutます。代わりに、最後のルールを追加します。 -任意の文字に一致し、エラーメッセージを出力します。

もちろん、実際のコンパイラでは、ルールは計算結果を画面に出力しませんが、その後のコード生成のために式自体を保存します。

どのように機能しますか？

数学者には、DFA（ 決定論的有限状態機械 ）の概念があります。これは、 N個の状態のいずれかになります。入力ストリームから1文字ずつ読み取ります。そして、テーブルがあります：現在の状態と読み込まれたキャラクターの各組み合わせ、どの状態に行くか。 flexの仕事は、指定された正規表現のセットでDFAを構築することです。一部の州では、このDKAが次のDKAに進むだけでなく、ルールを引き起こします。

生成されたパーサーlex.yy.c中を見て、構築されたDKAを見ることができlex.yy.c 15州がかかりました。スペースを節約するため、変換テーブルは明示的に（サイズが15x256）保存されず、洗練された重複リストに分割されます。最も視覚的な形式で表示するには、 -Cefオプションを使用してパーサーをコンパイルします（「テーブル圧縮を無効にする」）。

静的yyconst short yy_nxt [] [8] =
     {
     {0、0、0、0、0、0、0、0}、
     {3、4、5、6、7、8、9、10}、
     {3、4、5、6、7、8、9、10}、
     {-3、-3、-3、-3、-3、-3、-3、-3、-3}、
     {3、-4、-4、-4、-4、-4、-4、-4、-4}、
     {3、-5、-5、-5、-5、-5、-5、-5}、
     {3、-6、-6、-6、-6、-6、-6、-6、-6}、
     {3、-7、-7、-7、-7、-7、-7、-7}、
     {3、-8、-8、-8、-8、11、-8、-8}、
     {3、-9、-9、-9、-9、-9、12、-9}、
     {3、-10、-10、-10、-10、-10、-10、-10}、
     {3、13、13、14、13、13、13、13、13}、
     {3、-12、-12、-12、-12、-12、12、-12}、
     {3、13、13、14、13、13、13、13、13}、
     {3、-14、-14、-14、-14、-14、-14、-14}、
     };

静的yyconst short int yy_accept [15] =
     {0、
         0、0、8、6、5、5、3、3、2、4
         0、2、0、1
     };

ここでのシンボルは、パーサーの観点からは同一の8つのクラスに分割されます（たとえば、すべての数値が1つのクラスに結合されます）。 static yyconst int yy_ec[256]の個別の配列は、各文字をクラスに関連付けます。

メインのパーサーサイクルは非常に簡単です。

 yy_match：
    while（（yy_current_state = yy_nxt [yy_current_state] [yy_ec [（unsigned char）（* yy_cp）]]））> 0）
        {
        if（yy_accept [yy_current_state]）
            {
            yy_last_accepting_state = yy_current_state;
            yy_last_accepting_cpos = yy_cp;
            }

          yy_cp;
        }

    yy_current_state = -yy_current_state;

遷移表の正の数値は、「状態に進んで読み続ける」ことを意味します。負-「状態に入り、アクションを実行します。」状態にyy_acceptときyy_accept実行する必要のあるアクションの番号はyy_accept格納されyy_accept 。

例について考えてみましょう。数字の場合、「文字クラス」の数は6です。
シンボル6による初期状態（1）では、遷移表9を参照してください。
状態9で、別の数字（6）がある場合は、状態12に進んで読み取ります。
状態12から、別の図がある場合は、読み進めてください。（表には12個あります）
数字以外（6以外の任意の文字）を見つけた場合、アクションを実行する必要があります。9行目には-9、12行目には-12が表示されます。
yy_acceptをチェックしyy_accept 。どちらの場合も、ルール2を適用します（数値を認識するルールは、実際にはパーサーの2番目であることを思い出してください）。
両方で同じことを行う場合にflexが状態9と12を分離することにした理由は明らかではありません。しかし、彼は魂のない鉄片です、彼はよく知っています。

注目すべきことは、パーサーの準備が非常に簡単であることです。異なる構造の分岐認識の代わりに、1つの大きなテーブルと10行のループがあります。しかし、重大な問題があります。投稿の最初から例に戻りましょう。「構築の始まりを見つけてください（例えば{ ）; その終わりを見つけるために（例えば、 同じレベルのネストで} ）...「 同じレベルのネストでregexpはどのように条件を示すのですか？」

数学者も試してみた：彼らはそれが不可能であることを証明した。そのため、ネスト構造をサポートする言語（すべてBATファイルよりも複雑な言語）を解析するには、正規表現よりも強力なツールが必要です。次回は彼について。

コンパイル。 1：レクサー