if/while/forを構文解析する——文のASTでプログラム全体を組み立てる
式のパースだけでは、プログラムを表現できない
1 + 2 * 3のような式は、それ単体では評価すると値になりますが、プログラムはそれだけで成り立ちません。値に名前を付けて後で使い回す（let）、条件によって処理を分岐する（if/else）、同じ処理を繰り返す（while/for）、途中で処理を打ち切って抜ける（return/break/continue）——こうした「値を作る」のではなく「プログラムの流れを制御する」要素を文（Statement）と呼びます。プログラム全体は、この文の並びとして表現されます。今回は式のパーサに続けて、この文を構文解析し、抽象構文木（AST）をプログラム全体が表現できる形まで拡張しました。
Stmtの設計
文を表すStmtは、式のExprと同様のenumとして定義しました。
pub type Block = Vec<Stmt>;
#[derive(Debug, Clone, PartialEq)]
pub enum Stmt {
Let {
name: String,
value: Expr,
},
Expr(Expr),
Block(Block),
If {
condition: Expr,
then_branch: Block,
else_branch: Option<Box<Stmt>>,
},
While {
condition: Expr,
body: Block,
},
For {
var: String,
iterable: Expr,
body: Block,
},
Return(Option<Expr>),
Break,
Continue,
}Exprを扱う既存のenumとは別にStmtという新しいenumを用意したのは、これまでのTokenKindとBinaryOpを分けた理由と同じ発想です。「値を生む式」と「プログラムの流れを制御する文」は役割が異なるので、型としても分離しています。Stmt::Expr(Expr)のように、文の中に式を埋め込むケース（x;のような式文）はありますが、逆に式の中に文が埋め込まれることはありません。この非対称性が、この言語が「ブロックの最後の式がそのまま戻り値になる」ようなRust的な式指向の言語ではなく、C++的な文中心の言語であることを型の上でも表しています。
then_branch/bodyは素のBlock（Vec<Stmt>）ですが、else_branchだけOption<Box<Stmt>>という一段複雑な型になっています。これはelseの後に来るものが「別のif文」（else ifの連鎖）か「素のブロック」かのどちらもあり得るためで、Stmtという共通の型に両方を収めることで、新しい型を増やさずに表現しています。
波括弧を必須にした理由——dangling else問題
if/while/forの本体は、常に{ ... }で囲むことを文法上必須にしました。C言語のように波括弧を省略して単文だけを書けるようにする設計もありますが、それには「dangling else（ぶら下がりelse）問題」と呼ばれる古典的な曖昧さが伴います。
if (a)
if (b)
foo();
else
bar();このコードのelseが、内側のif (b)に対応するのか、外側のif (a)に対応するのか、インデントだけでは判断できません（実際のC言語では「一番近いifに対応する」という規則で曖昧さを解消していますが、書き手の意図とズレやすく、バグの温床になりがちです）。波括弧を必須にしてしまえば、この曖昧さは構文レベルでそもそも発生しません。RustやGoが同様の理由で波括弧を必須にしているのと同じ判断です。
Parserの実装: 文の再帰下降パース
式のパース（Pratt Parsing）が「演算子の優先順位」という1つの明確な問題を解くための専用のアルゴリズムだったのに対し、文のパースには優先順位のような概念はありません。文の種類は次のトークンを見ればほぼ一意に決まるため、素直な再帰下降パース（先頭のトークンで分岐し、各文の形に合わせて必要なトークンをexpectで確認しながら読み進める）で実装しています。
プログラム全体のエントリポイントはparse_programで、Eofが出るまでparse_stmtを呼び続けます。
pub fn parse_program(&mut self) -> Result<Vec<Stmt>, ParseError> {
let mut stmts = Vec::new();
while self.peek_kind() != &TokenKind::Eof {
stmts.push(self.parse_stmt()?);
}
Ok(stmts)
}
fn parse_stmt(&mut self) -> Result<Stmt, ParseError> {
match self.peek_kind() {
TokenKind::Let => self.parse_let_stmt(),
TokenKind::If => self.parse_if_stmt(),
TokenKind::While => self.parse_while_stmt(),
TokenKind::For => self.parse_for_stmt(),
TokenKind::Return => self.parse_return_stmt(),
TokenKind::Break => {
self.advance();
self.expect(TokenKind::Semicolon, "expected ';' after 'break'")?;
Ok(Stmt::Break)
}
TokenKind::Continue => {
self.advance();
self.expect(TokenKind::Semicolon, "expected ';' after 'continue'")?;
Ok(Stmt::Continue)
}
TokenKind::LBrace => Ok(Stmt::Block(self.parse_block()?)),
_ => self.parse_expr_stmt(),
}
}先頭のトークンがどの文にも当てはまらない場合（識別子・リテラル・(など）は、式文として扱います。式単体に;を付けたものが1つの文になる、というのはC言語系ではおなじみの規則です。
fn parse_expr_stmt(&mut self) -> Result<Stmt, ParseError> {
let expr = self.parse_expression()?;
self.expect(TokenKind::Semicolon, "expected ';' after expression statement")?;
Ok(Stmt::Expr(expr))
}if文は、elseの直後がさらにifかどうかを見て、else ifの連鎖と単純なelseブロックを区別します。
fn parse_if_stmt(&mut self) -> Result<Stmt, ParseError> {
self.advance();
self.expect(TokenKind::LParen, "expected '(' after 'if'")?;
let condition = self.parse_expression()?;
self.expect(TokenKind::RParen, "expected ')' after if condition")?;
let then_branch = self.parse_block()?;
let else_branch = if self.peek_kind() == &TokenKind::Else {
self.advance();
if self.peek_kind() == &TokenKind::If {
Some(Box::new(self.parse_if_stmt()?))
} else {
Some(Box::new(Stmt::Block(self.parse_block()?)))
}
} else {
None
};
Ok(Stmt::If { condition, then_branch, else_branch })
}else ifが来た場合、parse_if_stmtが自分自身を再帰的に呼び出しています。if (a) { .. } else if (b) { .. } else { .. }は、Stmt::Ifのelse_branchの中にさらにStmt::Ifが入れ子になった構造として表現され、else ifをいくつ連ねても同じ仕組みで対応できます。
while・forも、条件式やループ変数を(...)の中で読み取る点を除けばifと同じ形です。
fn parse_for_stmt(&mut self) -> Result<Stmt, ParseError> {
self.advance();
self.expect(TokenKind::LParen, "expected '(' after 'for'")?;
let var = self.parse_ident()?;
self.expect(TokenKind::In, "expected 'in' after for-loop variable")?;
let iterable = self.parse_expression()?;
self.expect(TokenKind::RParen, "expected ')' after for-loop header")?;
let body = self.parse_block()?;
Ok(Stmt::For { var, iterable, body })
}forはfor (item in arr) { ... }という、変数名と対象をinで結ぶ形にしました。C言語のような3節（初期化式・条件式・更新式）のforではなく、配列などのコレクションを走査するfor-inの形です。if/whileと同じく条件（ここではループヘッダ）全体を(...)で囲む、という文法上の一貫性を保っています。
returnは、値を伴う場合と伴わない場合の両方をサポートしています。
fn parse_return_stmt(&mut self) -> Result<Stmt, ParseError> {
self.advance();
let value = if self.peek_kind() == &TokenKind::Semicolon {
None
} else {
Some(self.parse_expression()?)
};
self.expect(TokenKind::Semicolon, "expected ';' after return statement")?;
Ok(Stmt::Return(value))
}returnの直後を覗いて、それが;ならその場でNone（値なしのreturn;）、そうでなければ式としてパースします。値を返す関数のreturn 1;と、値を返さない関数（Rustで言う()型、C/C++/Javaで言うvoid）の途中離脱に使うreturn;の両方を、1つのStmt::Return(Option<Expr>)で表現しています。
テスト
else ifの連鎖のように、パース結果の入れ子構造そのものを検証するテストを書いています。
#[test]
fn else_if_chain() {
assert_eq!(
parse_program("if (a) { 1; } else if (b) { 2; } else { 3; }"),
vec![Stmt::If {
condition: Expr::Ident("a".to_string()),
then_branch: vec![Stmt::Expr(Expr::Int(1))],
else_branch: Some(Box::new(Stmt::If {
condition: Expr::Ident("b".to_string()),
then_branch: vec![Stmt::Expr(Expr::Int(2))],
else_branch: Some(Box::new(Stmt::Block(vec![Stmt::Expr(Expr::Int(3))]))),
})),
}]
);
}動作確認
これまでのフェーズでは字句解析・構文解析の結果を確認するだけでしたが、今回でプログラム全体をパースできるようになったため、ParserをCLIに統合しました。ファイルを読み込み、字句解析→構文解析を通して得られたASTをそのまま表示します。
$ cat examples/hello.na
let x = 1 + 2 * 3;
if (x > 5) {
x;
} else {
0;
}
$ cargo run -- examples/hello.na
Let {
name: "x",
value: Binary {
op: Add,
left: Int(1),
right: Binary {
op: Mul,
left: Int(2),
right: Int(3),
},
},
}
If {
condition: Binary {
op: Gt,
left: Ident("x"),
right: Int(5),
},
then_branch: [
Expr(Ident("x")),
],
else_branch: Some(
Block([
Expr(Int(0)),
]),
),
}let文とif/else文が、それぞれ想定通りの構造でパースされています。1 + 2 * 3の優先順位も式のパーサ実装時と変わらず正しく処理されており、字句解析・構文解析という2つの独立したフェーズがそのまま組み合わさって動作していることが確認できます。
備考
代入文はまだ実装していない
let x = 1;のような変数宣言は実装しましたが、x = 2;のように既存の変数へ再代入する文はまだ実装していません。理由は、この言語で変数を可変（mutable）にするかどうか、するとしてどのような構文にするか（Rustのようにlet mutで明示するか、デフォルトで可変にするかなど）を、まだ検討していないためです。字句解析の時点で=（TokenKind::Eq）はトークンとして用意済みで、let文の中では既に使っていますが、式の中で代入演算子として使う設計はまだ確定していません。可変性の設計は、この後の静的型検査のフェーズで型システム全体の方針と合わせて検討する予定です。
StmtとExprを分けたことで、式文（Stmt::Expr）という一見回りくどい表現が必要になった
x;やadd(1, 2);のように、式をそのまま文として書きたい場面があります。StmtとExprを完全に別の型にした以上、こうした「式単体からなる文」を表現するにはStmt::Expr(Expr)という、Exprを1段ラップしただけのケースが必要になります。一見冗長に見えますが、これはStmtとExprの役割を型で厳密に分離したことの必然的な帰結です。もしStmtとExprを1つの型にまとめていたら、Stmt::Exprというラップは不要になる代わりに、「if文が値の一部として使われる」ような、この言語では意図していない構造まで型上表現できてしまいます（Rustはまさにこちらの設計で、ifが式になり、ブロックの最後の式が値になります）。この言語では既に述べた通り「ブロック末尾の式がそのまま戻り値になる」仕組みを採用しないと決めているため、式文というラップの手間を払ってでも、式と文を型として明確に分離する設計を選びました。