技術
コウノトリ：C ++でプログラミング言語を作成する方法
パート1：トークナイザー
このシリーズでは、新しいスクリプト言語を開発し、そのプロセスを段階的に説明します。
不思議な読者の頭に浮かぶ最初の質問は、次のようになります。 「本当に新しいプログラミング言語が必要ですか？」
本当に新しいプログラミング言語が必要ですか？
この質問に答えるために、私は自分自身に小さな余談を許します。
なぜ建築家は自分の建物にシンプルで反復的なリズムを選ぶのでしょうか？
あなたが建築家（ソフトウェアではなく実際の実店舗の建築家）であり、非常に官僚的な国で生まれるほど運が悪いと想像してみてください。あなたは未開発の故郷にあるショッピングモールの素晴らしいアイデアを持っているので、プロジェクトを作成して建築許可を申請します。もちろん、彼らはあなたが登録された会社を持っていないという理由であなたをすぐに拒絶します。だから、あなたは会社を登録します。それをするために、あなたはいくらかのお金を預ける必要があります。次に、あなたはあなたの会社の名前を思いつきますが、それは拒否されます。 5回目の試行で承認され、アプリケーションはヒープの最下部に移動します。最終的に、あなたはあきらめるか、その間に他の誰かがショッピングモールを建てたことに気づきます。
しかし、私たちは本物の建築家ではありません。私たちです ソフトウェアエンジニア 、そして私たちは許可や官僚主義なしで私たちのアイデアを実現する特権を持っています。私たちに必要なのは、余暇と、数独パズルの代わりにプログラミングに費やす意志だけです。
それでもプログラミングの動機が純粋な好奇心ではないと主張する場合は、私が設計した最初のプログラミング言語は、単なる好奇心ではなく、必然性の結果として開発されたとだけ言っておきます。ただし、それがこのブログを読む最初の動機ではありません。ここで出会う多くのアイデアは、実際に独自のプログラミング言語を作成する必要がない場合でも、興味を持ち続けるためにかなり興味深く革新的だと思います。
フットプリントの小さいスクリプト言語を開発するという私たちの目標は、それを「コウノトリ」と名付けるように私を刺激しました。幸いなことに、名前を承認するように官僚を説得する必要はありません。
シリーズを進めながらプログラミング言語を開発していくので、バグも発生する可能性があります。シリーズの終わりに近づくにつれて、それらは解決されるべきです。
ここで説明するすべての完全なソースコードは、次のURLから無料で入手できます。 GitHub 。
最後に、この段落のタイトルからの質問に答えるために、いいえ、実際には新しいプログラミング言語は必要ありませんが、C ++でプログラミング言語を作成する方法をデモンストレーションしようとしているため、デモンストレーション用に作成します。 。
Tokenizerのリトルヘルパー
他のプログラマーが定期的に同じ問題に直面しているかどうかはわかりませんが、この問題に頻繁に直面しています。
対数時間で値を高速に取得する必要があるKey-Valueコンテナーが必要です。ただし、コンテナを初期化した後は、コンテナに新しい値を追加したくありません。したがって、std::map （またはstd::unordered_map）は、高速挿入も可能にするため、やり過ぎです。
ラズベリーパイに最適なウェブサーバー
私は不必要な最適化に完全に反対していますが、この場合、多くのメモリが何にも無駄になっていないように感じます。それだけでなく、後で実装する必要があります 最大のムンク そのようなコンテナの上にあるアルゴリズム、およびmapそのための最良のコンテナではありません。
2番目の選択肢はstd::vectorで、挿入後にソートされます。このアプローチの唯一の問題は、ベクトルがソートされていることを覚えておく必要があるため、コードの可読性が低いことです。そこで、その制約を保証する小さなクラスを開発しました。
（すべての関数、クラスなどは名前空間storkで宣言されています。読みやすくするためにその名前空間は省略します。）
template class lookup { public: using value_type = std::pair; using container_type = std::vector; private: container_type _container; public: using iterator = typename container_type::const_iterator; using const_iterator = iterator; lookup(std::initializer_list init) : _container(init) { std::sort(_container.begin(), _container.end()); } lookup(container_type container) : _container(std::move(container)) { std::sort(_container.begin(), _container.end()); } const_iterator begin() const { return _container.begin(); } const_iterator end() const { return _container.end(); } template const_iterator find(const K& key) const { const_iterator it = std::lower_bound( begin(), end(), key, [](const value_type& p, const K& key) { return p.first first == key ? it : end(); } size_t size() const { return _container.size(); } }; ご覧のとおり、このクラスの実装は非常に簡単です。考えられるすべてのメソッドを実装したくはありませんでした。必要なメソッドだけを実装しました。基になるコンテナーはvectorであるため、事前入力されたvectorまたはinitializer_listで初期化できます。
トークナイザーは、入力ストリームから文字を読み取ります。プロジェクトのこの段階では、入力ストリームを決定するのが難しいので、std::functionを使用します。代わりに。
using get_character = std::function; getcを返すintなどのCスタイルのストリーム関数のよく知られた規則を使用します。 charの代わりにまた、ファイルの終わりを示す負の数もあります。
ただし、トークナイザーでトークンタイプを想定する前に、事前に数文字を読み取ると非常に便利です。そのために、一部の文字を未読にするストリームを実装しました。
class push_back_stream { private: const get_character& _input; std::stack _stack; size_t _line_number; size_t _char_index; public: push_back_stream(const get_character& input); int operator()(); void push_back(int c); size_t line_number() const; size_t char_index() const; }; スペースを節約するために、実装の詳細は省略します。 GitHubページ 。
ご覧のとおり、push_back_stream get_characterから初期化されます関数。オーバーロードされたoperator()次の文字を取得するために使用され、push_backキャラクターをストリームに戻すために使用されます。 line_numberおよびchar_numberエラーレポートに使用される便利な方法です。
char_indexに注意してください現在の行の文字のインデックスではなく、全体です。そうしないと、push_backを実装するために、過去のすべての文字をいくつかのコンテナーに保持する必要があります。正しく機能します。
予約済みトークン
トークナイザーは、最下位レベルのコンパイラコンポーネントです。入力トークンと「スピットアウト」トークンを読み取る必要があります。私たちが関心を持っているトークンには4つのタイプがあります。
- 予約済みトークン
- 識別子
- 数字
- 文字列
コメントには関心がないため、トークナイザーは誰にも通知せずにコメントを「食べる」だけです。
株価からオプション価格を計算する方法
この言語の魅力と惑星での人気を確実にするために、よく知られているCのような構文を使用します。 C、C ++、JavaScript、Java、C＃、Objective-Cで非常にうまく機能したため、Storkでも機能する必要があります。復習コースが必要な場合は、以前の記事の1つを参照してください。 C / C ++学習リソース 。
予約済みトークンの列挙は次のとおりです。
enum struct reserved_token { inc, dec, add, sub, concat, mul, div, idiv, mod, bitwise_not, bitwise_and, bitwise_or, bitwise_xor, shiftl, shiftr, assign, add_assign, sub_assign, concat_assign, mul_assign, div_assign, idiv_assign, mod_assign, and_assign, or_assign, xor_assign, shiftl_assign, shiftr_assign, logical_not, logical_and, logical_or, eq, ne, lt, gt, le, ge, question, colon, comma, semicolon, open_round, close_round, open_curly, close_curly, open_square, close_square, kw_if, kw_else, kw_elif, kw_switch, kw_case, kw_default, kw_for, kw_while, kw_do, kw_break, kw_continue, kw_return, kw_var, kw_fun, kw_void, kw_number, kw_string, }; 「kw_」で始まる列挙型メンバーはキーワードです。それらは通常C ++キーワードと同じであるため、接頭辞を付ける必要がありました。接頭辞のないものは演算子です。
それらのほとんどすべてがC規則に従います。そうでないものは次のとおりです。
-concatおよびconcat_assign （..および..=）、これは連結に使用されます
-idivおよびidiv_assign （および=）、整数除算に使用されます
-kw_var変数宣言用
-kw_fun関数宣言用
-kw_number数値変数の場合
-kw_string文字列変数の場合
必要に応じてキーワードを追加します。
説明する価値のある新しいキーワードが1つあります：kw_elif。私は、単一ステートメントのブロック（中括弧なし）は価値がないと固く信じています。次の2つの場合を除いて、私はそれらを使用しません（そして、何かが欠けているとは感じません）。
for、while、またはifの直後に誤ってセミコロンを押したときブロックの前のステートメント。運が良ければ、コンパイル時エラーが返されますが、ダミーのifステートメントと常に実行されるブロックが返されることがあります。幸いなことに、私は何年にもわたって自分の過ちから学んだので、それはめったに起こりません。 パブロフの犬 最終的にも学びました。- ifステートメントを「連鎖」させた場合、ifブロック、1つ以上のelse-ifブロック、およびオプションでelseブロックがあります。技術的には、
else ifと書くと、それはelseです。そのifステートメントである1つのステートメントのみでブロックします。
したがって、elifブレースレスステートメントを完全に排除するために使用できます。それを許可するかどうかは、今待つことができる決定です。
予約済みトークンを返す2つのヘルパー関数があります。
std::optional get_keyword(std::string_view word); std::optional get_operator(push_back_stream& stream); 関数get_keyword渡された単語からオプションのキーワードを返します。その「単語」は、文字またはアンダースコアで始まる、文字、数字、およびアンダースコアのシーケンスです。 reserved_tokenを返します単語がキーワードの場合。それ以外の場合、トークナイザーはそれが識別子であると見なします。
関数get_operatorシーケンスが有効な演算子である限り、はできるだけ多くの文字を読み取ろうとしています。さらに読み取ると、認識された最長の演算子の後に読み取った余分な文字がすべて読み取られなくなります。
php7の下位互換性はありますか
これら2つの関数を効果的に実装するには、string_viewの間に2つのルックアップが必要です。およびreserved_keyword。
const lookup operator_token_map { {'++', reserved_token::inc}, {'--', reserved_token::dec}, {'+', reserved_token::add}, {'-', reserved_token::sub}, {'..', reserved_token::concat}, /*more exciting operators*/ }; const lookup keyword_token_map { {'if', reserved_token::kw_if}, {'else', reserved_token::kw_else}, {'elif', reserved_token::kw_elif}, {'switch', reserved_token::kw_switch}, {'case', reserved_token::kw_case}, {'default', reserved_token::kw_default}, {'for', reserved_token::kw_for}, {'while', reserved_token::kw_while}, {'do', reserved_token::kw_do}, {'break', reserved_token::kw_break}, {'continue', reserved_token::kw_continue}, {'return', reserved_token::kw_return}, {'var', reserved_token::kw_var}, {'fun', reserved_token::kw_fun}, {'void', reserved_token::kw_void}, {'number', reserved_token::kw_number}, {'string', reserved_token::kw_string} }; get_keyword実装は完全に簡単ですが、get_operatorの場合、n番目の文字のみを考慮して、特定の文字を候補演算子と比較するカスタムコンパレータが必要です。
class maximal_munch_comparator{ private: size_t _idx; public: maximal_munch_comparator(size_t idx) : _idx(idx) { } bool operator()(char l, char r) const { return l _idx && l これは、位置idxの文字だけを考慮に入れる通常の字句コンパレータですが、文字列が短い場合は、位置idxにヌル文字があるかのように扱います。これはどの文字よりも小さいです。他のキャラクター。
これはget_operatorの実装であり、maximal_munch_operatorを作成する必要があります。クラスクリア：
std::optional get_operator(push_back_stream& stream) { auto candidates = std::make_pair( operator_token_map.begin(), operator_token_map.end() ); std::optional ret; size_t match_size = 0; std::stack chars; for (size_t idx = 0; candidates.first != candidates.second; ++idx) { chars.push(stream()); candidates = std::equal_range( candidates.first, candidates.second, char(chars.top()), maximal_munch_comparator(idx) ); if ( candidates.first != candidates.second && candidates.first->first.size() == idx + 1 ) { match_size = idx + 1; ret = candidates.first->second; } } while (chars.size() > match_size) { stream.push_back(chars.top()); chars.pop(); } return ret; } 基本的に、最初はすべての演算子を候補として扱います。次に、文字ごとに読み取り、equal_rangeを呼び出して現在の候補をフィルタリングし、n番目の文字のみを比較します。前の文字はすでに比較されているため、比較する必要はありません。また、後続の文字はまだ無関係であるため、比較する必要はありません。
範囲が空でない場合は常に、範囲の最初の要素に文字がないかどうかを確認します（そのような要素が存在する場合、ルックアップがソートされると、常に範囲の先頭になります）。その場合、法的なオペレーターが一致します。そのような最も長い演算子は、私たちが返すものです。その後、最終的に読んだすべての文字を未読にします。
トークナイザー
トークンは異種であるため、トークンはstd::variantをラップする便利なクラスです。さまざまなトークンタイプ、つまり：
- 予約済みトークン
- 識別する
- 数
- ストリング
- ファイルの終わり
class token { private: using token_value = std::variant; token_value _value; size_t _line_number; size_t _char_index; public: token(token_value value, size_t line_number, size_t char_index); bool is_reserved_token() const; bool is_identifier() const; bool is_number() const; bool is_string() const; bool is_eof() const; reserved_token get_reserved_token() const; std::string_view get_identifier() const; double get_number() const; std::string_view get_string() const; size_t get_line_number() const; size_t get_char_index() const; }; identifier std::stringのメンバーが1人だけのクラスですタイプ。私の意見では、std::variantとして便利です。その選択肢のすべてが異なるタイプである場合、よりクリーンです。
これで、トークナイザーを作成できます。 push_back_streamを受け入れる1つの関数になります次のトークンを返します。
秘訣は、最初に読んだ文字の文字タイプに基づいて、さまざまなコードブランチを使用することです。
- ファイルの終わり文字を読み取ると、関数から戻ります。
- 空白を読み取る場合はスキップします。
- 英数字（文字、数字、またはアンダースコア）を読み取る場合、そのタイプの連続するすべての文字を読み取ります（最初の文字が数字の場合は、ドットも読み取ります）。次に、最初の文字が数字の場合、シーケンスを数値として解析しようとします。それ以外の場合は、
get_keywordを使用しますキーワードか識別子かをチェックする関数。 - 引用符を読み取る場合は、エスケープ文字をエスケープせずに文字列として扱います。
- スラッシュ文字（
/）を読み取ると、次の文字がスラッシュかアスタリスク（*）かを確認し、その場合は行/ブロックコメントをスキップします。 - それ以外の場合は、
get_operatorを使用します関数。
これがtokenize関数の実装です。呼び出している関数の実装の詳細は省略します。
token tokenize(push_back_stream& stream) { while (true) { size_t line_number = stream.line_number(); size_t char_index = stream.char_index(); int c = stream(); switch (get_character_type(c)) { case character_type::eof: return {eof(), line_number, char_index}; case character_type::space: continue; case character_type::alphanum: stream.push_back(c); return fetch_word(stream); case character_type::punct: switch (c) { case ''': return fetch_string(stream); case '/': { char c1 = stream(); switch(c1) { case '/': skip_line_comment(stream); continue; case '*': skip_block_comment(stream); continue; default: stream.push_back(c1); } } default: stream.push_back(c); return fetch_operator(stream); } break; } } } 下位レベルの関数を呼び出す前に、読み取った文字をプッシュバックすることがわかります。パフォーマンスの低下はほとんどなく、低レベルの関数コードははるかにクリーンです。
例外
例外に対する彼の怒りの1つで、私の兄はかつて言った：
「例外をスローする人と、例外をキャッチする必要がある人の2種類があります。私はいつもその悲しい第二のグループにいます。」
私はその声明の精神に同意します。私は特に例外が好きではありません。例外をスローすると、コードの保守と読み取りが非常に難しくなる可能性があります。ほとんどいつも。
モノのインターネットホームデバイス
私はそのルールに例外を設けることにしました（駄洒落が意図されていました）。コンパイラから例外をスローして、コンパイルの深さから解放するのは非常に便利です。
例外の実装は次のとおりです。
class error: public std::exception { private: std::string _message; size_t _line_number; size_t _char_index; public: error(std::string message, size_t line_number, size_t char_index) noexcept; const char* what() const noexcept override; size_t line_number() const noexcept; size_t char_index() const noexcept; }; ただし、トップレベルのコードですべての例外をキャッチすることを約束します。 line_numberも追加しましたおよびchar_indexプリティプリントのメンバー、およびそれを実行する関数：
void format_error( const error& err, get_character source, std::ostream& output ); まとめ
これで、シリーズの最初の部分は終わりです。それほどエキサイティングではなかったかもしれませんが、基本的な解析エラー処理に加えて、便利なトークナイザーが用意されています。どちらも、今後の記事で説明する興味深いものの重要な構成要素です。
この投稿からいくつかの良いアイデアが得られたことを願っています。詳細を調べたい場合は、 GitHubページ 。
基本を理解する
プログラミング言語はどのように書きますか？
コンパイルされたコードを実行できる言語文法とランタイムコンテキストを作成する。
プログラミング言語を作るものは何ですか？
その文法、構文規則、および最小の語彙単位（トークン）の意味的意味。
C ++のトークナイザーとは何ですか？
Tokenizerは、ストリームから文字を読み取り、結果としてC ++オブジェクトとして実装された最小の字句単位であるトークンを提供するコンポーネントです。
