Compiler/Syntax Analysis

Compiler/Syntax Analyzer

コード

タスク概要

シンプルなプログラミング言語用の Syntax Analyzer を作る。

入力は Compiler/Lexical Analyzer での出力形式に基づいたトークン列のテキスト。

実装

yacc 使おうぜ、yacc。と言いたくなる気も少しあるけど、真面目に実装する。そもそも C 言語じゃないしね。

Rosetta Code のページには pseudo code があって、それでは再帰下降パーザと演算子優先順位パーザの組み合わせが使われていたので、それに倣うことにする。Rosetta Code は同じ問題を色々な言語で実装して比較できるようにするのも目的だし、あえて本流に逆らう必要もない。

エラー

Lexical Analyzer のときに用意したエラーを拡張する。具体的には ErrorKind に SyntaxError を追加する。

#[derive(Debug)]
pub enum ErrorKind {
    LexicalAnalyzerError,
}

本来ならタスクの独立性を高めるためにこのタスク専用にコードを用意すべきなのだろうが、面倒なのでやめておく。Token に関しても同様。

これにともない、Cargo.toml の [dependency] に lexical_anzlyer を追加。

[dependencies]
lexical_analyzer = {path="../lexical_analyzer"}

pub struct ASTNode {
    pub(crate) kind: NodeKind,
    pub(crate) lhs: Option<Box<ASTNode>>,
    pub(crate) rhs: Option<Box<ASTNode>>,
}

メンバを見ればわかると思うが、ごく普通の二分木。lhs と rsh はそれぞれ Left Hand Side, Right Hand Side を意味しているが、left, right の方がわかりやすかったかもしれない。

NodeKind は task のページで定義されているノードの種類をそのまま持ってきた。

pub enum NodeKind {
    Identifier(String),
    String(String),
    Integer(i32),
    Sequence,
    If,
    Prtc,
    Prts,
    Prti,
    While,
    Assign,
    Negate,
    Not,
    Multiply,
    Divide,
    Mod,
    Add,
    Subtract,
    Less,
    LessEqual,
    Greater,
    GreaterEqual,
    Equal,
    NotEqual,
    And,
    Or,
    None,
}

唯一 "None" を加えたが、これは演算子優先順位構文解析でのみ使用する。

解析部

今回のタスクでは与えられたトークン列に対して一度に解析を行い、AST を出力することから、SyntaxAnalyzer::parse() のみを pub にして構造体としての SyntaxAnalyzer は見えないようにする。
SyntaxAnalyzer::parse() の signature は

    pub fn parse(mut token_iter: IntoIter<Token>) -> Result<ASTNode>

で、入力としてのトークン列は内部で Iterator の形でアクセスする。本来はエラーを起こす可能性のある Lexical Analyzer からトークンを得るため Iterator はふさわしくないが、このタスクでは Lexical Analyzer による字句解析は済んで問題がなかったトークン列のみを扱うため、この形で入力を受けるようにした。

結果として SyntaxAnalyzer は

pub struct SyntaxAnalyzer {
    token_iter: IntoIter<Token>,
    next_token: Token,
}

のようになった。next_token に関しては次項を参照。

トークン先読み

前述のように、このタスクでは全てのトークン列が生成済みの状態で構文解析を行うため、解析時には全トークンが既知になっている。よってこのようにする意味はあまりないのだけれど、 1 トークン先読みを行う。

SyntaxAnalyzer の next_token はこの先読みをしたトークン。先読みの処理は以下の通り。

    fn read_token(&mut self) -> Result<Token> {
        let next_token = self.token_iter.next();
        match next_token {
            Some(t) => Ok(std::mem::replace(&mut self.next_token, t)),
            None => Err(CompileError::new(ErrorKind::SyntaxError, "unexpected EOF")),
        }
    }

Lexical Analyzer での一文字先読みと大体似た感じだが、大きな違いとしてトークン先読み時に replace で前に先読みしていたトークンを返すようにしている。これは Lexical Analyze では Copy を実装した char のみを扱っていたため不要だったことによる。

Syntax Analyer で扱うのはトークン列で、その店には Identifier のように String の値を持っている場合がある。そして、その値は AST でも使用する。そのため、一旦 Syntax Analyzer から ownership を手放して ASTNode に渡したい。

というわけで、トークンを消費時に read_token() を呼ぶと、先読みをすると同時に replace で消費したトークンの ownership を手放して return している。

再帰降下構文解析

task の文法を見ると、左再帰がないことが簡単に確認できることから、再帰降下構文解析による解析が可能だとわかる。

再帰降下構文解析では生成規則にのっとってコードを書き下ろすだけで良いため、手書きでもそんなに苦労せずに書ける。一例として stmt から生成される if 文

'if' paren_expr stmt ['else' stmt]

