関数型のテンプレートエンジンを作ってみる(0.2.1) - パース用のトークナイザを書く。

関数型のテンプレートエンジンを作ってみる(0.2) - スコープ・変数定義の導入 - terazzoの日記で定義したタグのパーサを書く。

パーサの実装にはJparsec*1を使用する。シンボルと属性名はJparsecに用意されているTerminals.Identifierを、属性値のExpressionにはTerminals.StringLiteral.DOUBLE_QUOTE_TOKENIZERを使用する。

とりあえずタグの部分をパースできるようにする。まずトークナイザ(というか字句解析部分)を書いてみる。

        String[] tags = new String[] {"insert", "define"};        // タグ名
        String[] opts = new String[] {"{", "}", "=", "/"};        // その他の記号部分
        Terminals terminals = Terminals.caseSensitive(opts, tags);

        Parser<Fragment> identifier = Terminals.Identifier.TOKENIZER;
        Parser<String> expression = Terminals.StringLiteral.DOUBLE_QUOTE_TOKENIZER;
        Parser<?> ignorable = Scanners.WHITESPACES;                // スペース類

        Parser<?> tagTokenizer =  Parsers.or(terminals.tokenizer(), identifier, expression);

次いでパーサの仮実装。まずはシングルタグの場合だけで、出力は仮にString型でnullを出すようにしておく。

        // 属性名=属性値の部分。
        // <attribute> ::= <identifier> "=" <identifier>
        //        | <identifier> "=" <doublequoted> ※区切り文字は省略
        Parser<String> attributeParser =
            Parsers.or(
                // 属性名=シンボル
                Parsers.sequence(
                    Terminals.Identifier.PARSER,
                    terminals.token("="),
                    Terminals.Identifier.PARSER,
                    new Map3<String, Token, String, String>() {
                        public String map(String name, Token op, String symbol) {
                            return null;
                        }
                    }
                ),
                // 属性名=Expression
                Parsers.sequence(
                    Terminals.Identifier.PARSER,
                    terminals.token("="),
                    Terminals.StringLiteral.PARSER,
                    new Map3<String, Token, String, String>() {
                        public String map(String name, Token op, String expression) {
                            return null;
                        }
                    }
                )
            );
        // シングルタグ: <signletag> ::= "{" <tagname> <attribute>* "/" "}" ※区切り文字は省略
        Parser<String> singleTagParser = 
            terminals.token("{").next(
                Parsers.sequence(
                    terminals.token(tags),
                    attributeParser.many(),
                    new Map2<Token, List<String>, String>() {
                        public String map(Token a, List<String> b) {
                            return null;
                        }
                    }
                )
            ).followedBy(terminals.token("/").next(terminals.token("}")));

組み合わせてパースしてみる。Jparsecのパーサは<構文解析部のパーサ>.from(<字句解析部のパーサ>, デリミタ)で作る。

        Parser<String> parser = singleTagParser.from(tagTokenizer, ignorable.skipMany());
        // パースしてみる(仮実装のため結果はnull)
        String parsed = parser.parse("{define name=yourname value=\"テラゾー\"/}");

ちゃんと受理される。

これを使って、テンプレート全体をパースできるパーサを作る……と思ったけど、なかなか上手くいかない。
タグ外の部分は基本的に構文が自由なので、タグ内のトークナイザを拡張しても上手く書く事が出来ない。
仕方が無いので、トークナイザの方である程度構造を見てどういうトークンを使うかを切り分けるようにする。
(発想としては、JparsecがDOUBLE_QUOTE_TOKENIZERを作っているのと同じ方式)

    public static final Terminals startBrace = Terminals.operators("{");
    public static final Terminals endBrace = Terminals.operators("}");
    public static final Terminals operators = Terminals.operators("/", "=");

    /**
     * @param tags タグ名を含むTerminals
     * @return タグ部分のトークナイザを戻す。
     */
    private static Parser<List<Token>> tagTokenizer(Terminals tags) {
        Parser<Object> tagNames = tags.tokenizer();
        Parser<Object> operatorTokenizer = operators.tokenizer();

        Parser<Fragment> identifier = Terminals.Identifier.TOKENIZER;
        Parser<String> expression = Terminals.StringLiteral.DOUBLE_QUOTE_TOKENIZER;
        Parser<?> ignorable = Scanners.WHITESPACES;

        Parser<Object> tagContent =
            Parsers.or(tagNames, identifier, expression, operatorTokenizer);

        Parser<List<Token>> tagTokenizer =
            Parsers.sequence(
                startBrace.tokenizer().token(),
                repeatWithIgnorables(tagContent.token(), ignorable),
                endBrace.tokenizer().token(),
                flatter);

        return tagTokenizer;
    }
    // 前後・トークン間に空白を含んだ繰り返し用のパーサを生成する。
    private static <T> Parser<List<T>> repeatWithIgnorables(Parser<T> parser, Parser<?> ignorables) {
        return ignorables.optional().next(parser.sepEndBy(ignorables.skipMany()));
    }
    // (Token, List<Token>, Token)をList<Token>にMapする
    private static final Map3<Token, List<Token>, Token, List<Token>> flatter =
        new Map3<Token, List<Token>, Token, List<Token>>() {
        public List<Token> map(Token start, List<Token> tags, Token end) {
            List<Token> tokens = new ArrayList<Token>(tags.size() + 2);

            tokens.add(start);
            tokens.addAll(tags);
            tokens.add(end);

            return tokens;
        }
    };

地のテキストの部分は、「{」「}」で囲われた部分以外としておく。「{」「}」自体を使いたいときは「\」でエスケープする。
エスケープされてる部分はトークナイザでアンエスケープしてしまう。

    public static final String LITERAL_NAME = "TEXT";
    private static Parser<Fragment> literalTokenizer() {
        Parser<Void> scanner = Scanners.pattern(Patterns.regex("((\\\\\\{)|(\\\\\\})|[^{}])*"), LITERAL_NAME);
        Parser<String> sourceParser = scanner.source();
        Parser<Fragment> tokenizer = sourceParser.map(
            new Map<String, Fragment>() {
                public Fragment map(String text) {
                    String unescaped = text.replaceAll("\\\\\\{", "{").replaceAll("\\\\\\}", "}");
                    return new Fragment(unescaped, LITERAL_NAME);
                }
                public String toString() {
                    return LITERAL_NAME;
                }
            });
        return tokenizer;
    }

正規表現を使う部分のパフォーマンスが気になるけど……
字句解析と構文解析を分ける意味があまり無い気がして来た……

全体のトークナイザは上の二つを組み合わせて作る。

    /**
     * @param tags タグ名を含むTerminals
     * @return テンプレート全体のトークナイザを戻す。
     */
    public static Parser<List<Token>> newTokenizer(Terminals tags) {
        Parser<List<Token>> tagTokenizer = tagTokenizer(tags);
        Parser<List<Token>> literalTokenizer = literalTokenizer().token().many(); // 型を合わせるためmany()

        Parser<List<Token>> tokenizer = 
            Parsers.or(tagTokenizer, literalTokenizer).many().map(listFlatter);

        return tokenizer;
    }
    // List<List<Token>>)をList<Token>にMapする
    private static final Map<List<List<Token>>, List<Token>> listFlatter =
        new Map<List<List<Token>>, List<Token>>() {
        public List<Token> map(List<List<Token>> items) {
            List<Token> tokens = new ArrayList<Token>();
            for (List<Token> item : items) {
                tokens.addAll(item);
            }
            return tokens;
        }
    };

これを使ってパーサを作るのだけど長いので次回。

*1:http://jparsec.codehaus.org/Downloadsのjparsec 2.0