構文解析をやってみる

字句解析ができたので、次は構文解析器の制作に取り掛かります。

どうやって作ろう？

買った 2 冊の書籍には、

再帰下降構文解析
パーサコンビネータのソースコード

が載っていました。ちなみに、開発言語が C# であることと、実際の動きを見ながらやってみたいこともあり、yacc などのツールは使わないことにしました。作る言語のことを考えると、パーサコンビネータを C# でまるっと実装するのが良さそうですが、こちらもまずは動作の理解を深めるために、簡単な構文を再帰下降構文解析を使って解析するコードを作成しようと思います。

解析の前に、終端記号と非終端記号の用語の定義を…

表1: 終端記号と非終端記号

終端記号	それ以上分解されない記号 ≒ トークン
非終端記号	置換されうる記号 ≒ 定義していくやつ

再帰下降構文解析

文法として、左再帰を持たず、一個のトークンの先読みで判断できるような文法になっていれば、解析できるようです。そもそもこの辺をあまり理解していないのですが、いろいろやってみて、だめになったら考えます。（ちなみに、2 週間でできる ! の方では、四則演算のところだけ順位を決めて解析する方法が載っていました。これが終わったらやってみようと思います。）なお、世の中のパーサジェネレータを見ると、LL 法のものが結構あり、先読みの数を増やせばそれなりに実用性があるようです。

左再帰は厳密な定義はよくわからないのですが、こちらによると「A → Aa|b」のように、同じ非終端記号が一番左にいきなり現れるようなやつです。これは、文法の定義の仕方で解消できるようです（やりかたが書いてありましたが、ぱっと見では理解できませんでした）。一個のトークンの先読みで判断できるような文法は、文字通りです。（ぱっと思いついた感じですと、ジェネリクスの構文で List<string が、List<string> なのか、List < string という比較演算なのかの判断つかないように思いましたが、やってみないとわからないですね。ちょっと調べた参考はこちら）

ここまでを心に留めて、以下の構文解析を作ってみようと思います。

左再帰をもうちょっと調べてみた

Wikipedia にアルゴリズムが載っていました（こちら）。アルゴリズム自体は意味がわからなかったのですが、手続きはこちらの感じでできました。ただ、生成される木の結合方向が変わるそうで、あまり良くないようです。Wikipedia には、" 再帰ではなくループで繰り返しを実現する文法に書き換える（拡張 BNF などによる構文規則では * を使って表現できる。手続き型の実装には、綺麗に演算子の左結合性も含め変換できる）。" と書いてあったため、ひとまずは、それにしたがおうと思います。（左再帰が起きないように注意する方針）

構文の話にもどる

さて、ここでもう一度、読んでいる本を見比べてみました。

再帰下降構文解析のアルゴリズムについては、2. の方で詳しく説明されていたのですが、残念ながらそちらの本では構文が左再帰バリバリの BNF で解説されていました（この本は yacc を使うので良いのですが）。アルゴリズムの解説のところでは、BNF が一度構文図に置き換えられて、その後構文図に書き直すときになんか表現が変わっていました。

一方、1. の方では繰り返し規則などを使って構文が定義されていたため、構文については、1. の方を見つつ、プログラムを書くときは 2. の方と Wikipedia を参考にしながら進めることにしました。なお、1. の方でも、演算子の優先度は別の方法で解決していたため、再帰下降構文解析をバリバリ手書きでやるのは、最初の四則演算 + αくらいまでにしておき、感覚的にわかったところで 1. の本のパーサコンビネータのところを読みながらシステムを作ろうかと思います。

つくる

以前、ブログに貼ったこちらの構文を作ってみます。忘れているので、メタ記号も再掲

表2: メタ記号

記号	意味
{ }	カッコ内が 0 回以上の繰り返しと一致
[ ]	カッコ内が 0 回または 1 回一致
a \| b	a または b
()	カッコ内をひとまとまりとする

factor: 	NUMBER | "(" expression ")"
term:		factor { ("*" | "/") factor }
expression:	term { ("+" | "-") term }

こちらを実装したのが以下のコードです。前回作った字句解析器を少し改造して、先読みができるようになっています。また、ファイルの終端では、終端のトークンが返るように変更されています。

解析のコード自体は、上の EBNF の内容をそのまま関数にしただけでした。明日にでも、変換の手順をまとめようと思います。これくらいなら、パーサジェネレータを書けそうです。

