経緯

プログラミング言語論の講義を大学で履修しており、構文解析が面白かったので Rust で実装してみたいと思いました。なるべく学んだことを対応づけながら実装していきます。

ちなみに作ったものを学友に教えるのが目的なので、あまり高度なものは作りたくない...。
-> Json Parserだったら楽では
ってことで Json の構文解析をやってみます。

脳死でやりたいのでなんちゃって TDD でやります
単に Parser の実装をしても面白くないので、Parser -> Formatter -> Cli として派生させていきます。

成果物
https://github.com/sor4chi/json-parser

字句解析

まず最初に字句解析をします。

まずは JSON の構成に必要な Token を定義します。

計算機科学における字句解析 (じくかいせき、英: lexical analysis) とは、広義の構文解析の前半の処理で、自然言語の文やプログラミング言語のソースコードなどの文字列を解析して、後半の狭義の構文解析で最小単位（終端記号）となっている「トークン」（字句）の並びを得る手続きである。字句解析を行うプログラムは字句解析器である。

作ってから Wiki を確認しましたがやっぱり Token っていわゆる終端記号のことだったっぽい？

考察 *終端記号とToken*

言語の理論でチョムスキー標準形など、言語の生成規則の標準化をするプロセス内で終端を明示的にする表現が出てきます。

$S \rightarrow AB | ASB$
$A \rightarrow a$
$B \rightarrow b$

このように終端記号を弾き出す $a$ や $b$ のことを終端記号、いわゆる Token と呼ぶのかな？
こういう標準化のやりたいことがなんとなく理解できる。形式言語から構文を推測するための手法？

実装し始めてすぐ気づいて直したのですが、Number や String といったリテラルのものを Token として扱うと定義や処理が複雑になってしまいます。これは上記 Wiki にも全く同じことが書いてあって安心しました。
Token = 終端記号とはせず、リテラルも一塊の Token として扱うようにした方が処理上都合いいとわかりました。

考察 *JSONのBNFと終端記号の話*

リポジトリに JSON を BNF 記法で定義したもの。

BNF Playground
を書いて置いておきましたが、このダブルクオートで囲われた記号にあたるのが Token というわけですね？

なので、Token は以下のように定義します。

#[derive(Debug, PartialEq, PartialOrd, Clone)]
pub enum Token {
    LBrace,
    RBrace,
    LBracket,
    RBracket,
    Colon,
    Comma,
    StringValue(String),
    NumberValue(f64),
    BooleanValue(bool),
    NullValue,
    End,
}

Rust の enum は構造体のように扱えるので、String や Number などのリテラルを Token に含めることができます。この性質を利用して先ほどの拡張された定義での Token を実装します。

テスト

TDD なんで先にテストを書きます。

#[test]
fn test_tokenize() {
    let input = r#"{"foo":123}"#;
    let mut lexer = Lexer::new(input);
    let tests: Vec<Token> = vec![
        Token::LBrace,                         // {
        Token::StringValue("foo".to_string()), // "foo"
        Token::Colon,                          // :
        Token::NumberValue(123.0),             // 123
        Token::RBrace,                         // }
        Token::End,                            // end
    ];

    for test in tests {
        assert_eq!(lexer.next_token(), test);
    }
}

これが通れば一応簡易的な Lexer は完成です。

実装

Lexer を実装します。（コードは全文載せると長いので一部抜粋しています）

まず、Lexer を作るにあたって Peek という構造を使います。
Peek は入力を 1Item ずつ読み込むいわばストリームで、カーソル（ポインタ）を進めずに次の Item を覗き見る（peek する）ことができます。
そして次の Item にカーソルを進めるとそれはその Item を消費した（consume した）ことになり、その Item は破棄されます。

字句解析では、Input が Vec<char> で現在見ている文字と次の文字を見る必要があるので、Peek というデータ構造がピッタリのようです。

まず Vec を Peekable な Iterator に変換するユーティリティ型を定義します。これは後の構文解析でも使うので、src/utility.rs に定義しました。

use std::iter::Peekable;
use std::vec::IntoIter;

pub type PeekableIter<T> = Peekable<IntoIter<T>>;

次に Lexer を定義します。Lexer は Peekable な Iteratorchar_stream を持ちます。
あとは new メソッドで Lexer を作成できるようにします。

pub struct Lexer {
    char_stream: PeekableIter<char>,
}

impl Lexer {
    pub fn new(input: &str) -> Self {
        Lexer {
            char_stream: input.chars().collect::<Vec<char>>().into_iter().peekable(),
        }
    }
}

