mini-typescriptコンパイラを読む〜パーサ編〜
https://gyazo.com/a0decfcf884310069398836507fcd66d https://twitter.com/sanders_n/status/1401937771724345344?s=20
↑ 作者のtweet
はじめに
あくまでこれは学習用のリポジトリで、コンパイラとしてできることはとっっっても限られている
作者もREADEMEに書いている
A miniature model of the Typescript compiler, intended to teach the structure of the real Typescript compiler
その分シンプルなのでコンパイラがどういう動作でパースしてASTを作っているのか理解できる
このページでの目標
書いていたら長くなったので「パーサ編」(このページ)と「型チェック/トランスパイル編」で分けることにした
ここでの目標は「tsファイルをパースしてASTを得るところまでの処理を理解すること」
コードリーディング
というわけで早速読んでいく
index.ts
起点であるのindex.tsから読んでいく
code:index.ts
import fs = require('fs')
import { compile } from './compile'
// print errors, write js to file
console.log(errors)
fs.writeFileSync(process.argv1 + '.js', js) 見ての通りやっていることは単純で
1. compileをimport
2. compileに読み込んだtsファイルのテキストを渡す
3. 2で帰ってきたerrorを出しつつ トランスパイルされたjsファイルを書き出し
なのでメインの処理は compile.tsにあることがわかる
compile.ts
compile.tsもやっていることは少ない
code:compile.ts
import { Error, Module } from "./types"
import { errors } from './error'
import { lex } from "./lex"
import { parse } from "./parse"
import { bind } from "./bind"
import { check } from "./check"
import { transform } from "./transform"
import { emit } from "./emit"
export function compile(s: string): [Module, Error[], string] {
errors.clear()
const tree = parse(lex(s))
bind(tree)
check(tree)
const js = emit(transform(tree.statements))
}
パースのメインとなる処理は
code:compile_core.ts
const tree = parse(lex(s)
の部分でもらった文字列をlexという関数に渡し、その戻り値をさらにparseに渡すことでtree=ASTを得ている その後はcheckなどで構文チェックをしている
errorsはシングルトンなMapになっておりcheck関数やbind関数でエラーが追加される仕組みなっている
その後作成されたASTから型アノテーションなどを削除しjsファイルとしてトランスパイルした上で、AST/エラー/js文字列を返す
jsに変換しているところは一旦おいて(後述する)、最初にtsファイルの文字列が渡されるlex.tsを見ていく
lex.tsの全体像
ここから本格的にパーサっぽい処理に入ってくる
lex.tsではlex関数とlexAll関数が定義されているがlexAll関数はtestでしか利用されてないので一旦置いておく
lex関数は以下のような実装になっている
code:lex_about.ts
export function lex(s: string): Lexer {
let pos = 0
let text = ""
let token = Token.BOF
return {
scan,
token: () => token,
pos: () => pos,
text: () => text,
}
function scan() {
/* 略 */
}
function scanForward(pred: (x: string) => boolean) {
/* 略 */
}
}
lex関数は内部で pos, text, tokenという状態を保持し、それぞれの情報を取得するための関数を提供する
このpos, text, tokenにはそれぞれ以下のような情報が記録されている
pos : 今読み込んでいる場所の位置情報
全体の何文字目かで記録している
text : 直近で読み込んだ部分の文字列
var test = 10;とかならvarとかtest、=みたいに意味で分割されてテキストとして入る
token : 直近で読み込んだ部分がどんな意味を持つかの情報
変数名なのか演算子なのかkeywordなのか、はたまた数値なのか......etc
またscan関数を呼び出すことで意味のある一かたまりごとに読み進め、pos, text, tokenの中身を更新していく
そのためのutil関数のとしてscanForward関数が切り出されている
lex.tsのscan関数及びscanForward関数
lex関数の全体像を掴んだところでscan関数及びscanForward関数の中身を見てみる
上記の通りscanForward関数はscan関数で読み進めていくためのユーティリティ関数のようなものなので先にscanForward関数を見ていく
scanForward関数
code:scan_forward.ts
function scanForward(pred: (x: string) => boolean) {
while (pos < s.length && pred(s.charAt(pos))) pos++;
}
と言ってもやっていることはこれだけ
scanForward関数には1文字を評価するなんらかの関数が引数として与えられる
pred(s.charAt(pos))としているのでxに来るのは一文字である
そして引数で渡した関数がtrueを返す間posの値をインクリメントし続けている
つまり単に指定した種類の文字が続いている間はポジションのカウンタ(=pos)を進めるだけである
scan関数
次にメインであるscan関数を見ていくscan関数は上記の通り「意味のある一かたまりごとに読み進め、pos, text, tokenの中身を更新していく」という動作をする
code:scan.ts
function scan() {
scanForward(c => / \t\b\n/.test(c)) const start = pos
if (pos === s.length) {
token = Token.EOF
}
else if (/0-9/.test(s.charAt(pos))) { scanForward(c => /0-9/.test(c)) text = s.slice(start, pos)
token = Token.Literal
}
else if (/_a-zA-Z/.test(s.charAt(pos))) { text = s.slice(start, pos)
}
else {
pos++
switch (s.charAt(pos - 1)) {
case '=': token = Token.Equals; break
case ';': token = Token.Semicolon; break
case ":": token = Token.Colon; break
default: token = Token.Unknown; break
}
}
}
まずは最初の2行では
code:scanL2_L3.ts
scanForward(c => / \t\b\n/.test(c)) const start = pos
scanForward(c => /[ \t\b\n]/.test(c))で空白/タブ/改行などがあったらその終わりまでposを進めている
これによってvarと変数名の間のスペースなどを解釈できるようになっている
空白/タブ/改行が終わるところまでposが進んだらその時点でのposの値をstartとして保存する
この場所から先はなんらかの文字列が来るはずであるため開始位置を記録しておく
ここから先の処理は現在地の直後に来る文字列によって分岐している
code:scanL4_L6.ts
if (pos === s.length) {
token = Token.EOF
}
最初の分岐ではファイルの最後まで到達したのかの判断をしている
到達した場合はtokenをToken.EOFとする
ちなみにtokenにはTokenとしてenumで定義されたものが入る(詳しくはtype.tsを参照のこと)
code:scanL7_L11.ts
else if (/0-9/.test(s.charAt(pos))) { scanForward(c => /0-9/.test(c)) text = s.slice(start, pos)
token = Token.Literal
}
次の分岐は現在のposの直後に数字が来た場合の分岐である
JSでは数字始まりの変数名やkeywordは許されていないので空白/タブ/改行直後で数字が来た時点で数値と判断できる
そのためscanForward(c => /[0-9]/.test(c))で数字が続く限りposを進める
その上で先程記録したstartから現在のposまで(つまり数字が続いている部分)をtextとして切り出す
さらにtokenをToken.Literalに設定する
code:scanL11_L15.ts
else if (/_a-zA-Z/.test(s.charAt(pos))) { text = s.slice(start, pos)
}
次の分岐は現在のposの直後に「a-zの文字または_」、つまり記号として予約されていない文字が来た場合の分岐である
この場合変数名やなんらかのkeyword(varとかfunctionとか)であることが考えられる
そのため数値の時と同様scanForward(c => /[_a-zA-Z0-9]/.test(c))で_a-zA-Z0-9が続く限りposを進め、その間のtextを保存する
※ ここでは一文字目が_a-zA-Zのどれかと保証されているのでそれ以降は数字が続くことも許されている
ここはtokenの指定が少し複雑で
切り出したtextがkeywordsのどれかに一致する : そのkeywordで宣言されたTokenを指定
それ以外 : Token.Identifierを指定
となっている。ここでいうkeywordsは
code:keywords.ts
const keywords = {
function: Token.Function,
var: Token.Var,
return: Token.Return,
};
となっており、つまりは切り出したtextがfunction, var, returnだったら専用のTokenを指定するという処理になっている。
code:scanL15_L23.ts
else {
pos++
switch (s.charAt(pos - 1)) {
case '=': token = Token.Equals; break
case ';': token = Token.Semicolon; break
case ":": token = Token.Colon; break
default: token = Token.Unknown; break
}
}
最後の分岐は現在のposの直後に記号が来た場合の処理である
最初でposをインクリメントしているのは記号は1文字に限定するという原則に立っているからだと考えられる
||や??など記号が連続する記法もあるので 少し雑な気もするがサポート外ということで
あとは記号の種類によって専用のtokenを設定し、該当しないものはToken.Unknown を設定している
lex.tsまとめ
lex.tsでは
pos, text, tokenという3つの情報を内部でもち、その情報を読む関数を提供する
scan関数を呼び出すことで意味のあるひとかたまりごとに読み進め、pos, text, tokenの中身を読んだ内容に応じて更新する
というようなことを行なっている。
次に読んでいくparse関数ではこのlex関数が提供する関数群(pos(), text(), token(),scan())を利用してASTを生成しているので、これらの挙動を理解しておくと読むのが楽になる parse.tsの起点
parse関数の全体はとても大まかに以下のようになっている
code:parse.ts
export function parse(lexer: Lexer): Module {
lexer.scan()
return parseModule()
function parseModule(): Module {
// 略
}
// その他関数も略
}
処理を追うとやっていることは大きく分けて以下の2つである
1. 1回lexer.scan()を呼ぶ (lexerは先程解説したlex関数が渡される)
2. parseModule()の返り値を返す
lex.tsで解説したとおり、1. を行うことでlex関数の内部ではコードがひとかたまり分読み進められ、読み進めた部分の情報が記録される
→ つまり最初1ブロック(意味のかたまりの単位)の読み込みを行っていると考えて良い
その上で 2. を実行することでASTを生成している。
よってファイルの中身を読み進めてASTを生成するのはparseModule関数である事がわかる
そこでparseModuleを見てみると
code:parseModule.ts
function parseModule(): Module {
const statements = parseSeparated(parseStatement, () => tryParseToken(Token.Semicolon))
parseExpected(Token.EOF)
return { statements, locals: new Map() }
}
parseModuleでは以下のことを行っている
1. parseSeparated, parseStatement, tryParseToken関数たちを利用してファイルを読み進めAST(statements)を得る
2. (この時点でファイルの最後まで読み終えたはずなので)最後にlex関数内でEOFトークンがセットされているか確認する
lex関数のscan関数、最初の分岐で終端だった場合はToken.EOFを設定する処理があった
もしこの時点でToken.EOFになっていなかったら1. の処理がうまく行ってないことになるのでerrorをセットする
詳しい仕組みはparseExpected関数の仕組み部分で見ていく
3. 最後に生成した ASTとlocalsという名の空のMapを返す
つまりファイルを読み進めASTを得る処理は
const statements = parseSeparated(parseStatement, () => tryParseToken(Token.Semicolon))
に集約されていることがわかる
ということで parseSeparated, parseStatement, tryParseToken関数たちを読んでいく
....と言いたいところだがその前にparse関数内各所でユーティリティ的に使われている関数たちの挙動を確認する
parse関数内のutil関数たち
parse関数内には以下の3つの関数が定義されており、parse関数内各所で利用されている
parseToken関数
tryParseToken関数
parseExpected関数
これらの挙動を理解すると本題に入りやすくなるので説明する
code:parseToken.ts
function parseToken() {
const t = lexer.token()
lexer.scan()
return t
}
まずはparseToken関数
この関数はご覧の通り
現在lex関数に記録されているtokenの情報を読み出し
lex関数での読込位置を進める
読みだしたtoken情報を返す
という処理をしている。
やっていることは単純だが、「すでに読み込んであるToken情報を読み、lex関数の読込位置を先に進めておく」という挙動であることに注意する
要は 「位置を進める→読む」 ではなく 「読む→位置を進める」の順であるということ
parse関数の最初でlex関数のscan()を呼び出しているもの先に読み込んでおく方式であるからと言える
code:tryParseToken.ts
function tryParseToken(token: Token) {
if (lexer.token() === token) {
lexer.scan()
return true
}
else {
return false
}
}
次にtryParseToken関数
この関数はtoken情報を引数に受け取り、そのtokenと現在読み込まれたtokenが一致するかをboolで返す関数である
この関数では引数に受け取ったtokenと現在読み込まれたtokenが一致する場合のみ読み込み位置を先に進める
code:parseExpected.ts
function parseExpected(expected: Token) {
const pos = lexer.pos()
const actual = parseToken()
if (actual !== expected) {
error(pos, parseToken: Expected ${Token[expected]} but got ${Token[actual]})
}
return actual === expected
}
最後にparseExpected関数
この関数もtoken情報を引数に受け取り、そのtokenと現在読み込まれたtokenが一致するかを返している点でtryParseToken関数とにているが、以下の2点で大きく異る
単にboolを返すだけでなく、errorを登録している点
引数に受け取ったtokenと現在読み込まれたtokenが一致するかどうかにかかわらず読み込みを先に進める点
errorの登録についてはerrors.tsを見るとわかる
code:errors.ts
import { Error } from './types'
export const errors: Map<number,Error> = new Map()
export function error(pos: number, message: string) {
if (!errors.has(pos)) {
errors.set(pos, { pos, message })
}
}
このようにErrorをシングルトンなMapとしてexportし、error関数によってポジションとエラーメッセージを記録している。
以降の処理では基本的にこの3つの関数を利用してコードを読み進めている
センテンスごとの分割
先述した通り、parase関数でメイン処理(ASTを生成しているところ)は8行目の
const statements = parseSeparated(parseStatement, () => tryParseToken(Token.Semicolon))
部分である。
まずはparseSeparated関数を見ていく
code:parseSeparated.ts
function parseSeparated<T>(element: () => T, separator: () => unknown) {
while (separator()) {
list.push(element())
}
return list
}
parseSeparated関数
parseSeparated関数は第2引数でもらった関数がtrueを返し続ける限り第1引数を呼び出し、その中身を配列に詰めるという動作を行なっている。
ここで、呼び出し元と共に鑑みると第1引数と第2引数はそれぞれ
第1引数 : 各文のASTを生成する関数
第2引数 : セミコロンが来たかどうかの判定を行う関数
tryParseToken関数は「引数に指定したtokenと現在読み込まれたtokenが一致するかを返す関数」であり、今回は呼び出し元でToken.Semicolonを渡しているため
となる
つまりセミコロンごと=各文でASTを生成し、配列化をしている
よって各文のparseをしているのはparseSeparated関数の第1引数=parseStatementということになる
各文のパース処理
parseStatement関数を見ていく
code:parseStatement.ts
function parseStatement(): Statement {
const pos = lexer.pos()
if (tryParseToken(Token.Var)) {
const name = parseIdentifier()
const typename = tryParseToken(Token.Colon) ? parseIdentifier() : undefined
parseExpected(Token.Equals)
const init = parseExpression()
return { kind: Node.Var, name, typename, init, pos }
}
else {
return { kind: Node.ExpressionStatement, expr: parseExpression(), pos }
}
}
parseStatement関数はこのような処理になっており、
最初にこの関数が呼ばれた時点での読み込み位置を記録している。
次に 読み込んだ部分のTokenが「1. Varであった場合」と 「2.それ以外」 で場合分けを行なっている。
1. の場合
parseIdentifier関数を呼び出す。
code:parseIdentifer.ts
function parseIdentifier(): Identifier {
const pos = lexer.pos()
let text = lexer.text()
if (!parseExpected(Token.Identifier)) {
text = "(missing)"
}
return { kind: Node.Identifier, text, pos }
}
parseIdentifierでは現在の読み込み位置と読み込んだテキストを保持している
この時点でlex関数のtext、つまりここでのtextには varに続くワードが入っていることに注意する
上のif (tryParseToken(Token.Var))の時点で「tryParseToken(Token.Var)がtrueを返している」 = 「読み込み位置はvarの次に進められている」からである
ピンと来ない場合はtryParseTokenの説明を参照されたし
もしも現在読み込んだ部分(varの直後)がToken.Identifierでない場合は正しく変数が宣言されてないことになるのでtextは"(missing)"とする。
ここでもparseExpectedを呼んでいるので、読み込み位置は変数名の次まで進んでいる
ピンと来ない場合はparseExpectedの説明を参照されたし
その上で{ kind: Node.Identifier, text, pos }というオブジェクトを返している
これはASTのうち、変数部分の情報を返している
JSのASTに触れたことがある方はIdentifierのNodeと言えばわかると思う
このオブジェクトはname変数に記録される
parseStatement関数に戻ると次はconst typename = tryParseToken(Token.Colon) ? parseIdentifier() : undefinedとなっている
これは変数宣言をした後に:があるか、つまり型の宣言がされているかを判別している
:がある場合は次に型名がくるはずなのでもう一度parseIdentifierを呼びtypeNameとする
ない場合はtypeNameはundefinedとする
さらにparseExpected(Token.Equals)では =がくることを確認し、来ない場合はエラーを登録している
なので var a,b = 0みたいな記法はこのparserではまだ許されていない
この時点で読み込み位置は=の次まで進んでいる
最後にconst init = parseExpression()でparseExpressionの返り値をinitに記録する
その上で{ kind: Node.Var, name, typename, init, pos }というオブジェクトを返している
ここでこのオブジェクトの中身を整理すると
code:returnValueOfParseStatement.ts
{
kind: Node.Var, // このNode(ASTの一部分)の種類。今回ならvarによる変数宣言部分であるという意味
name, // 変数名についての情報
typename, // 型名についての情報(numberとかstringとか)
init, // 初期値についての情報。つまり = の右辺について
pos // node自体のスタート位置
}
となる
2. の場合
この場合は単純で純粋に{ kind: Node.ExpressionStatement, expr: parseExpression(), pos }を返している
kindではExpressionStatementと呼ばれるタイプのNodeであるとしている
これもJSのASTで用いられるNodeのタイプで式の文全体を示している
その上で exprにはparseExpressionの返り値を渡している
つまり式の構造解釈自体はparseExpressionに任せている
parseExpression関数による式のParse
parseStatement関数ではparseした一文が変数宣言であった場合のinitに、そうでない場合はexprにparseExpression関数の返り値を指定していた。
よって名前の通りparseExpression関数は変数宣言の右辺や一般的な代入などの式をparseする関数である
code:parseExpression.ts
function parseExpression(): Expression {
const pos = lexer.pos()
const t = parseToken()
switch (t) {
case Token.Identifier:
const name = { kind: Node.Identifier, text: lexer.text(), pos } as const
if (tryParseToken(Token.Equals)) {
return { kind: Node.Assignment, name, value: parseExpression(), pos }
}
else {
return name
}
case Token.Literal:
return { kind: Node.Literal, value: +lexer.text(), pos }
default:
error(pos, "Expected identifier or literal but got " + Tokent) return { kind: Node.Identifier, text: "(missing)", pos }
}
}
parseExpression関数を見ていく
最初の行はもはや恒例、読み初めの位置の記録である
次の行では現在のtokneの情報を取得している
と同時にその後読み込み位置を先に進めている
以降は取得したtokenをもとに分岐している
case1 : tokenがIndentifier、 つまり何らかの変数名や関数名などであった場合
この場合はname変数として{ kind: Node.Identifier, text: lexer.text(), pos }、つまり変数自体の情報(名前,位置など)を記録する
その上で次のtokenが=だった場合、
{ kind: Node.Assignment, name, value: parseExpression(), pos }
を返している。
これはそれぞれ以下のような意味になる
code:returnValueOfPECase1.ts
{
kind: Node.Assignment, // 代入の式であることを記録 変数宣言の場合parseStatementで捕まるのでここには来ない
name, // 左辺の変数の情報としてnameを指定
value: parseExpression(), // 右辺をさらにparaseする
pos // 読み込み位置
}
ここでは以下の点に注意したい
kind: Node.Assignment なのは変数宣言の場合parseStatementで最初の分岐に捕まりここには来ないため
純粋な変数への代入であると解釈できる
valueでparseExpression()を呼ぶことで再帰的にASTを生成している
これは var a = b = c = 1みたいな記法を解釈するため=が続く限りparaseする必要があるためである
case2 : tokenがLiteral、つまり数字だった場合
この場合は返すオブジェクトは以下のようになる
code:returnValueOfPECase2.ts
{
kind: Node.Literal, // 数字であることを記録
value: +lexer.text(), // 値は数値に変換
pos // 読み込み位置
}
case3 : case1,2以外
現在時点ではこの部分にはIdentiferあるいはLiteralのtokenが来るはずなのでこのケースに入った場合は(このパーサにおいては)構文エラーとなる
よってエラーを登録し以下の情報を返す
code:returnValueOfPECase3.ts
{
kind: Node.Identifier, // 種類は一応Identifierであるとする
text: "(missing)", // textはないのでmissing
pos // 読み込み位置
}
これがparseExpression関数の処理である
parse.tsまとめ
parse.tsでは以下のようにしてASTを得ている
parseModule関数で;ごとに文を分割し、各文の文字列に対してparseStatement関数を実行
その結果を文ごとのASTの配列にして返す
parseStatement関数では変数宣言かそれ以外かを判別する
変数宣言の場合は変数名や型情報など=の手前部分までparseし右辺のparseはparseExpression関数に任せる
変数宣言でない場合は丸々parseExpressionに任せる
parseExpression関数では読み込んだ部分のtokenの応じてASTのnodeを生成し返す末端の処理を行なっている
変数名などが来る場合は=が終わるまで再帰的にparseExpressionを呼び出したうえで変数の情報Nodeを返す
数値の場合は数値としてのNodeを返す
それ以外ならエラーを登録する
このようにしてASTが生成されている
最後に
とても長くなってしまったがこれでパース部分の処理は終わりとなる
なるべく丁寧に書いたつもりなので一通り読めばこのコンパイラのパース処理については理解していただけるのではと思う
またここまで読んだ方には分かると思うがまだこの時点ではTS/JSの殆どの構文は正しくparseできない
作者の意図するように、少しずつ自分でパース可能な構文を増やしていくことでより学習が進むはず
次回は型チェック及びJS化の処理を読んでいくが、その後は構文の追加なども行なっていきたい
次回
参考
名称の確認などで何度も参考にさせていただいた
ASTについての基本的な知識を得る上でとても良い資料であると思う