Rustで作るプログラミング言語処理系字句解析編

注意: オートマトン、Rustの超基本文法¹は前提知識としています。(実装に対してはオートマトンの知識は必ずしも要求しませんが)

字句解析とは

ある言語のプログラムを与えても、PCにとっては最初はただの文字の羅列でしかありません。これを意味のある文字列ごとに区切り、字句トークンの列にします。

例:) "x = 1" => [ID("x"), EQUAL, INT(1)]

字句トークン:: プログラミング言語の文法の構成単位となるような文字列に対応するトークン

字句解析器の自動生成(ざっくり理論)

字句解析器:: 文字列からトークン列を生成するプログラム

字句解析器を自動生成するには、その自動生成プログラムに正規表現とトークンの対応を与える必要があります。

例

"if"          return Ok(IF);
"else"        return Ok(ELSE);
":"           return Ok(COLON);
"::"          return Ok(COLONCOLON);
[A-Za-z]([A-Za-z]|[0-9])*   return Ok(ID(self.yytext().to_string()));

正規表現から決定性オートマトンを構成することで、文字列からトークン列への変換が実現できます。

(正規表現 => NFA => DFAの流れで構成)

優先規則

ここで、考慮せねばならない文字列がでてきます。以下は文字列とそれにマッチするトークンを示したものです

"iframe" => [IF, ID("rame")]　or　[ID("iframe")]
"if" => [IF, ID("rame")]　or　[ID("iframe")]
"::" => [COLON, COLON]　or　[COLONCOLON]

コードに複数の解釈があってはたまったものではありません。字句解析器はどちらか片方に判別する必要があります。そのための規則が以下のように決められています。

最長一致 ... 正規表現に一致する最長の部分文字列を採用する。
優先規則 ... 同じ長さの場合，上に書いた規則が優先される。

この規則によって

"iframe" ----(最長一致)----> [ID("iframe")]
"if" ----(優先規則)----> [IF]
"::" ----(最長一致)----> [COLONCOLON]

と解釈できました。

実装

しません。

こんなもんイチから実装してたら精神がもたないので、OSSをありがたく使わせていただきます。ごめんなさい怒らないでください。

github.com

使い方やflexファイルの書き方は本家マニュアルを見てください。

cargoでライブラリを作成

$ cargo new lex
$ cd lex

これで、lexディレクトリができました。src/lib.rsを書くことで、ライブラリとして他のプロジェクトで呼び出すことができます。

トークンの定義

src/token.rs クリックしてコードを見る

#[derive(PartialEq, Debug)]
pub enum Token {
    ID(String),    // 変数
    INT(String),   // 数値
    IF,            // if
    ELSE,          // else
    DEF,           // def
    Nil,           // Nil
    LPAREN,        // (
    RPAREN,        // )
    LBRACKET,      // [
    RBRACKET,      // ]
    COMMA,         // ,
    PLUS,          // +
    MINUS,         // -
    TIMES,         // *
    DIV,           // /
    DOT,           // .
    COLON,         // ,
    COLONCOLON,    // ::
    EQ,            // =
    EQEQ,          // ==
    LESS           // <
}

長いですが、まだnonscalaの字句トークンは全て網羅していません。足りない分はあとで追加します。

後で書くテストを有効にするため、enumの前に#[derive(PartialEq, Debug)]と書いています。

本来は明示的にPartialEqトレイトとDebugトレイトをimplementして==比較と、出力するときのフォーマットを定義する必要がありますが、こうすることでいちいち自分で書かなくても、いい感じに実装されます。便利です。

Flexオプション

src/lib.flex クリックしてコードを見る

pub mod token;
use token::Token;
use Token::*;

%%
%class Lexer
%result_type Token

%ALPHA=[A-Za-z]
%DIGIT=[0-9]
%WHITE_SPACE_CHAR=[\ \t\b\012]


"if"          return Ok(IF);
"else"        return Ok(ELSE);
"def"         return Ok(DEF);
"Nil"         return Ok(Nil);
"("           return Ok(LPAREN);
")"           return Ok(RPAREN);
"["           return Ok(LBRACKET);
"]"           return Ok(RBRACKET);
","           return Ok(COMMA);
"+"           return Ok(PLUS);
"-"           return Ok(MINUS);
"*"           return Ok(TIMES);
"/"           return Ok(DIV);
"."           return Ok(DOT);
":"           return Ok(COLON);
"::"          return Ok(COLONCOLON);
"="           return Ok(EQ);
"=="          return Ok(EQEQ);
"<"           return Ok(LESS);

" "           return self.yylex();
\t            return self.yylex();
\r            return self.yylex();
\n            return self.yylex();
[A-Za-z]([A-Za-z]|[0-9])*   return Ok(ID(self.yytext().to_string()));
[1-9][0-9]*                 return Ok(INT(self.yytext().to_string()));

%%

$ rflex lib.flex で字句解析器がlib.rsとして同じディレクトリに生成されます。

テストコード

tests/yylex.rs クリックしてコードを見る

extern crate lex; // src/lib.rsを読み込める

use lex::token::Token::*;

#[test]
fn if_test() {
  let mut lex = lex::Lexer::new(
    "if",
  );

  assert_eq!(lex.yylex().ok(), Some(IF));
  assert!(lex.yylex().is_err());
}

#[test]
fn variable() {
  let mut lex = lex::Lexer::new(
    "x",
  );
  assert_eq!(lex.yylex().ok(), Some(ID("x".to_string())));
  assert!(lex.yylex().is_err());
}

#[test]
fn exp() {
  let mut lex = lex::Lexer::new(
    "x = 1",
  );
  assert_eq!(lex.yylex().ok(), Some(ID("x".to_string())));
  assert_eq!(lex.yylex().ok(), Some(EQ));
  assert_eq!(lex.yylex().ok(), Some(INT("1".to_string())));
  assert!(lex.yylex().is_err());
}

$ cargo test

これでtests以下の#[test]がついた関数をすべて実行できます。

次回予告

今回はOSSに頼ってしまい申し訳ありませんでした。次回からはそんなことはないはずです。見捨てないでください。

さて次回は構文解析です。果たしてモチベを維持できるのか、がんばれopferちゃん。

おすすめ、Rust by Exampledoc.rust-lang.org↩