本当は Parser を正しく実装する場合それぞれの Token が Source Code 上のどこにあるか、どれくらいの長さかを保持しておくことが必要です(エラー出力、フォーマットなどで使う)。
今回は簡易的に実装するので、Token の位置情報は保持しません。

次に、Lexer の Token を PhfMap で定義します。これは src/token.rs に定義しました。
PhfMap は Rust のマクロで、コンパイル時にハッシュマップを作成します。静的なハッシュマップを作成するので、実行時にはハッシュマップを作成する必要がなく、高速に動作して便利です。

pub static CHAR_TOKENS: phf::Map<char, Token> = phf_map! {
    '{' => Token::LBrace,
    '}' => Token::RBrace,
    '[' => Token::LBracket,
    ']' => Token::RBracket,
    ':' => Token::Colon,
    ',' => Token::Comma,
};

pub static KEYWORD_TOKENS: phf::Map<&'static str, Token> = phf_map! {
    "true" => Token::BooleanValue(true),
    "false" => Token::BooleanValue(false),
    "null" => Token::NullValue,
};

ここでは、{ や } などの Char を Token に変換するためのマップと、true や false などの Keyword を Token に変換するためのマップを定義しています。

次に、Lexer の consume_char メソッドを実装します。これは Peekable な Iterator の next メソッドを呼び出して、次の文字を消費します。

文字消費

テスト

まずはテストを書きます。

#[test]
fn test_consume_char() {
    let input = r#"{}[]:,"#;
    let mut lexer = Lexer::new(input);
    assert_eq!(lexer.consume_char(), Token::LBrace); // {
    assert_eq!(lexer.consume_char(), Token::RBrace); // }
    assert_eq!(lexer.consume_char(), Token::LBracket); // [
    assert_eq!(lexer.consume_char(), Token::RBracket); // ]
    assert_eq!(lexer.consume_char(), Token::Colon); // :
    assert_eq!(lexer.consume_char(), Token::Comma); // ,
}

これが通れば consume_char メソッドは完成です。

実装

impl Lexer {
    fn consume_char(&mut self) -> Token {
        match self.char_stream.next() {
            Some(c) => match CHAR_TOKENS.get(&c) {
                Some(token) => token.clone(),
                None => Token::Unknown,
            },
            None => Token::End,
        }
    }
}

これで、Lexer の consume_char メソッドは完成です。

これを数値リテラルや Boolean 値、Null 値などの Token に対しても実装します。（コードは省略します）

構文解析

構文解析は、字句解析で得られた Token を元に、構文木を作成します。
イメージとしては、1 次元的な Token の列を、構文という 2 次元的な木構造のデータに変換するようなものです。

構文解析は、字句解析と同様に、Peekable な Iterator を使って実装します。

まずは、構文解析のための構文木を定義します。構文木は src/node.rs に定義しました。

pub enum SyntaxKind {
    StringLiteral(String),
    NumberLiteral(f64),
    TrueKeyword,
    FalseKeyword,
    NullKeyword,
    PropertyAssignment,
    Identifier(String),
    ObjectLiteralExpression,
    ArrayLiteralExpression,
    End,
}

構文木は、SyntaxKind という enum をネストした構造体で定義しています。

次に、構文木のノードを定義します。ノードは、SyntaxKind と、そのノードの子ノードの Vec を持ちます。

pub struct SyntaxNode {
    pub kind: SyntaxKind,
    pub children: Vec<SyntaxNode>,
}

こうすることで構文のパーツひとつひとつ（ノード）の関係を表現できます。

例えば Object は Key(=foo)と Value(=bar)のペアを持ちますが、これを SyntaxNode で表現します。

SyntaxNode {
    kind: SyntaxKind::ObjectLiteralExpression,
    children: vec![
        SyntaxNode {
            kind: SyntaxKind::PropertyAssignment,
            children: vec![
                SyntaxNode {
                    kind: SyntaxKind::Identifier("foo".to_string()),
                    children: vec![],
                },
                SyntaxNode {
                    kind: SyntaxKind::StringLiteral("bar".to_string()),
                    children: vec![],
                },
            ],
        },
    ],
}

というようになり、構文木を構成できます。

次に、構文解析をする Parser を定義します。Parser は Peekable な Iteratortoken_stream を持ちます。

pub struct Parser {
    token_stream: PeekableIter<Token>,
}

Parser は、src/parser.rs に定義しました。

テスト

テストを書きます。

#[test]
fn test_parse() {
    let input = r#"{"foo": "bar"}"#;
    let expected = SyntaxNode {
        kind: SyntaxKind::ObjectLiteralExpression,
        children: vec![SyntaxNode {
            kind: SyntaxKind::PropertyAssignment,
            children: vec![
                SyntaxNode {
                    kind: SyntaxKind::Identifier("foo".to_string()),
                    children: vec![],
                },
                SyntaxNode {
                    kind: SyntaxKind::StringLiteral("bar".to_string()),
                    children: vec![],
                },
            ],
        }],
    };

    let mut parser = Parser::new(input);
    let actual = parser.parse();
    assert_eq!(actual, expected);
}

