字句解析をやってみる

プログラミング言語を作る的な本を 2 冊読み中ですが、そろそろ手元にコードがないとピンとこなくなってきたため、とりあえず作り始めようと思いました。

まずは、字句解析器（Lexical Analyzer）です。Lex を試してみてもよいのですが、自前でもそう大変そうではないので作ってみることにしました。さて、何で書くかなのですが…一番慣れている C# でやろうと思います。まぁ、一度作ってしまえば、多言語への移植も大変ではないですし。また、正規表現は書いていると頭が痛くなっているので、極力使わず。数値のリテラル部分などは、片方の本に載っていたオートマトンの話を使おうと思います。

本を 2 冊読むと、ちょっとずつ方針が違ったのですが、字句解析器に必要な機能としては、

GetToken 的なメソッドで 1 トークンを取り出せるようにする
トークンの先読みができるようにする

の 2 つがあれば良いようです。

片方の本では、整数リテラル・文字リテラル・識別子の 3 種類のみを考え、キーワード（if とか）や演算子は識別子に含めてしまう方式でやっていましたが、こちらはあまりしっくりこなかったので、キーワードや演算子は識別子と別物扱いし、キーワードや演算子も種類分けする方針で作ろうと思います。実装では、この前やった CodeMirror の Mode の stream オブジェクトも参考にします。

表1: stream にほしいメソッド

メソッド	動作
string Peek()	ストリームを進めずに次の一文字を読み取ります。終端の場合 null を返します。
string Next()	次の一文字を読み取り、ストリームを 1 文字進めます。終端の場合 null を返します。
void SkipToLineEnd()	ストリームを行末へ進めます。
bool IsSpace(char c)	c がスペースなら true を返します。
void SkipSpace()	スペースを読み飛ばします。
bool Match(string pattern, bool advance = true)	文字列が一致したら true を返す。一致して advance が true なら、文字分進める

そのほか、stream では、現在の行数と何文字目かもカウントするようにします。基本方針は、Match で長い文字列のキーワードや演算子から一致を確認していって、一致しなかったら、各種リテラルの解析を始めるという感じにします。コメントや文字リテラルに入った場合はステートを変更して、その解析をやっていく感じです。

この辺りは、漠然と頭にはあったのですが、本と CodeMirror の Mode 周りの実装を見て、考えがまとまりました。（このサイトの実装を始めてから、頭でぐるぐるしていたことがスッキリしました）

さて、考えるのはこの辺にして、実装を始めようと思います…

できた

もきょもきょやったらできました。書いたコードを食わせてみたら、それなりに動きました。

将来的に 4 バイト文字にも対応できるように、string でやっています。そのほか、ループが多く処理効率が悪い気もしますが、気にならない速度で動くでしょう。ぐしゃぐしゃっと書いたので、どっかにバグがあると思いますが、ひとまず先に進めそうです。次は、構文解析器を作ってみようと思います。

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

namespace SumireScriptLib.LexicalAnalyzer
{
    public class SsLexicalAnalyzer
    {
        SsStreamReader ssReader;

        List<SsKeyword> kws = new List<SsKeyword>();
        List<SsKeyword> operators = new List<SsKeyword>();
        List<SsKeyword> marks = new List<SsKeyword>();

        public SsLexicalAnalyzer(TextReader reader)
        {
            if (reader == null)
            {
                throw new SsException("TextReader が null です。");
            }

            ssReader = new SsStreamReader(reader);
            registerKeywords();
        }

        //識別子で使えない記号
        string exIdentifier = "+-*/^?\\:;.,'\"()[]{}<>!#$%&|=~`@ \t\r\n";
        List<string> cantUserList = new List<string>();

