Explore cs in depth!

情報系の専門学校生.compiler/assembler/linker/loader/os/any lowlevel implementations

Rustで有限オートマトンを書いてAtcoder Beginner ContestのA問題を解いてみる

概要

お久しぶりです.
最近は Peachili というコンパイラドライバの実装や,
今までやってこなかった大学数学の勉強,
アルゴリズムやデータ構造を含むCSの基礎知識を1から勉強し直しているという感じで,
あまり記事を書けていませんでした.
Goコンパイラを書く記事シリーズは何処へ

とても短い+ネタ記事になってしまいますが,
最近 計算理論正規言語 らへんの勉強もやり始めたので,
それに関連した知識としてオートマトンを取り上げ,
競プロの問題をオートマトンを用いて解いてみようと思います.

私はコンパイラ自作のとき毎回手書きでTokenizerを書いているのですが,
自分で作った字句解析器生成系を使って簡略化したいなあと思っているので,
正規言語・表現周辺の知識を身につけるモチベが上がってきているのです.

Rust言語で字句解析器生成系を実装し,
クレートとして公開しようと思っているので,その時は利用していただけるとありがたいです.

本記事の内容としては,
以下の本を参考にしています.

再度述べておきますが,
この記事はあくまでもネタ記事であり,
有限オートマトンを含む計算理論を体系的に解説する記事ではありません.

オートマトンを使って遊んだんだな」 くらいの認識で見ていただければ.

続きを読む

Go1.13.8を読む#2 ~コンパイラのフロントエンド部まとめ~

  • 概要
    • go tool compile
    • コンパイラのフロントエンド部
      • archInit
      • 字句解析,構文解析
      • 意味解析1,外部依存の無い型とメソッドの解析
      • 意味解析2,変数代入の解析
      • 意味解析3,手続き本体の型検査
      • 意味解析4,キャプチャ変数解析
  • まとめ

概要

お久しぶりです.

とある事情でGoコンパイラの実装を詳細に理解する必要があるため,
コードリーディングを行うことにしました.

いくつかの記事に分けてGoコンパイラソースコードを読んでいく,
その第二回です.

前回, go コマンドの挙動を簡単に理解し,
go build と実行されたとき最終的に go tool compile が実行されていることを理解しました.
これはプロジェクトの依存関係が整理された状態で,
外部依存の無いパッケージから随時コンパイルされる,という感じになっていました.

今回はこの go tool compile コマンドを追っていきながら,
コンパイル処理全体の大まかな理解を目指します.
(実際にはこの記事ではフロントエンド部までの概観しかできませんでした.)

  • 字句解析はいつ行われている?
  • 意味解析のタイミングは?
  • IRはどこで生成される?

などなどが把握できることを目標にします.
繰り返しますが 各フェーズの処理は"詳細に追いません".
それは次回以降やっていきます.

なお,今回のソースコードはすべて こちら を参照しています.
バージョンはv1.13.8 です.
引用するコードもすべてこのバージョンです.

続きを読む

Go1.13.8を読む#1 ~コンパイルまでの流れ~

  • 概要
    • go コマンドのメイン処理
      • コマンドライン引数のパース
      • $GOPATHのチェック
      • 実行環境の設定
      • コマンド実行ループ
    • go build の挙動
      • Builder の初期化
        • BuildInit
      • 入力ソースの解決
    • 実際のコンパイル処理まで
      • Builder.Do()
      • Builder.build()
  • まとめ

概要

お久しぶりです.

とある事情でGoコンパイラの実装を詳細に理解する必要があるため,
コードリーディングを行うことにしました.

以前Lexerのコードを読んだことがありますが,
あのときはコンパイラの知識も不足していたし,特に目的もなかったために続きませんでした.

いくつかの記事に分けてGoコンパイラソースコードを読んでいく,
その第一回です.

今回は go コマンド処理の全体を概観し,
次回以降コンパイル処理を詳細に追うことにします.
後述しますが, go コマンドは非常に多くの機能をシングルバイナリで実現していて,
それ自体が巨大なCLI のようになっています.
まずはその全体感を把握しつつ,
次回以降一番の目的であるコンパイラの挙動を大まかに把握することにしましょう.

なお,今回のソースコードはすべて こちら を参照しています.
バージョンはv1.13.8 です.
引用するコードもすべてこのバージョンです.

続きを読む

SecHack365'19に参加し,実行プログラム基盤のスクラッチ実装をした

概要

以前,このような記事を書きました.

drumato.hatenablog.com

実はこのDepthの開発活動はSecHack365という 人材育成プロジェクト に参加した中で作成した成果物であり,
またその成果物のうちごく一部を簡単に取り上げたもの,になります.
今回はSecHack365という活動がどういうものかをシェアしていけたらな,と思っています.

本記事は以下のようにして構成されています.

  • 概要
  • SecHack365の活動を振り返る
    • Sechack365とは
    • 参加の動機
      • 応募時点でやりたかったこと
      • 応募したコース
      • 最終的に達成したこと
    • 各集合回のまとめ
      • 応募時点~神奈川回
      • 北海道回まで
      • 福岡回まで
      • 宮城回まで
      • 愛媛回まで
      • 沖縄回まで
    • 全体を通して
  • 付加学習・SecHack365以外の活動
  • まとめ
続きを読む

実行プログラム作成基盤をフルスクラッチで書いた

  • 概要
  • 自己紹介
  • 本題
    • Motivation
      • motivationまとめ
    • 実装の歴史
    • 今できること
    • 困ったこと
      • ELFに蔓延るNULL三姉妹
      • そもそもやっている人がいない
  • まとめ

概要

この記事は 言語実装 Advent Calendar 2019 の8日目です.

言語処理系の理論,自作言語の実装については既に他の方が記事を出してくださると思うので,
私は 実行可能なプログラム に変換する部分を主軸に置きながら自作言語のお話をさせていただければと思います.

実装自体は以下のリンクに置いてあります.

github.com

続きを読む

glibcラッパーからLinuxのシステムコールハンドラまでを読む,まとめる

概要

IPFactory Advent Calendar 2019 一日目.
急遽開いた弊サークルのカレンダー,既に一日目が終わろうとしている.

私は日頃から勉強した内容をMarkdownにまとめ,
Gitリポジトリに保存するようにしている.

ここではそのリポジトリから,
Linuxにおけるシステムコールの流れのメモを取り出して紹介しよう.

誰も投稿しないよりよっぽどマシだし,
おそらく誰かの何かになれると思う.

要は急にやることになったので何もなかった.

続きを読む

ELFバイナリに含まれるnullセクション/ヘッダの真実…?

概要

gccの吐くELFバイナリを見てみると、セクションヘッダテーブルの先頭に NULLヘッダ を見つけます。
これってなんだろう? ってずっと疑問だったのですが、今日理由がわかったのでそれについて述べたいと思います。

厳密には、 nullセクション も含まれています。
サイズが0のセクション と、それに対応する 全てのメンバが0のヘッダ が存在します。
また本記事で取り上げるnullセクション/ヘッダの意味は私がなんとなくそうじゃね?と思ったもので、
もっと歴史的な経緯、重要な意味が含まれているかも知れません。
その場合は教えて下さい。

続きを読む