RustでJSONの構文解析がしたい
経緯
プログラミング言語論の講義を大学で履修しており、構文解析が面白かったのでRustで実装してみたいと思いました。なるべく学んだことを対応づけながら実装していきます。
ちなみに作ったものを学友に教えるのが目的なので、あまり高度なものは作りたくない...。
-> Json Parserだったら楽では
ってことでJsonの構文解析をやってみます。
脳死でやりたいのでなんちゃってTDDでやります
単にParserの実装をしても面白くないので、Parser -> Formatter -> Cliとして派生させていきます。
成果物
字句解析
まず最初に字句解析をします。
まずはJSONの構成に必要なTokenを定義します。
計算機科学における字句解析 (じくかいせき、英: lexical analysis) とは、広義の構文解析の前半の処理で、自然言語の文やプログラミング言語のソースコードなどの文字列を解析して、後半の狭義の構文解析で最小単位（終端記号）となっている「トークン」（字句）の並びを得る手続きである。字句解析を行うプログラムは字句解析器である。
作ってからWikiを確認しましたがやっぱりTokenっていわゆる終端記号のことだったっぽい？
考察 *終端記号と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