        private void registerKeywords()
        {
            kws.Add(new SsKeyword("if", SsTokenType.Kw_IF));
            kws.Add(new SsKeyword("for", SsTokenType.Kw_FOR));
            kws.Add(new SsKeyword("while", SsTokenType.Kw_WHILE));
            kws.Add(new SsKeyword("return", SsTokenType.Kw_RETURN));
            kws.Add(new SsKeyword("continue", SsTokenType.Kw_CONTINUE));
            kws.Add(new SsKeyword("break", SsTokenType.Kw_BREAK));
            kws.Add(new SsKeyword("class", SsTokenType.Kw_CLASS));
            kws.Add(new SsKeyword("struct", SsTokenType.Kw_STRUCT));
            kws.Add(new SsKeyword("enum", SsTokenType.Kw_ENUM));
            kws.Add(new SsKeyword("null", SsTokenType.Kw_NULL));
            kws.Add(new SsKeyword("new", SsTokenType.Kw_NEW));

            //演算子
            operators.Add(new SsKeyword("+", SsTokenType.Op_Plus));
            operators.Add(new SsKeyword("-", SsTokenType.Op_Minus));
            operators.Add(new SsKeyword("*", SsTokenType.Op_Astarisk));
            operators.Add(new SsKeyword("/", SsTokenType.Op_Slash));
            operators.Add(new SsKeyword("^", SsTokenType.Op_Hat));
            operators.Add(new SsKeyword("%", SsTokenType.Op_Percent));

            operators.Add(new SsKeyword("=", SsTokenType.Op_Substitution));

            operators.Add(new SsKeyword("!", SsTokenType.Op_Not));
            operators.Add(new SsKeyword("==", SsTokenType.Op_Equal));
            operators.Add(new SsKeyword(">=", SsTokenType.Op_GT_Equal));
            operators.Add(new SsKeyword("<=", SsTokenType.Op_LT_Equal));
            operators.Add(new SsKeyword("!=", SsTokenType.Op_Not_Equal));
            operators.Add(new SsKeyword("&&", SsTokenType.Op_And));
            operators.Add(new SsKeyword("||", SsTokenType.Op_Or));


            operators.Add(new SsKeyword("++", SsTokenType.Op_Increment));
            operators.Add(new SsKeyword("--", SsTokenType.Op_Decrement));

            operators.Add(new SsKeyword("+=", SsTokenType.Op_AddEq));
            operators.Add(new SsKeyword("-=", SsTokenType.Op_SubEq));
            operators.Add(new SsKeyword("*=", SsTokenType.Op_MulEq));
            operators.Add(new SsKeyword("/=", SsTokenType.Op_DivEq));


            //記号
            marks.Add(new SsKeyword(":", SsTokenType.Colon));
            marks.Add(new SsKeyword(";", SsTokenType.SemiColon));
            marks.Add(new SsKeyword(".", SsTokenType.Period));
            marks.Add(new SsKeyword(",", SsTokenType.Comma));
            marks.Add(new SsKeyword("'", SsTokenType.Quote));
            marks.Add(new SsKeyword("\"", SsTokenType.D_Quote));

            //カッコ
            marks.Add(new SsKeyword("(", SsTokenType.Bk_LR));
            marks.Add(new SsKeyword(")", SsTokenType.Bk_RR));
            marks.Add(new SsKeyword("[", SsTokenType.Bk_LS));
            marks.Add(new SsKeyword("]", SsTokenType.Bk_RS));
            marks.Add(new SsKeyword("<", SsTokenType.Bk_LA));
            marks.Add(new SsKeyword(">", SsTokenType.Bk_RA));
            marks.Add(new SsKeyword("{", SsTokenType.Bk_LB));
            marks.Add(new SsKeyword("}", SsTokenType.Bk_RB));

            //文字の長さ順にソート
            kws.Sort(delegate (SsKeyword s1, SsKeyword s2)
            {
                return s2.keyword.Length - s1.keyword.Length;
            });
            operators.Sort(delegate (SsKeyword s1, SsKeyword s2)
            {
                return s2.keyword.Length - s1.keyword.Length;
            });
            marks.Sort(delegate (SsKeyword s1, SsKeyword s2)
            {
                return s2.keyword.Length - s1.keyword.Length;
            });

            for (int i = 0; i < exIdentifier.Length; i++)
            {
                cantUserList.Add(exIdentifier[i].ToString());
            }
        }

