はじめに
簡単な数式解析ツールを作ったので、その解説を記事にしました。
入力された数式文字列に対して字句解析と構文解析を行うことで計算結果を出力します。
四則演算と括弧による優先順位制御ができます。
> 1 + 2 - 3
0
> (1 + 2) / 3 - 4 * (5 + 6)
-43
字句解析
字句解析とは入力された文字列を解析して、トークンという最小単位の並びに変換する作業のことです。
トークンは列挙体で定義します。
#[derive(Debug, PartialEq)]
pub enum Token {
Number(f64), // 数値
Plus, // 加算演算子 '+'
Minus, // 減算演算子 '-'
Asterisk, // 乗算演算子 '*'
Slash, // 除算演算子 '/'
LParen, // 左括弧 '('
RParen, // 右括弧 ')'
Unknown(char), // 不明なトークン
}
次に上記のトークン列を生成するLexer構造体を定義します。
解析時に文字列を一文字先読みするために、Peekableというイテレータを保持しています。
これでイテレータを進めずに一文字先の文字を確認できます。
pub struct Lexer<T>
where
T: Iterator<Item = char>,
{
chars: Peekable<T>,
}
impl<T> Lexer<T>
where
T: Iterator<Item = char>,
{
pub fn new(chars: T) -> Self {
Lexer {
chars: chars.peekable(),
}
}
fn parse_number(&mut self) -> String {
let mut num = String::new();
while is_digit(self.chars.peek()) {
num.push(self.chars.next().unwrap());
}
num
}
}
parse_number関数は数字文字列の範囲を読み進めて返す関数です。
演算子や括弧は1文字ですが、数字は複数文字で構成されている場合があるので
まとめて読み進める関数を用意しておきます。
次に字句解析処理を実装します。
impl<T> Iterator for Lexer<T>
where
T: Iterator<Item = char>,
{
type Item = Token;
fn next(&mut self) -> Option<Self::Item> {
while is_whitespace(self.chars.peek()) {
self.chars.next();
}
match self.chars.peek() {
c if is_digit(c) => {
let mut num = self.parse_number();
if let Some('.') = self.chars.peek() {
self.chars.next();
num = format!("{}.{}", num, self.parse_number());
}
Some(Token::Number(num.parse::<f64>().unwrap()))
}
_ => match self.chars.next() {
Some('+') => Some(Token::Plus),
Some('-') => Some(Token::Minus),
Some('*') => Some(Token::Asterisk),
Some('/') => Some(Token::Slash),
Some('(') => Some(Token::LParen),
Some(')') => Some(Token::RParen),
Some(c) => Some(Token::Unknown(c)),
_ => None,
},
}
}
}
スペース等の空白をスキップして、何らかの文字が見つかるまで読み進めます。
もし数値文字が来た場合は、数値文字列の解析を行います。
parse_number関数を呼び出して数値文字列をまとめて取得します。
この時、次に.が来た場合は再度parse_number関数を呼び出して小数部分を取得します。
最後に数値文字列をf64にパースしてToken::Numberを返します。
数値文字以外の場合は、それぞれの演算子文字に対応したトークンを返します。
解析できない文字が来たらToken::Unknownを返します。
入力文字列を全て読み進めた場合がNoneを返します。
例えば1 + 2.0 - 3.14という数式を字句解析した場合、以下の様なトークン列を生成します。
[Token::Number(1), Token::Plus, Token::Number(2.0), Token::Minus, Token::Number(3.14)]
構文解析
構文解析とはトークン列を文法的に正しいかを解析して、木構造に変換する処理のことです。
この数式解析ツールでは処理の簡略化のため、木構造を作成せずその場で計算処理を行っています。
ちなみに四則演算の文法をBNFっぽく表現すると以下の様になります。
<expr> ::= <term> [('+'|'-') <term>]*
<term> ::= <factor> [('*'|'/') <factor>]*
<factor> ::= <number> | '(' <expr> ')'
<number> ::= 数値
本記事ではBNFについて説明は省略しますがざっくり説明すると
<expr>は加減算の式、<term>は乗除算の式、<factor>は数値か括弧式を表しています。
下に行くほど計算の優先順位が高くなります。
構文解析を行うParserの定義は以下の通りです。
字句解析と同様にトークンを1つ先読みする必要があるため、Peekableを保持します。
pub struct Parser<T>
where
T: Iterator<Item = Token>,
{
tokens: Peekable<T>,
}
impl<T> Parser<T>
where
T: Iterator<Item = Token>,
{
pub fn new(tokens: T) -> Self {
Parser {
tokens: tokens.peekable(),
}
}
pub fn parse(&mut self) -> Result<f64, String> {
let value = self.parse_expression()?;
match self.tokens.next() {
Some(token) => Err(format!("Invalid token {:?}", token)),
None => Ok(value),
}
}
}
上記のparse関数で入力された数式を解析して計算結果を返します。
解析中にエラーが発生した場合はErrを返します。
また、parse_expression関数の呼び出し後にトークンが残っているかをチェックしています。
トークンが残っている場合は、無効なトークンが存在していると判定してエラーを返します。
残ってない場合は数式を解析できたので計算結果を返します。
parse_expression関数
parse_expression関数は加減算式を解析する関数です。
まずparse_term関数を呼び出してより優先順位の高い数式を解析します。
そしてToken::PlusかToken::Minusが来なくなるまで加減算を続けて、最後に計算結果を返します。
...
fn parse_expression(&mut self) -> Result<f64, String> {
let mut left_value = self.parse_term()?;
while let Some(Token::Plus | Token::Minus) = self.tokens.peek() {
let token = self.tokens.next();
let right_value = self.parse_term()?;
if let Some(Token::Plus) = token {
left_value += right_value;
} else {
left_value -= right_value;
}
}
Ok(left_value)
}
parse_term関数
次に乗除算の式の解析を行うparse_term関数を追加します。
処理の流れはparse_expression関数とほぼ同じです。
まず優先順位の高いparse_factor関数を呼び出して、Token::AsteriskかToken::Slashが来なくなるまで乗除算を繰り返します。
...
fn parse_term(&mut self) -> Result<f64, String> {
let mut left_value = self.parse_factor()?;
while let Some(Token::Asterisk | Token::Slash) = self.tokens.peek() {
let token = self.tokens.next();
let right_value = self.parse_factor()?;
if let Some(Token::Asterisk) = token {
left_value *= right_value;
} else {
left_value /= right_value;
}
}
Ok(left_value)
}
parse_factor関数
最も優先順位の高いparse_factor関数を追加します。
次のトークンがToken::LParenなら括弧付きの数式なので、再度parse_expression関数を呼び出します。
その後Token::RParenが来ることを確認します。
次のトークンが数値ならばその値を返します。
それ以外の場合は、トークンの並びが文法的に正しくないのでエラーを返します。
...
fn parse_factor(&mut self) -> Result<f64, String> {
match self.tokens.next() {
Some(Token::LParen) => {
let value = self.parse_expression()?;
if let Some(Token::RParen) = self.tokens.peek() {
self.tokens.next();
Ok(value)
} else {
Err("RParen not found".to_string())
}
}
Some(Token::Number(value)) => Ok(value),
Some(token) => Err(format!("Invalid token {:?}", token)),
None => Err("Invalid syntax".to_string()),
}
}
この様に解析関数を再帰的に呼び出すことで、数式のトークン列から計算結果を求めることができます。
main関数
最後にmain関数を実装して完了です。
ループ内で標準入力を読み取り、その結果をParserに渡します。
そして解析を行って結果を画面に出力します。エラーの場合はそのメッセージを出力します。
空文字を入力したらループを出て終了です。
fn main() {
loop {
print!("> ");
stdout().flush().unwrap();
let mut input = String::new();
stdin().read_line(&mut input).expect("Failed to read line");
input = input.trim().to_string();
if input.is_empty() {
break;
}
let lexer = Lexer::new(input.chars());
let mut parser = Parser::new(lexer);
match parser.parse() {
Ok(value) => println!("{value}"),
Err(message) => println!("ERROR: {message}"),
}
}
}
参考文献