の解析部の概形を示すと、

        // 'if'
        if *self.next_token.kind() != TokenKind::KeywordIf {
            return Err(CompileError::new(
                ErrorKind::ParseError,
                "\"if\" is expected.",
            ));
        }
        self.read_token()?;

        // paren_expr
        let condition = self.parse_paren_expr()?;

        // stmt
        let if_clause = Some(Box::new(self.parse_stmt()?));
        
        // 'else'
        let else_clause = if *self.next_token.kind() == TokenKind::KeywordElse {
            self.read_token()?;
            // stmt
            Some(Box::new(self.parse_stmt()?))
        } else {
            None
        };
    }

というように生成規則に則って、順に解析をしているだけとわかる。

後はこれに AST を構築する部分を付け加えていく。そのためには各文でどのような部分木を構築すべきかを理解しておく必要がある。二分木ということもあってか タスクのページでは S 式で書かれているため、Lisp 等を知らないと少し読みにくいかもしれない。というわけで図示すると、

となる。解析時にこの形の部分木を構築する。よって if 文を解析する parse_if_stmt() は以下の通り。

    fn parse_if_stmt(&mut self) -> Result<ASTNode> {
        if *self.next_token.kind() != TokenKind::KeywordIf {
            return Err(CompileError::new(
                ErrorKind::ParseError,
                "\"if\" is expected.",
            ));
        }
        self.read_token()?;

        let condition = self.parse_paren_expr()?;
        let mut node = ASTNode {
            kind: NodeKind::If,
            lhs: Some(Box::new(condition)),
            rhs: None,
        };

        let if_clause = Some(Box::new(self.parse_stmt()?));
        let else_clause = if *self.next_token.kind() == TokenKind::KeywordElse {
            self.read_token()?;
            Some(Box::new(self.parse_stmt()?))
        } else {
            None
        };

        node.rhs = Some(Box::new(ASTNode {
            kind: NodeKind::If,
            lhs: if_clause,
            rhs: else_clause,
        }));

        Ok(node)
    }

他も似た感じで解析を行っている。特殊なことはやっていないので難しくはないけれど、print のみは見た目と構築される AST の間に少し開きがある。例として

print("abc", 42, "def");

を考える。このとき、String である "abc" と "def" に対しては Prts のノードを作り、42 に対しては Prti ノードを作る。よって、print トークンを見た時点ではどのような部分木を構築するかを決められず、prt_list の解析時に構築することになる。

そして、先述の print を解析して得られるべき AST は

である。つまりは print を解析しているというよりも ptr_list を解析している感覚になる。

実際の処理は

    fn parse_prt_list(&mut self) -> Result<ASTNode> {
        let node = match self.next_token.kind() {
            TokenKind::String(_) => ASTNode {
                kind: NodeKind::Prts,
                lhs: Some(Box::new(self.make_string_node()?)),
                rhs: None,
            },
            _ => ASTNode {
                kind: NodeKind::Prti,
                lhs: Some(Box::new(self.parse_expr()?)),
                rhs: None,
            },
        };

        let mut lhs = ASTNode {
            kind: NodeKind::Sequence,
            lhs: None,
            rhs: Some(Box::new(node)),
        };

        while *self.next_token.kind() == TokenKind::Comma {
            self.read_token()?;

            let node = match self.next_token.kind() {
                TokenKind::String(_) => ASTNode {
                    kind: NodeKind::Prts,
                    lhs: Some(Box::new(self.make_string_node()?)),
                    rhs: None,
                },
                _ => ASTNode {
                    kind: NodeKind::Prti,
                    lhs: Some(Box::new(self.parse_expr()?)),
                    rhs: None,
                },
            };

            lhs = ASTNode {
                kind: NodeKind::Sequence,
                lhs: Some(Box::new(lhs)),
                rhs: Some(Box::new(node)),
            };
        }
        Ok(lhs)
    }

となり、先読みしたトークンを基に Prts と Prti のどちらのノードを作るかを決めている。

他の非終端記号も同様の処理をしているだけなので、ソースを参照。

終端記号の扱いにおいて注意すべきは Identifier、もしくは String トークン。両者とも String 型の値を持っており、AST 構築時にその値をトークンから ASTNode に move させる必要がある。