        private bool isIdentifierUseable(string c)
        {
            if (c == null)return false;

            foreach (string mark in cantUserList)
            {
                if (string.Equals(c, mark)) return false;
            }

            return true;
        }

        StringBuilder sb = new StringBuilder();
        public SsToken GetToken()
        {
            SsToken token = getToken();

            if (token != null)
            {
                //終了位置を設定
                token.SetEndPos(ssReader);
            }

            return token;
        }

        private SsToken getToken()
        {
            sb.Clear();

            ssReader.SkipSpace();
            string c = ssReader.Peek(); //スペース読み飛ばしたら最後に行く可能性もあるので、ここで判定
            if (c == null) return null;

            //行コメント
            while (ssReader.Match("//"))
            {
                ssReader.SkipToLineEnd();
                ssReader.SkipSpace();
                 c = ssReader.Peek();
                if (c == null) return null;
            }

            //コメント
            if (ssReader.Match("/*"))
            {
                while (!ssReader.Match("*/"))
                {
                    ssReader.Next();
                    c = ssReader.Peek();
                }
                //再帰にしてみた
                return getToken();
            }



            int l = ssReader.Line;
            int ch = ssReader.Ch;
            

            if (isDigit(c))
            {
                SsTokenNumber numToken = null;
                //数値系のリテラルを確認
                if (ssReader.Match("0x"))
                {
                    c = ssReader.Peek();
                    while (isHexDigit(c))
                    {
                        if (!string.Equals(c, "_"))
                        {
                            sb.Append(c);
                        }
                        ssReader.Next();
                        c = ssReader.Peek();
                    }
                    if (string.IsNullOrEmpty(sb.ToString()))
                    {
                        throw new SsLexicalAnalyzeException("リテラルが不正です", ssReader.Line, ssReader.Ch);
                    }

                    numToken = new SsTokenNumber(SsTokenNumberType.Hex, sb.ToString(), l, ch);

                }
                else if (ssReader.Match("0b"))
                {
                    c = ssReader.Peek();
                    while (isBinaryDigit(c))
                    {
                        if (!string.Equals(c, "_"))
                        {
                            sb.Append(c);
                        }
                        ssReader.Next();
                        c = ssReader.Peek();
                    }
                    if (string.IsNullOrEmpty(sb.ToString()))
                    {
                        throw new SsLexicalAnalyzeException("リテラルが不正です", ssReader.Line, ssReader.Ch);
                    }
                    numToken = new  SsTokenNumber(SsTokenNumberType.Binary, sb.ToString(), l, ch);

                }
                else
                {
                    while (isDigit(c))
                    {
                        sb.Append(c);
                        ssReader.Next();
                        c = ssReader.Peek();
                    }
                    if (string.Equals(c, ".")) // 少数点
                    {
                        sb.Append(c);
                        ssReader.Next();

                        // 1. 表記を許すか? 許してみよう
                        c = ssReader.Peek();
                        while (isDigit(c))
                        {
                            sb.Append(c);
                            ssReader.Next();
                            c = ssReader.Peek();
                        }
                        numToken = new SsTokenNumber(SsTokenNumberType.Float, sb.ToString(), l, ch);
                    }
                    else
                    {
                        numToken = new SsTokenNumber(SsTokenNumberType.Integer, sb.ToString(), l, ch);
                    }
                }

                if (numToken != null)
                {
                    c = ssReader.Peek();

                    //数字の後に、識別子で使える文字が続いてたらエラー
                    if (isIdentifierUseable(c))
                    {
                        throw new SsLexicalAnalyzeException("リテラルが不正です。数値リテラルに使用できない文字が使われています。", ssReader.Line, ssReader.Ch);
                    }
                    return numToken;
                }
            }
            else
            {

                //識別子を抜き出し
                if (isIdentifierUseable(c))
                {

                    //識別子かキーワード
                    while (isIdentifierUseable(c))
                    {
                        sb.Append(c);
                        ssReader.Next();
                        c = ssReader.Peek();
                    }
                    string identifier = sb.ToString();
                    foreach (SsKeyword kw in operators)
                    {
                        if (string.Equals(kw.keyword, identifier))
                        {
                            return new SsToken(kw.tokenType, identifier, l, ch);
                        }

                    }
                    return new SsToken(SsTokenType.Identifier, identifier, l, ch);
                }
                else if (string.Equals(c, "\""))
                {
                    //文字リテラルモード
                    ssReader.Next();

                    c = ssReader.Peek();
                    while (!string.Equals(c, "\""))
                    {
                        if (c == null)
                        {
                            throw new SsLexicalAnalyzeException("文字リテラルが閉じていません", ssReader.Line, ssReader.Ch);
                        }
                        if (string.Equals(c, "\n"))
                        {
                            throw new SsLexicalAnalyzeException("文字リテラルに改行は含められません", ssReader.Line, ssReader.Ch);
                        }

                        if (ssReader.Match("\\n"))
                        {
                            sb.Append("\n");
                        }
                        else if (ssReader.Match("\\r"))
                        {
                            sb.Append("\r");
                        }
                        else if (ssReader.Match("\\t"))
                        {
                            sb.Append("\t");
                        }
                        else if (ssReader.Match("\\\\"))
                        {
                            sb.Append("\\");
                        }
                        else if (ssReader.Match("\\\""))
                        {
                            sb.Append("\"");
                        }
                        else
                        {
                            if (string.Equals(c, "\\"))
                            {
                                throw new SsLexicalAnalyzeException("未知のエスケープシーケンスです", ssReader.Line, ssReader.Ch);
                            }
                            sb.Append(c);
                            ssReader.Next();
                        }
                        c = ssReader.Peek();
                    }
                    ssReader.Next();

                    return new SsToken(SsTokenType.Text, sb.ToString(), l, ch);
                }
                else if (string.Equals(c, "'"))
                {
                    //エスケープなし文字リテラルモード（ほんとにやるかは別）
                    ssReader.Next();
                    c = ssReader.Peek();
                    while (!string.Equals(c, "'"))
                    {
                        if (c == null)
                        {
                            throw new SsLexicalAnalyzeException("文字リテラルが閉じていません", ssReader.Line, ssReader.Ch);
                        }
                        sb.Append(c);
                        ssReader.Next();
                        c = ssReader.Peek();
                    }
                    ssReader.Next();

                    return new SsToken(SsTokenType.Text, sb.ToString(), l, ch);
                }
                else
                {
                    //演算子か、記号
                    foreach (SsKeyword op in operators)
                    {
                        if (ssReader.Match(op.keyword))
                        {
                            return new SsToken(op.tokenType, op.keyword, l, ch);
                        }

                    }

                    foreach (SsKeyword m in marks)
                    {
                        if (ssReader.Match(m.keyword))
                        {
                            return new SsToken(m.tokenType, m.keyword, l, ch);
                        }
                    }

                    //未知のトークン スペースまで切る
                    while (!ssReader.IsSpace(c))
                    {
                        sb.Append(c);
                        ssReader.Next();
                        c = ssReader.Peek();
                    }
                    return new SsToken(SsTokenType.Unknown, sb.ToString(), l, ch);
                }

            }
            return null;
        }

        private bool isDigit(string str)
        {
            if (str == null) return false;
            char c = str[0];
            return '0' <= c && c <= '9';
        }

        private bool isHexDigit(string str)
        {
            if (str == null) return false;
            char c = str[0];
            // 読みづらくなりがちなので "_" で切れるようにした
            return ('0' <= c && c <= '9') || ('a' <= c && c <= 'f') || ('A' <= c && c <= 'F') || c == '_';
        }

        private bool isBinaryDigit(string str)
        {
            if (str == null) return false;
            char c = str[0];
            // 読みづらくなりがちなので "_" で切れるようにした
            return '0' == c || '1' == c || c == '_';
        }

        class SsKeyword
        {
            public string keyword;
            public SsTokenType tokenType;

            public SsKeyword(string kw, SsTokenType type)
            {
                keyword = kw;
                tokenType = type;
            }

            public override string ToString()
            {
                return keyword + " : " + tokenType.ToString();
            }
        }
    }
}

字句解析をやってみる

できた

目次

アウトライン