14文字と5つの単語
交通費を計算するスクリプトに、fare * 2 + 300 という行があります。人が読めば、5つの単語です。コンパイラにとっては、空白を含めて14個の文字が並んでいるだけです。
文法を調べる前に、文字を単語にまとめ、空白を捨てる部分が要ります。小さくて速い部分ですが、細かい誤りが起きやすいところです。
このレッスンのゴール
メモ
ソースコードの文字をトークンに分けられる。
重要な言葉
| ことば | いみ | れい |
|---|---|---|
| トークン | プログラムの1語と、その種類の組 | NUMBER 300 |
| 字句解析器 | トークンを作る、コンパイラの部分。レキサーとも言う | |
| パターン | ある種類のトークンの形を決める規則 | [0-9]+ |
| 最長一致 | パターンに合う限り、文字を長く取る決まり | |
| キーワード | 言語が自分のために取っておく単語 | if |
| 字句解析器の生成系 | パターンから字句解析器を書く道具 | flex |
学生が入力するセルは、このプレビューでは空白です。
トークンは種類と文字列の組
字句解析器は、コンパイラ本体の最初の部分です。文字を左から読み、トークンを1つずつ渡します。
トークンには、NUMBER や NAME のような種類と、もとの文字列があります。空白とコメントは、トークンになりません。1つのトークンの終わりと、次の始まりを分けるだけです。
例: fare * 2 + 300
| 文字 | 種類 | 文字列 |
|---|---|---|
| f a r e | NAME | fare |
| * | OP | * |
| 2 | NUMBER | 2 |
| + | OP | + |
| 3 0 0 | NUMBER | 300 |
| 4つの空白 | トークンなし | 捨てる |
学生が入力するセルは、このプレビューでは空白です。
20行あまりの字句解析器
# 小さな字句解析器: 数、名前、記号。空白は捨てます。
text = "fare * 2 + 300"
tokens = []
i = 0
while i < len(text):
ch = text[i]
if ch == " ":
i = i + 1
elif ch.isdigit():
start = i
# 数字が続くあいだ読み進めます（最長一致）。
while i < len(text) and text[i].isdigit():
i = i + 1
tokens.append(["NUMBER", text[start:i]])
elif ch.isalpha():
start = i
while i < len(text) and text[i].isalpha():
i = i + 1
tokens.append(["NAME", text[start:i]])
else:
tokens.append(["OP", ch])
i = i + 1
print(tokens)
# text を "days*12" に変えて、もう一度実行しましょう。
flex が字句解析器を書く
本物の言語の字句解析器を手で書くのは、時間がかかります。flex のような生成系は、パターンの一覧から字句解析器を書きます。
calc.l では、各行がパターンと、合ったときにする動作の組です。[0-9]+ は、数字が1つ以上という意味です。その動作は、文字列を数に直し、NUMBER というトークンをパーサーに返します。Run で規則を見てから、電卓をゼロから作り直します。
コンパイラのフォルダに入る
cd ~/compilerここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
トークンを返す規則
grep -n "return" calc.lここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
make が作ったものを消す
make cleanここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
電卓を作り直す
makeここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
flex が書いた C の行数
wc -l lex.yy.cここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
字句解析器が知る文字と知らない文字
下の Run は、それぞれ1行を電卓に流し込みます。どのメッセージが字句解析器から、どれがパーサーから出るかを見ましょう。
字句解析器の最後の規則は、点1つです。ほかの規則に合わなかった、どんな文字にも合います。unexpected character と出して、トークンは作りません。残ったトークンを、パーサーが受け取ります。
空白がまったくない
echo "1500+300" | ./calcここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
空白が多すぎる
echo " 8 * 125" | ./calcここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
字句解析器が知らない記号
echo "8 % 3" | ./calcここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
数にくっついた文字
echo "2y + 5" | ./calcここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
先頭のゼロ
echo "0010 * 3" | ./calcここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
小数点のある数
echo "12.5 + 1" | ./calcここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
字句解析器は1文字ごとに1つのトークンを渡す、と思いがちです。それなら 0010 は4つの数になります。実際は最長一致で、パターンに合う限り読み続けます。だから 0010 は1つの NUMBER で、iffy はキーワード if と fy ではなく、1つの NAME です。
さらに挑戦: コメントを捨てる
課題が通ったら、コメントを足しましょう。# から行の終わりまでをコメントとし、トークンを作りません。今の決まりでは、# は ERROR になります。
まず自分のテストを3つ書きます。"price * 2 # 往復" から NAME、OP、NUMBER の3つだけが出ることを確かめましょう。そして、コメントを字句解析器で捨てると、パーサーが楽になる理由を説明しましょう。