最近 Crafting Interpreters という interpreter を作る本を読んでいて、とりあえず本通りにやって Lox という言語の tree-walk interpreter を作りました。作り終わって、この手の言語処理系を作る本では大抵ブロックを { } で表現するけれど Python のようにインデントでブロックを表現する言語の場合、Lexer, Parser はどう作ればよいのかなという疑問が生じました。また文末の ; もなくしてみたいと思い Lox interpreter の実装を元に自作言語に挑戦してみました。

元実装は Java 製でしたが私は Java でのテストの書き方をよく知らないので Go で書きなおしました。

ちなみに、Python のようにインデントでブロックを表現することを Off-side rule というらしいです。

Crafting Interpreters

作者:Nystrom, Robert
Genever Benning

Amazon

文法

とりあえずまずは完成形をば。作った言語の文法は以下のような感じです。Python 風味なのはインデントをブロックとして扱っているくらいで、あとはもとの Lox 言語を踏襲しています。 keyword も Python と同じにすればより Python 風になったと思いますが、あくまで　off-side rule の言語の処理系が作りたいのであって、Python 処理系を作りたいわけではなかったのでそこはあまりこだわりませんでした。

// declare variable
var x = 10; // terminal ';' is optional

var こんにちは = "Hello World"
print(こんにちは) // => Hello World

// if statement
if expr:
  statements
elseif expr:
  statements
else:
  statements

// while loop
while expr:
  statements

// for loop
for var i = 0; i < 5; i = i + 1:
  print(i)

// function
fun fib(n):
  if n <= 1:
    return n
  return fib(n-1) + fib(n-2)

// closure
fun makeCounter():
  var i = 0
  fun count():
    i = i + 1
    return i
  return count

var counter = makeCounter()
print(counter()) // => 1
print(counter()) // => 2

// class
// there is no class variable
class Hoge:
  pass

class Hoge:
  hoge(x, y):
    pass

class Hoge:
  init(x, y):
    this.x = x
    this.y = y

class Hoge:
  piyo(x, y):
    print(x + y)

var h = Hoge()
h.name = "hoge piyo" // instance variable can define anytime
print(h.name) // => hoge piyo

// inheritance
class A:
  method():
    return "a"

class B(A):
  method():
    return "b"
  methodA():
    return super.method()

class C(B):
  pass

print(C().methodA()) // => a

// include another file
include "another.tlps" // path is relative path from the file which describe include statement

// indentation can be used for if branch, loop body and function body
var x = 1
  var y = 1  // indentation error

インデントをブロックとして扱う

手始めに Python の挙動を調べてみました。今まで Python を書くときはスペース4つで表現してきたものの、2つでも書けるしこの辺の個数に何か制限はあるのかな？と。試してみるとスペースが1つだろうが3つだろうが深さのレベルさえ同じならば個数に依存しなさそうということがわかりました。スペース2個が { に対応するとかだったら話が簡単なのになと思っていたのですが的が外れました。

インデントをブロックとして扱う方法を自力では思いつかなかったので調べてみると以下の記事を見つけました。

lemniscus.hatenablog.com

行頭の空白の数の増減をスタックで管理しながら INDENT ({ に相当) だったり DEDENT (} に相当)を Token として生成すると。なるほど確かにその方法だと空白の数に制限をかけずに済みそうです。またこの方式から unindent does not match any outer indentation level という error は Lexer の時点で出すのが良さそうということもわかりました。

/tmp $ cat ex.py
def hoge():
    x = 1
  y = 2

/tmp $ python ex.py
  File "/tmp/ex.py", line 3
    y = 2
         ^
IndentationError: unindent does not match any outer indentation level

この情報から実際に実装してみたのがこの辺。Go の標準ライブラリには stack がなさそうだったので slice 使って自作しました。

https://github.com/goropikari/tlps/blob/423b76f03000e26273d74e52180f73b41fcce4cd/scanner.go#L232-L268

ブロックが使えるところに制限をかける

Python の場合、下記のプログラムの例のようにブロックを使える部分には制限があります。

/tmp $ cat ex.py
x = 1
  y = 2

/tmp $ python ex.py
  File "/tmp/ex.py", line 2
    y = 2
IndentationError: unexpected indent

Python の言語仕様を参考に自作言語では if や def のように : を使うものはブロックとして NEWLINE INDENT statements DEDENT を使うという制限をかけました。

block:
    | NEWLINE INDENT statements DEDENT 
    | simple_stmt

Python のブロック 10. Full Grammar specification — Python 3.9.7 documentation

また、ブロックを parse するときは for のブロックなのか if のブロックなのかということを区別するタグをつけるようにしました。ブロックが許されていないところでブロックが作られた場合は None というタグをつけました。そして interpreter がそのブロックオブジェクトを評価するときに None ならばエラーで落とすという仕様にしました。interpreter の処理を書いている途中で評価するときでなく parse 時点でエラーで落としてよかったなと思いましたが、まぁいいかととりあえずそのままにしました。

tlps/parser.go at 423b76f03000e26273d74e52180f73b41fcce4cd · goropikari/tlps · GitHub

ブロックを使うところに制限をかけてみると if, else に加えて elif のようなものもないと、if 文がネストの深い書き方になってしまうことに気付きました。

if (aaa) {
  xxx
} else if (bbb) {
  yyy
} else if (ccc) {
  zzz
}

: のあとにはブロックがくるとしたせいで、{} を使った↑と等価なことをしたい場合、↓のような書き方を強いることになってしまいました。 elif のような keyword を追加するか、else if xxx: のような書き方を許し else のあとに : がくるか if が来るかを判定する方法の2種類が考えられましたが、いろいろな言語が elif のような keyword を持っているのでそちらに合わせました。(Julia が好きなので elseif にしましたが)

if aaa:
  xxx
else:
    if bbb:
      yyy
    else:
      if ccc:
        zzz

文末の `;` をなくす

元々の Lox 言語は print 123; のように文末を ; で終えるようになっていたのでこれを省略できるようにしてみました。簡単のために文は複数行にはならないと言う制限をかけ、; の代わりに \n を文の区切りとして使うことにしました。元々の Lox 言語はスペースや \n といったいわゆる空白文字はすべて無視する仕様だったのでまずは \n を意味のある文字として Token にすることにしました。

ただ全ての \n を意味のあるものとする必要はなく、空白行の \n (コメントだけの行も含めて)は無視していいというか残したままだと parser 側の処理が面倒になりそうだったので無視するようにしました。

文末の ; を省略するのはこの程度の対応で実現することができました。

tlps/scanner.go at 423b76f03000e26273d74e52180f73b41fcce4cd · goropikari/tlps · GitHub