Compiler/Lexical Analyzer
Compiler/Lexical Analyzer
タスク概要
シンプルなプログラミング言語用の Lexical Analyzer を作る。
実装
lex 使おうぜ、lex。と言いたくなる気も少しあるけど、真面目に実装する。そもそも C 言語じゃないしね。
正規表現のパターンに対するマッチといえば、有限オートマトンだ。とはいえ今回は手で実装するので、知っているにこしたことはないが知らなくても問題ない。それこそ lex を作るというのなら必須だけど。
事前準備
本体の実装前に、使用するデータ構造を用意する。
エラー
Rust なので、エラーが起こり得る処理は Result を返すようにする。Result は Result<T, E> で成功時とエラー時の型を指定するが、このエラーの型を自前で定義する。
lexcal analyzer 単体なら、std::io::Error をそのまま使っても大丈夫かなと思ったりもしたけど、他の Compiler 関連タスクでも std::io::Error を使うのはちょいとキツい。
というわけで std::io::Error を参考にして作ってみた。
#[derive(Debug)] pub enum ErrorKind { LexicalAnalyzerError, } #[derive(Debug)] pub struct CompileError { kind: ErrorKind, repr: Box<dyn Error + Send + Sync>, }
ErrorKind には今後 SyntaxError 等が増える、予定。
トークン
そのトークンがどんな種類かを示す TokenKind とそのトークンの場所。
#[derive(Debug)] pub struct Token { pub kind: TokenKind, line_number: usize, column_number: usize, }
TokenKind は Input Specification を基にしている。
#[derive(Debug, PartialEq, Eq)] pub enum TokenKind { OpMultiply, OpDivide, OpMod, OpAdd, OpSubtract, // OpNegate, 使わない OpLess, OpLessEqual, OpGreater, OpGreaterEqual, OpEqual, OpNotEqual, OpNot, OpAssign, OpAnd, OpOr, LeftParen, RightParen, LeftBrace, RightBrace, Semicolon, Comma, KeywordIf, KeywordElse, KeywordWhile, KeywordPrint, KeywordPutc, Identifier(String), Integer(i32), String(String), EndOfInput, }
Identifier, Integer, String のみは値を持つ。
解析部
ここが本体。
pub struct LexicalAnalyzer<'a> { /// 先読みした一文字。EOF の場合に None。 next_char: Option<char>, /// ソースの読み込み元 stream: Chars<'a>, /// 現在の行数 line_number: usize, /// 現在の列数 column_number: usize, }
lexcal analyer の常道として一文字先読みをしておき、これを消費したら次の一文字を読む形で処理を行う。文字は stream から読み込み、next_char に格納する。これを行うのが read_char()。
/// stream を一文字進め、next_char に格納する。 fn read_char(&mut self) { if self.next_char == Some('\n') { self.line_number += 1; self.column_number = 0; } self.next_char = self.stream.next(); self.column_number += 1; }
なお、ここで line_number と column_number の変更も行う。
それでは簡単なトークンから順に実装していく。処理の大元は next_token()というメソッドにある。
0 文字で決まるもの
EndOfInput のみがこれに当てはまる。なので、next_char が None であるかを見れば良い。終わり。
1 文字で決まるもの
その文字が単独で出現した時点でトークンが確定できるのは {'*','%','+','-','(',')','{','}',';',','}。これも next_char を見るだけでできる。一例として '*' を挙げると、
Some('*') => { self.read_char(); Ok(Token::new(TokenKind::OpMultiply, start_line, start_column)) }
となる。EndOfInput と違って next_char の文字を消費しているため、read_char() で次の文字に進めておくのを忘れずに。
2 文字目で決まるもの
これは {'<','>','=','!','&','|'} が該当する。うち、{'<','>','=','!'} は現在の next_char を見ただけでは何のトークンになるか一意に決めることができない。'<' の場合、OpLess と OpLessEqual のどちらになるかが分からない。なので、次の文字を見て決める。次の文字が '=' なら OpLessEqual で、それ以外なら OpLess。
/// 一文字目が '<' のトークン fn read_less(&mut self, line_number: usize, column_number: usize) -> Result<Token> { self.read_char(); if self.next_char == Some('=') { self.read_char(); Ok(Token::new( TokenKind::OpLessEqual, line_number, column_number, )) } else { Ok(Token::new(TokenKind::OpLess, line_number, column_number)) } }
ここで、'=' の場合にのみ read_char() を呼んで next_char を消費していることに注意。もし、next_char が '=' 以外の文字だった場合、その文字は次のトークンの一部であるため、ここで消費してしまうと間違った結果になってしまう。
{'&','|'} に関してはこの時点でどのトークンになるか一意に決まるのだけれど、それぞれ "&&", "||" で一つのトークンを構成するため、次の文字がそれ以外になっていないかを調べる。で、違っていたらエラー。
/// 一文字目が '&' のトークン fn read_and(&mut self, line_number: usize, column_number: usize) -> Result<Token> { self.read_char(); if self.next_char == Some('&') { self.read_char(); Ok(Token::new(TokenKind::OpAnd, line_number, column_number)) } else { Err(CompileError::new( ErrorKind::LexicalAnalyzerError, "invalid character: '&' is expected", )) } }
'/' またはコメント
これも 2 文字目で決まる、と言えなくもないのだけれど、コメントに関して少し特別な処理がある。というのも、コメントは
という特徴がある。これに対応するためには
- コメントを読み飛ばす
- コメントに続くトークンを読み込む
を行う。
/// '/' の次の文字が '*' 以外: OpDivide /// '/' の次の文字が '*' : コメントを読み飛ばし、次のトークンを返す fn read_div(&mut self, line_number: usize, column_number: usize) -> Result<Token> { self.read_char(); if self.next_char == Some('*') { // comment self.read_char(); self.discard_comment()?; self.next_token() } else { Ok(Token::new(TokenKind::OpDivide, line_number, column_number)) } }
read_div という名前で良いかはさておき、discard_comment() でコメントを読み飛ばし、next_token() でコメントに続くトークンを読み込んでいる。難しいところは何もない。discard_comment() は "*/" が来るまでひたすら read_char() を呼んでいるだけだから詳しくはソースを見て。
Integer その 1
これからは長さが不定のトークンを扱う。とはいえ、元々実装対象の言語が非常にシンプルなため、大体は最初の文字を見た時点でどのトークンであるかは決まってしまい、あとはそのトークンがどこまでなのかを調べるだけだったりする。
それで、最初が数字([0-9])で始まっている場合は、Integer だ。処理は read_integer_literal() で行っている。
/// 数値リテラルを読み込む fn read_integer_literal(&mut self, line_number: usize, column_number: usize) -> Result<Token> { let mut number_string = String::new(); number_string.push(self.next_char.unwrap()); self.read_char(); loop { match self.next_char { Some(c) if is_number(c) => { number_string.push(c); self.read_char(); } Some(c) if c.is_alphabetic() => { return Err(CompileError::new( ErrorKind::LexicalAnalyzerError, "Invalid number. Starts like a number, but ends in non-numeric-characters", )); } _ => { break; } } } match number_string.parse() { Ok(num) => Ok(Token::new( TokenKind::Integer(num), line_number, column_number, )), Err(_) => Err(CompileError::new( ErrorKind::LexicalAnalyzerError, "invalid number.", )), } }
基本的には String を用意して数字が続く限り push し続けるで構わないのだけれど、エラー処理で少し手間がかかる。というのも、直後にアルファベットが来た場合には、そこで Integer トークン終了とするのではなく、エラーにしなくてはいけない。つまり、"12<34" は Integer OpLess Integer という正常なトークン列であるのに対し、"12a34" はエラーであり、Integer Identifier Integer としてはいけない。
この処理は loop 内の match で行っている。
無事に読み終えたなら、String を数値に変換して Integer トークンを作る。
Integer その 2
Integer は文字定数としても表現可能。要は 'a' なら 97 といった具合。よって '\'' が来たら Integer。この処理は read_char_literal() で行う。
正規表現による char literal の表現は、
'([^'\n]|\\n|\\\\)'
となっている。エスケープ文字が頻出していて読みにくいが、これは大雑把に single quote で囲まれた一文字と考えられる。改行文字と single quote は不可。ただし、改行文字に関してはエスケープシーケンスを使うことで '\n' として表現できる。他にエスケープ文字自身を表す '\\' もある。よって char literal で single quote は使用不可。
コードを書く際にやっかいなのは、ソース中の '\n' が一文字の改行文字を表すのか '\' と 'n' の 2 文字からなるエスケープシーケンスなのかをちゃんと意識しないと混乱してしまうこと。
String
'"' から始まっていたら、それは String になる。char literal 同様エスケープを考慮する。String 内で使えないのは '"' と 改行文字。前者はエスケープシーケンスでも表現不可。なので、'"' 来るまで読み込むだけで ok。途中改行文字と出会ったらエラー。もちろん '"' が来ないままソースの末尾に辿りついてしまった場合もエラー。
/// 文字列リテラルを読み込む。 fn read_string_literal(&mut self, line_number: usize, column_number: usize) -> Result<Token> { let mut s = String::new(); self.read_char(); loop { match self.next_char { Some('"') => { self.read_char(); return Ok(Token::new(TokenKind::String(s), line_number, column_number)); } Some('\n') => { return Err(CompileError::new( ErrorKind::LexicalAnalyzerError, "End-of-line while scanning string literal", )); } Some(c) => { s.push(if c == '\\' { self.read_escaped_sequence()? } else { c }); } None => { return Err(CompileError::new( ErrorKind::LexicalAnalyzerError, "unexpected EOF", )); } } self.read_char(); } }
Identifier
Identifier のパターンはエスケープがないこともあってわかりやすい。
[_a-zA-Z][_a-zA-Z0-9]*
というわけで、先頭の文字が [_a-zA-Z] なら read_identifier() を呼ぶ。read_identifier() 内では [_a-zA-Z0-9] 以外の文字が来るまで読み込み続ける。
loop { if let Some(c) = self.next_char { if is_alnum(c) { identifier.push(c); self.read_char(); } else { break; } } else { // End of Input break; } }
キーワード類
これで最後。
lex とかで字句解析器を作る場合にはキーワード類もその場で識別すると思うけど、手書きでそれをやると面倒だ。なので、Identifier として識別してから、それがキーワードなのかを別途判定する。
Ok(Token::new( match &identifier[..] { "if" => TokenKind::KeywordIf, "else" => TokenKind::KeywordElse, "while" => TokenKind::KeywordWhile, "print" => TokenKind::KeywordPrint, "putc" => TokenKind::KeywordPutc, _ => TokenKind::Identifier(identifier), }, line_number, column_number, ))
余談
このタスクは Compiler という大きなタスクの中のサブタスクという位置付けということもあり、ディレクトリ構成を compiler/lexical_analyzer としたかった。ところが Cargo ではワークスペースのネストはできないし、Compiler の各タスクは独立性を高くするためか個別に実行形式を作るものになっていて、単独の compiler というクレートで全てをまかなうのもよろしくない。
ちなみに
cargo new --bin compiler/lexical_analyer
もうまくいかなかった。
仕方なく lexical_analyzer としたものの、これだと Compiler タスクの一部だということが分からないし、lexical_analyzer::lexical_analyzer::LexicalAnalyzer とかやりたくなかったから lib.rs に本体のコードを書くはめになってしまった。どうすれば良かったのだろう。