これが通れば、parse メソッドは完成です。

実装

とりあえず簡易的に実装してみます。

まずは、Parser の new メソッドを実装します。これは、Lexer から Token を受け取って、Parser を作成します。

impl Parser {
    pub fn new(input: &str) -> Self {
        let mut lexer = Lexer::new(input);
        let tokens = lexer.tokenize();
        let token_stream = tokens.into_iter().peekable();
        Parser { token_stream }
    }
}

次に、Parser の parse メソッドを実装します。

impl Parser {
    pub fn parse(&mut self) -> Node {
        let first_token = self.token_stream.peek();
        let result = match first_token {
            Some(Token::LBrace) => self.consume_object(),
            Some(Token::LBracket) => self.consume_array(),
            _ => Err("Unexpected the first token of input".to_string()),
        };
        match result {
            Ok(value) => value,
            Err(e) => panic!("{}", e),
        }
    }
}

もうちょっといい書き方ができそうなのですが、とりあえずこれで。
まず簡単な Validation を行っています。
{ か [ で始まっているかを確認しています。これは、JSON のルートノードは Object か Array であることを意味しています。

次に、consume_object か consume_array を呼び出しています。先ほどの Validation で、{ か [ で始まっていることを確認しているので、ここでは、それぞれのメソッドを呼び出すだけです。

Property Assignmentの解析(消費)

Property Assignment の解析(消費)を実装します。
Object は内部的に Key と Value のペアを持っています。これを Property Assignment と呼ぶことにしています。
この Property Assignment を複数持っているのが Object と考えています。

テスト

#[test]
fn test_property_assignment() {
    let input = r#""foo": 1"#;
    let expected = SyntaxNode {
        kind: SyntaxKind::PropertyAssignment,
        children: vec![
            SyntaxNode {
                kind: SyntaxKind::Identifier("foo".to_string()),
                children: vec![],
            },
            SyntaxNode {
                kind: SyntaxKind::NumberLiteral(1.0),
                children: vec![],
            },
        ],
    };
}

実装

impl Parser {
    fn consume_property_assignment(&mut self) -> Result<Node, String> {
        let property_name = match self.token_stream.peek() {
            Some(Token::StringValue(s)) => s.clone(),
            _ => return Err("Unexpected Identifier".to_string()),
        };
        self.token_stream.next();
        self.token_stream.next();
        match self.consume_value() {
            Ok(value) => Ok(Node::new(
                SyntaxKind::PropertyAssignment,
                vec![
                    Node::new(SyntaxKind::Identifier(property_name), vec![]),
                    value,
                ],
            )),
            Err(e) => Err(e),
        }
    }
}

まず、token_stream から Token を取り出しています。これは、Property Name となります。
次に、: を読み飛ばしています。これは、Property Name と Value の間にある : を読み飛ばしています。
最後に、Value を読み込んでいます。

他にも Object や Array の解析(消費)を実装する必要がありますが、ここでは省略します。

このように構文解析を実装してみました。

派生

これら Parser は Crate としてパッケージ化して、他のプロジェクトで使えるようにします。

パッケージ呼び出し

例えば formatter の Cargo.toml には以下のように記述します。

[package]
name = "formatter"
version = "0.1.0"
edition = "2021"

[dependencies]
json-parser = { path = "../parser" }

こうすれば crates/ フォルダにある parser パッケージを呼び出すことができます。
こうやって詳細に機能を切り出すことが容易にできる crate のシステムは便利ですね。

Formatter や Cli などの別のアプリケーション内で parser パッケージを呼び出してみます。
例えば Formatter の main.rs には以下のように記述します。

use json_parser::{
    node::{Node, SyntaxKind},
    parse::Parser,
};

fn main() {
    let input = r#"{
    "foo": 1,
    "bar": "baz"
}"#;
    let mut parser = Parser::new(input);
    let node = parser.parse();
    println!("{:#?}", node);
}

今まで parser/に書いてきた構文解析の資産を呼び出して別のアプリケーションで派生させることができそうですね。

まとめ

Formatter や Cli などの別のアプリケーション化は実装が長いので省略しますがぜひソースコードを読んでみてください。

学びたて or 今回が初めてなことだらけで実装にこだわる時間もなかったので質が最悪ですが、講義の復習と Rust の学習のいい機会になりました。

ここまで読んでくださりありがとうございました。

Discussion