プログラミング言語を作るの2章を読み進めた記録。興味があったけど手を出せずにいた自作プログラミング言語ですが、この記事を読んでまあつべこべ言わず手を動かそうと決心して、コードを書き始めた。成果物はここにあります。

処理系のうごき

プログラミング言語の処理系は通常以下のような流れで動く

  1. 字句解析: ソースコードをトークンの並びに分割する。字句解析を行うプログラムのことをレキシカルアナライザと呼ぶ。
  2. 構文解析: トークンの並びから抽象構文木を構築する。構文解析を行うプログラムのことをパーサと呼ぶ。
  3. 意味解析: 抽象構文木に対して、データ型などの意味的な解釈を行う。
  4. コード生成: 機械語やバイトコードなどを吐き出す

電卓プログラムの字句解析

lex というレキシカルアナライザを自動生成してくれるツールを使う。UNIX系のOSであれば最初から入っていることが多い。定義には正規表現を使う。

電卓プログラムの構文解析

yacc というパーサを自動生成してくれるツールを使う。

構文規則だけを抜き出すと以下のような感じ?

動かす

Makefile を書いた

以下のような感じ

コマンドラインから、温かみのある手動ビルドをしたいときは以下のような具合

shift と reduce

パーサーのうごきをちゃんと押さえておく。1 + 2 * 3 という入力があったときの動きは以下の通り。

  1. 1 (shift) next: AND
  2. primary_expression (reduce) next: AND
  3. term (reduce) next: AND
  4. expression (reduce) next: AND
  5. expression AND (shift) next: 2
  6. expression AND 2 (shift) next: MUL
  7. expression AND primary_expression (reduce) next: MUL
  8. expression AND term (reduce) next: MUL
  9. expression AND term MUL (shift) next 3
  10. expression AND term MUL 3 (shift) next CR
  11. expression AND term MUL primary_expression (reduce) next CR
  12. expression AND term (reduce) next CR
  13. expression (reduce) next CR
  14. expression CR (shift)
  15. line (reduce)
  16. line_list (reduce)

スタックの動き

  • 2 * 3 を reduce する際は、 term := term MUL primary_expression { $$ = $1 * $3; } の規則に従う
  • $1 = 2, $2 = *, $3 = 3 として、 新しい term には $$ = 2 * 3 が格納される
  • {} を書かなかった場合は $$ = $1 が補われる
  • つまり 1 => primary_expression($$ = 1) => term($$ = 1) => expression($$ = 1) みたいな感じになっている