using SumireScriptLib.LexicalAnalyzer;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SumireScriptLib.Parser
{
    public class SsParser
    {
        SsLexicalAnalyzer la;

        public SsParser(TextReader reader)
        {
            la = new SsLexicalAnalyzer(reader);
        }

        public SsASTree Parse()
        {
            SsASTree ret = m_expression();

            if (la.PeekToken(0).TokenType != SsTokenType.EndOfCode)
            {
                throw new SsSyntaxErrorException(
                    string.Format("なんかおかしいはず {0}", la.PeekToken(0)));
            }

            return ret;
        }


        private SsASTree m_factor()
        {
            // factor: 	NUMBER | "(" expression ")"

            SsToken first = la.PeekToken(0);

            if (first.TokenType == SsTokenType.Number)
            {
                return new SsASTree(la.GetToken());
            }
            else if (first.TokenType == SsTokenType.Bk_LR)
            {
                SsASTree tree = new SsASTree("factor");

                tree.Add(new SsASTree(la.GetToken()));
                tree.Add(m_expression());

                SsToken close = la.GetToken();
                if (close.TokenType == SsTokenType.Bk_RR)
                {
                    tree.Add(new SsASTree(close));
                }
                return tree;
            }

            throw new SsSyntaxErrorException(string.Format("factor {0}", first));
        }


        private SsASTree m_term()
        {
            // term:		factor { ("*" | "/") factor }

            SsASTree tree = new SsASTree("term");

            SsASTree factor = m_factor();
            tree.Add(factor);

            SsToken next = la.PeekToken(0);

            while (next.TokenType == SsTokenType.Op_Astarisk ||
                next.TokenType == SsTokenType.Op_Slash)
            {
                tree.Add(new SsASTree(la.GetToken()));
                tree.Add(m_factor());

                //2項演算っぽくなるように
                SsASTree nTree = new SsASTree("expression");
                nTree.Add(tree);
                tree = nTree;

                next = la.PeekToken(0);
            }

            return tree;
        }



        private SsASTree m_expression()
        {
            //  expression:	term { ("+" | "-") term }

            SsASTree tree = new SsASTree("expression");

            SsASTree term = m_term();
            tree.Add(term);
            SsToken next = la.PeekToken(0);
            
            while (next.TokenType == SsTokenType.Op_Plus ||
                next.TokenType == SsTokenType.Op_Minus)
            {
                tree.Add(new SsASTree(la.GetToken()));
                tree.Add(m_term());

                //2項演算っぽくなるように
                SsASTree nTree = new SsASTree("expression");
                nTree.Add(tree);
                tree = nTree;

                next = la.PeekToken(0);
            }
            
            return tree;
        }

    }


    public class SsASTree
    {
        public List<SsASTree> children = new List<SsASTree>();
        public SsToken token;
        public string name = null;


        public SsASTree(string name)
        {
            this.name = name;
        }

        public SsASTree(SsToken token)
        {
            this.token = token;
        }

        public void Add(SsASTree ch)
        {
            children.Add(ch);
        }

        public override string ToString()
        {
            if (name == null)
            {
                if (token != null)
                {
                    return token.ToString();
                }
            }
            return string.Format("{0}[{1}]", name, children.Count);
        }

        public void Print(StringWriter sw, int depth = 0)
        {
            for (int i = 0; i < depth; i++)
            {
                sw.Write("    ");
            }
            sw.WriteLine(this.ToString());

            foreach (SsASTree child in children)
            {
                child.Print(sw, depth + 1);
            }

        }

        public float Calc()
        {
            if (string.IsNullOrEmpty(name))
            {
                if (token.TokenType == SsTokenType.Number)
                {
                    return float.Parse(token.Text);
                }
            }

            if (string.Equals(name, "factor"))
            {
                if (children.Count == 1)
                {
                    return children[0].Calc();
                }
                else if(children.Count == 3)
                {
                    return children[1].Calc();
                }
            }
            else if (string.Equals(name, "term"))
            {
                if (children.Count >= 1)
                {
                    float val = children[0].Calc();

                    //子供が4以上になってもOK
                    for (int i = 1; i < children.Count; i += 2)
                    {
                        if (children[i].token.TokenType == SsTokenType.Op_Astarisk)
                        {
                            val *= children[i + 1].Calc();
                        }
                        else if (children[i].token.TokenType == SsTokenType.Op_Slash)
                        {
                            val /= children[i + 1].Calc();
                        }
                    }

                    return val;
                }

            }
            else if (string.Equals(name, "expression"))
            {
                if (children.Count >= 1)
                {
                    float val = children[0].Calc();
                    for (int i = 1; i < children.Count; i+=2)
                    {
                        if (children[i].token.TokenType == SsTokenType.Op_Plus)
                        {
                            val += children[i + 1].Calc();
                        }
                        else if (children[i].token.TokenType == SsTokenType.Op_Minus)
                        {
                            val -= children[i + 1].Calc();
                        }
                    }

                    return val;
                }

            }


            throw new SsException(string.Format("CalcError {0}", this));
        }
    }
}

はじめは繰り返し部分をそのままの順で子供に入れていたのですが、貼ったコードでは、左側のから枝になるようにしてみました。演算の実行は、本当は ASTree クラスのサブクラスとかにしてオーバーライドでやるべきなんでしょうが、とりあえず、if 文で分岐でやっています。

この Parser に、

((6 + 8) * 7 + 8 - 7) / 9 / 3

を入れると以下のような感じになります。計算は合っているようです。

expression[1]
    expression[1]
        expression[3]
            term[3]
                factor[3]
                    Bk_LR[1:0-1,1] (
                    expression[1]
                        expression[3]
                            expression[3]
                                expression[1]
                                    term[3]
                                        factor[3]
                                            Bk_LR[1:1-1,2] (
                                            expression[1]
                                                expression[3]
                                                    term[1]
                                                        Number[1:2-1,3] 6 (Integer)
                                                    Op_Plus[1:4-1,5] +
                                                    term[1]
                                                        Number[1:6-1,7] 8 (Integer)
                                            Bk_RR[1:7-1,8] )
                                        Op_Astarisk[1:9-1,10] *
                                        Number[1:11-1,12] 7 (Integer)
                                Op_Plus[1:13-1,14] +
                                term[1]
                                    Number[1:15-1,16] 8 (Integer)
                            Op_Minus[1:17-1,18] -
                            term[1]
                                Number[1:19-1,20] 7 (Integer)
                    Bk_RR[1:20-1,21] )
                Op_Slash[1:22-1,23] /
                Number[1:24-1,25] 9 (Integer)
            Op_Slash[1:26-1,27] /
            Number[1:28-1,29] 3 (Integer)

Result = 3.666667

超見づらいので、木のビジュアライザも欲しくなりますね。

参考にしたサイト

LL(1) 構文解析 - いらずんば