Identfier の処理を以下に示す。

        let Token { kind, .. } = self.read_token()?;
        match kind {
            TokenKind::Identifier(identifier) => Ok(ASTNode {
                kind: NodeKind::Identifier(identifier),
                lhs: None,
                rhs: None,
            }),

read_token() で SyntexAnalyzer に現在のトークン(Identifier トークン)の ownership を手放させてから ASTNode に move している。同様の処理は String トークンでも行っており、そちらは make_string_node() を参照。

演算子優先順位構文解析

expr の解析では演算子優先順位構文解析を使う。これはその名前の通り各演算子が持つ優先順位に基づいて解析を行う。そのため、事前に優先順位の値を決めておく。

解析対象となるのは expr, and_expr, equality_expr, relational_expr, additional_expr および multiplication_expr。そして後に書いたものほど優先順位が高い。よって、各 expr で用いる演算子に優先順位を割り当てると、

    // or
    const OR: Operator = Operator {
        kind: NodeKind::Or,
        right_associative: false,
        precedence: 10,
    };
    // and
    const AND: Operator = Operator {
        kind: NodeKind::And,
        right_associative: false,
        precedence: 20,
    };
    // equality
    const EQUAL: Operator = Operator {
        kind: NodeKind::Equal,
        right_associative: false,
        precedence: 30,
    };
    const NOT_EQUAL: Operator = Operator {
        kind: NodeKind::NotEqual,
        right_associative: false,
        precedence: 30,
    };
    // relational
    const LESS: Operator = Operator {
        kind: NodeKind::Less,
        right_associative: false,
        precedence: 40,
    };
    const LESS_EQUAL: Operator = Operator {
        kind: NodeKind::LessEqual,
        right_associative: false,
        precedence: 40,
    };
    const GREATER: Operator = Operator {
        kind: NodeKind::Greater,
        right_associative: false,
        precedence: 40,
    };
    const GREATER_EQUAL: Operator = Operator {
        kind: NodeKind::GreaterEqual,
        right_associative: false,
        precedence: 40,
    };
    // addition
    const ADD: Operator = Operator {
        kind: NodeKind::Add,
        right_associative: false,
        precedence: 50,
    };
    const SUBTRACT: Operator = Operator {
        kind: NodeKind::Subtract,
        right_associative: false,
        precedence: 50,
    };
    // multiplication
    const MULTIPLY: Operator = Operator {
        kind: NodeKind::Multiply,
        right_associative: false,
        precedence: 60,
    };
    const DIVIDE: Operator = Operator {
        kind: NodeKind::Divide,
        right_associative: false,
        precedence: 60,
    };
    const MOD: Operator = Operator {
        kind: NodeKind::Mod,
        right_associative: false,
        precedence: 60,
    };
    // sentinel として使うため、 precedence -1
    const NOT_OPERATOR: Operator = Operator {
        kind: NodeKind::None,
        right_associative: false,
        precedence: -1,
    };

となる。優先順位を示す値は precedence で、大きい値になるほど優先順位が高くなる。優先順位の値が 10 刻みであることに深い意味はない。ただ、なんとなく。

right_associative は演算子の結合規則が右結合であることを示すためのものだが、今回対象とする言語において全ての演算子は左結合であるため何の意味も持たない。

    ///  演算子優先順位パーザで式を解析する
    fn parse_expr(&mut self) -> Result<ASTNode> {
        let lhs = self.parse_primary()?;
        self.parse_expr_body(lhs, 0)
    }

    fn parse_expr_body(&mut self, node: ASTNode, min_precedence: i32) -> Result<ASTNode> {
        let mut lhs = node;

        let mut next_op = operator(self.next_token.kind());
        while next_op.precedence >= min_precedence {
            let op = next_op;
            self.read_token()?;

            let mut rhs = self.parse_primary()?;
            next_op = operator(self.next_token.kind());

            while next_op.precedence > op.precedence
                || ((next_op.precedence == op.precedence) && next_op.right_associative)
            {
                rhs = self.parse_expr_body(rhs, next_op.precedence)?;
                next_op = operator(self.next_token.kind());
            }

            lhs = ASTNode {
                kind: op.kind.clone(),
                lhs: Some(Box::new(lhs)),
                rhs: Some(Box::new(rhs)),
            };
        }

        Ok(lhs)
    }

parse_expr_body() が解析本体。

処理は二重ループを基本としている。まず、外側のループのみを考える。

        let mut lhs = node;

        let mut next_op = operator(self.next_token.kind());
        while next_op.precedence >= min_precedence {
            let op = next_op;
            self.read_token()?;

            let mut rhs = self.parse_primary()?;
            next_op = operator(self.next_token.kind());

            lhs = ASTNode {
                kind: op.kind.clone(),
                lhs: Some(Box::new(lhs)),
                rhs: Some(Box::new(rhs)),
            };
        }

このループでは以下のような木を構築する。 一方、内側のループ

            while next_op.precedence > op.precedence
                || ((next_op.precedence == op.precedence) && next_op.right_associative)
            {
                rhs = self.parse_expr_body(rhs, next_op.precedence)?;
                next_op = operator(self.next_token.kind());
            }

では逆に以下のような木を構築する。

つまり、外側のループで左結合を、内側のループで右結合を実現している。とはいえ、それだと右結合の中でさらに左結合といったケースを扱えない。それを処理しているのが、内側のループにある parse_expr_body() の再帰呼出しになっている。

余談

ここで生成した AST が続く Compiler/AST interpreter と Compiler/Code Generator の中心的役割を果たす...はず。