はじめに

言語処理は、ひとつは自然言語処理を研究するための分野であるが、もうひとつは(もちろん)プログラミング言語処理のための分野でもある。

世界初の高級言語と名高いFORTRANは、1950年半ばにそのコンパイラ開発プロジェクトが始まったが、そのプロジェクトは大変に難航し、実に18人年の工数を費やしたと言われている。(完成は1957年)

しかし、この困難をばねにして、言語処理分野は飛躍的に発展することになる。今回は、これを少しだけかじってみる。

以前、YACCのかなりディープな話を紹介したことがあるが、今回はその続編と言うより、その前編的な内容となる。

コンパイラのしくみ超入門

コンパイラに必要な機能として、大きく2つがある。ひとつは入力となるプログラミング言語を解析すること。そしてもうひとつは、ターゲットオブジェクト(通常、これはアセンブリ言語だったり、機械語だったりする)を生成すること。

ともあれ、まずはごく簡単なコンパイラの実装を見てみよう。いわゆる「ドラゴンブック」の例をJavaで実装したものである。

package dragon;

import java.io.IOException;
import java.io.Reader;

/** ミニコンパイラの字句解析部. */
public class Lexer {

    /** 入力文字ストリーム. */
    private Reader reader;
    /** シンボルテーブル. */
    private SymbolTable symbol;
    /** 行番号. */
    private int lineNo;
    /** 単語用のバッファ. */
    private StringBuilder buffer;
    /** 先読みした文字. EOF となった場合は <code>-1</code>. */
    private int lookAhead;

    /**
     * 字句解析部の構築.
     * <p>
     * 構築時点で予め1文字を先読みしておき, 以降常に1文字分 {@link #lookAhead}
     * に先読みした文字を保持している.
     *
     * @param reader 入力文字ストリーム
     * @param symbol シンボルテーブル
     * @throws IOException 入出力例外が発生した場合
     */
    public Lexer(Reader reader, SymbolTable symbol) throws IOException {
        this.reader = reader;
        this.symbol = symbol;
        this.lineNo = 1;
        this.buffer = new StringBuilder();
        // 常に1文字先読みする戦略.
        this.lookAhead = reader.read();
    }

    /**
     * トークンを読みだす.
     *
     * @return 読みだしたトークン
     * @throws SyntaxException 構文例外が発生した場合
     * @throws IOException 入出力例外が発生した場合
     */
    public Token lexan() throws SyntaxException, IOException {
        Token token;
        for (; ; ) {
            if (lookAhead == -1) {
                token = TokenType.DONE;
                break;
            }
            char c = (char) lookAhead;
            switch (c) {
            case '(': token = TokenType.LPAREN; lookAhead = reader.read(); break;
            case ')': token = TokenType.RPAREN; lookAhead = reader.read(); break;
            case '+': token = TokenType.PLUS; lookAhead = reader.read(); break;
            case '-': token = TokenType.MINUS; lookAhead = reader.read(); break;
            case '/': token = TokenType.SLASH; lookAhead = reader.read(); break;
            case '*': token = TokenType.ASTER; lookAhead = reader.read(); break;
            case ';': token = TokenType.SEMICOLON; lookAhead = reader.read(); break;
            default:
                if (Character.isWhitespace(c)) {
                    if (c == '\n')
                        ++lineNo;
                    lookAhead = reader.read();
                    continue;
                }
                if (Character.isDigit(c)) {
                    // 数値リテラルを読込む.
                    do {
                        buffer.append(c);
                        c = (char) (lookAhead = reader.read());
                    } while (Character.isDigit(c));
                    token = new NumberToken(Integer.parseInt(buffer.toString()));
                    buffer.setLength(0);
                } else if (Character.isLetter(c)) {
                    // 単語を読込む.
                    do {
                        buffer.append(c);
                        c = (char) (lookAhead = reader.read());
                    } while (Character.isLetterOrDigit(c) || c == '_');
                    String text = buffer.toString();
                    buffer.setLength(0);
                    // シンボルテーブルを検索.
                    token = symbol.lookup(text);
                } else {
                    throw new SyntaxException("Unexpected character '%s' at line %d",
                            ' ' <= c && c <= '\u007F'
                                ? String.valueOf(c)
                                : String.format("U+%04X", c & 0xFFFF), lineNo);
                }
                break;
            }
            break;
        }
        return token;
    }
}
package dragon;

import java.io.IOException;
import java.io.Reader;

/** ミニコンパイラのパーサ. */
public class Parser {

    /** 字句解析部. */
    private Lexer lex;
    /** コード生成部. */
    private Emitter gen;
    /** 先読みしたトークン. */
    private Token lookAhead;

    /**
     * パーサを構築する.
     *
     * @param reader 入力文字ストリーム
     * @throws IOException 入出力例外が発生した場合
     */
    public Parser(Reader reader) throws IOException {
        lex = new Lexer(reader, new SymbolTable());
        gen = new Emitter();
    }

    /**
     * 式の並びを構文解析し, コード生成を行う.
     * <p>
     * 式の並びの生成規則は以下の通り.
     * <blockquote>
     * &lt;式の並び> ::= ( 式 ";" )*
     * </blockquote>
     * <p>
     * 生成するコードは,
     * <ol>
     * <li>式を評価するコード. // 結果はスタックトップにロードされる.
     * </ol>
     * の繰り返しとなる. すなわち, 評価した式が順にスタックに積まれていくため,
     * 実際にはスタックから取り除いて結果を表示するなどの処理が必要である.
     *
     * @throws SyntaxException 構文例外が発生した場合
     * @throws IOException 入出力例外が発生した場合
     */
    public void parse() throws SyntaxException, IOException {
        lookAhead = lex.lexan();
        while (lookAhead.getType() != TokenType.DONE) {
            expr();
            match(TokenType.SEMICOLON);
        }
    }

    /**
     * 「式」を解析し, コード生成を行う.
     * <p>
     * 式の生成規則は以下の通り.
     * <blockquote>
     * &lt;式> ::= &lt;項> ( ( "+" | "-" ) &lt;項> )*
     * </blockquote>
     * <p>
     * 生成するコードは,
     * <ol>
     * <li>項を評価するコード. // 結果はスタックトップにロードされる.
     * <li>項を評価するコード. // 結果はスタックトップにロードされる.
     * <li>二項演算命令. // スタックトップから取り除き, 新スタックトップと演算した結果をスタックトップに戻す.
     * </ol>
     * となる. 上記, 2~3 は任意回数の繰り返しとなる.
     *
     * @throws SyntaxException 構文例外が発生した場合
     * @throws IOException 入出力例外が発生した場合
     */
    private void expr() throws SyntaxException, IOException {
        term();
        for (; ; ) {
            switch (lookAhead.getType()) {
            case PLUS:
                match(lookAhead.getType());
                term();
                gen.emitBinary(Emitter.BinaryOperator.ADD);
                continue;
            case MINUS:
                match(lookAhead.getType());
                term();
                gen.emitBinary(Emitter.BinaryOperator.SUB);
                continue;
            default: break;
            }
            break;
        }
    }

    /**
     * 「項」を解析し, コード生成を行う.
     * <p>
     * 項の生成規則は以下の通り.
     * <blockquote>
     * &lt;項> ::= &lt;因子> ( ( "*" | "/" | "DIV" | "MOD" ) &lt;因子> )*
     * </blockquote>
     * <p>
     * 生成するコードは,
     * <ol>
     * <li>因子を評価するコード. // 結果はスタックトップにロードされる.
     * <li>因子を評価するコード. // 結果はスタックトップにロードされる.
     * <li>二項演算命令. // スタックトップから取り除き, 新スタックトップと演算した結果をスタックトップに戻す.
     * </ol>
     * となる. 上記, 2~3 は任意回数の繰り返しとなる.
     *
     * @throws SyntaxException 構文例外が発生した場合
     * @throws IOException 入出力例外が発生した場合
     */
    private void term() throws SyntaxException, IOException {
        factor();
        for (; ; ) {
            switch (lookAhead.getType()) {
            case ASTER:
                match(lookAhead.getType());
                factor();
                gen.emitBinary(Emitter.BinaryOperator.MUL);
                continue;
            case SLASH:
                match(lookAhead.getType());
                factor();
                gen.emitBinary(Emitter.BinaryOperator.DIV);
                continue;
            case DIV:
                match(lookAhead.getType());
                factor();
                gen.emitBinary(Emitter.BinaryOperator.DIV);
                continue;
            case MOD:
                match(lookAhead.getType());
                factor();
                gen.emitBinary(Emitter.BinaryOperator.MOD);
                continue;
            default: break;
            }
            break;
        }
    }

    /**
     * 「因子」を解析し, コード生成を行う.
     * <p>
     * 因子の生成規則は以下の通り.
     * <blockquote>
     * &lt;因子> ::= "(" &lt;式> ")" | 数値 | 名前
     * </blockquote>
     *
     * @throws SyntaxException 構文例外が発生した場合
     * @throws IOException 入出力例外が発生した場合
     */
    private void factor() throws SyntaxException, IOException {
        switch (lookAhead.getType()) {
        case LPAREN:
            match(TokenType.LPAREN);
            expr();
            match(TokenType.RPAREN);
            break;
        case NUMBER:
            gen.emitLoadImmediate(((NumberToken) lookAhead).getValue());
            match(TokenType.NUMBER);
            break;
        case ID:
            gen.emitLoadVariable(((IdToken) lookAhead).getText());
            match(TokenType.ID);
            break;
        default:
            throw new SyntaxException();
        }
    }

    /**
     * 次のトークン (先読みしているトークン) が指定されたトークンタイプであることを確認して捨て,
     * さらに次のトークンを先読みする.
     *
     * @param type 確認するトークンタイプ
     * @throws SyntaxException トークンタイプが一致しなかった場合
     * @throws IOException 入出力例外が発生した場合
     */
    private void match(TokenType type) throws SyntaxException, IOException {
        if (lookAhead.getType() != type)
            throw new SyntaxException();
        lookAhead = lex.lexan();
    }
}
package dragon;

/** コード生成部. */
public class Emitter {

    /** 二項演算のオペコード. */
    public enum BinaryOperator {
        ADD(" ADD       // MOVE (SP)+,D0; ADD D0,(SP)%n"),
        SUB(" SUB       // MOVE (SP)+,D0; SUB D0,(SP)%n"),
        MUL(" MUL       // MOVE (SP)+,D0; MULS (SP),D0; MOVE D0,(SP)%n"),
        DIV(" DIV       // MOVE (SP)+,D0; MOVE (SP)+,D1; EXT D1; DIVS D0,D1; MOVE D1,-(SP)%n"),
        MOD(" MOD       // MOVE (SP)+,D0; MOVE (SP)+,D1; EXT D1; DIVS D0,D1; SWAP D1; MOVE D1,-(SP)%n");

        private String assembly;

        private BinaryOperator(String assembly) {
            this.assembly = assembly;
        }

        /** 対応するアセンブリ言語を返す. */
        public String toAssembly() { return assembly; }
    }

    /**
     * 即値ロード命令を生成する.
     *
     * @param value 即値
     */
    public void emitLoadImmediate(int value) {
        System.out.printf(" LDI %5d // MOVE #%d,-(SP)%n", value, value);
    }

    /**
     * 変数ロード命令を生成する.
     *
     * @param name 変数名
     */
    public void emitLoadVariable(String name) {
        System.out.printf(" LOD %-5s // MOVE %s,-(SP)%n", name, name);
    }

    /**
     * 二項演算命令を生成する.
     *
     * @param op 生成するオペコード
     */
    public void emitBinary(BinaryOperator op) { System.out.printf("%s", op.toAssembly()); }
}
package dragon;

import java.util.LinkedHashMap;
import java.util.Map;

/** シンボルテーブル. */
public class SymbolTable {

    /** 名前からトークンを引くための表. */
    private Map<String, Token> symtable;

    /** 識別子に割振る番号. */
    private int sequence;

    /** シンボルテーブルを構築する. */
    public SymbolTable() {
        symtable = new LinkedHashMap<>();
        // 予約語を登録する.
        for (TokenType e : TokenType.values())
            if (e.isKeyword())
                symtable.put(e.name(), e);
        sequence = 0;
    }

    /**
     * 指定された名前を検索し, トークンとして返す.
     * <p>
     * 初出の識別子の場合, {@link IdToken} インスタンスを新たに生成して登録する.
     *
     * @param name 名前
     * @return トークン
     */
    public Token lookup(String name) {
        Token token = symtable.get(name);
        if (token == null) {
            token = new IdToken(name, sequence++);
            symtable.put(name, token);
        }
        return token;
    }
}
package dragon;

/** トークンを表すオブジェクトのインタフェース. */
public interface Token {

    /**
     * トークンタイプを返す.
     *
     * @return トークンタイプ
     */
    TokenType getType();

    /**
     * このトークンが予約語であることを示す.
     *
     * @return 予約語であれば {@code true}
     */
    boolean isKeyword();
}
package dragon;

/**
 * トークンタイプ.
 * <p>
 * {@link #NUMBER} および {@link #ID} 以外のトークンタイプは, トークン自身を兼ねている. (邪道)
 */
public enum TokenType implements Token {
    /** 入力テキストが終了したことを示す. */ DONE,
    /** ";". */ SEMICOLON,
    /** "(". */ LPAREN,
    /** ")". */ RPAREN,
    /** "+". */ PLUS,
    /** "-". */ MINUS,
    /** "*". */ ASTER,
    /** "/". */ SLASH,
    /** 予約語 "DIV". */ DIV { @Override public boolean isKeyword() { return true; } },
    /** 予約語 "MOD". */ MOD { @Override public boolean isKeyword() { return true; } },
    /** 数値リテラル. */ NUMBER,
    /** 識別子. */ ID;

    @Override public TokenType getType() { return this; }
    @Override public boolean isKeyword() { return false; }
}
package dragon;

/** 数値リテラルトークン. */
public class NumberToken implements Token {

    /** 値. */
    private int value;

    /**
     * 値を指定して数値リテラルトークンを構築する.
     *
     * @param value 値
     */
    public NumberToken(int value) {
        this.value = value;
    }

    /**
     * 値を返す.
     *
     * @return 値
     */
    public int getValue() {
        return value;
    }

    /**
     * 数値リテラルであることを示す {@link TokenType.NUMBER} を返す.
     *
     * @return {@link TokenType.NUMBER}
     */
    @Override public TokenType getType() {
        return TokenType.NUMBER;
    }

    /**
     * 数値リテラルが予約語ではないことを示す {@code false} を返す.
     *
     * @return {@code false}
     */
    @Override public boolean isKeyword() { return false; }
}
package dragon;

/**
 * 識別子トークン.
 * <p>
 * シンボルテーブル内のエントリを兼ねているため, コード生成に必要な情報を含んでいる.
 * このミニコンパイラの例では名前とアドレス代わりのシーケンス番号を保持している.
 * ただし, 現状シーケンス番号は使用していない.
 */
public class IdToken implements Token {

    /** 名前. */
    private String text;
    /** シーケンス番号. */
    private int sequence;

    /**
     * 名前とシーケンス番号を指定してインスタンスを構築する.
     *
     * @param text 名前
     * @param sequence シーケンス番号
     */
    public IdToken(String text, int sequence) {
        this.text = text;
        this.sequence = sequence;
    }

    /**
     * 識別子の名前を返す.
     *
     * @return 名前
     */
    public String getText() {
        return text;
    }

    /**
     * 識別子のシーケンス番号を返す.
     *
     * @return シーケンス番号
     */
    public int getSequence() { return sequence; }

    /**
     * 識別子のトークンタイプ {@link TokenType.ID} を返す.
     *
     * @return {@link TokenType.ID}
     */
    @Override public TokenType getType() {
        return TokenType.ID;
    }

    /**
     * 識別子が予約語でないことを示す {@code false} を返す.
     *
     * @return {@code false}
     */
    @Override public boolean isKeyword() { return false; }
}
package dragon;

/** 構文例外. */
public class SyntaxException extends Exception {
    private static final long serialVersionUID = -3922533298276814934L;

    public SyntaxException() { }
    public SyntaxException(String format, Object... args) {
        super(String.format(format, args));
    }
}
package dragon;

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.Reader;

/** ミニコンパイラ. */
public class Main {

    /**
     * エントリポイント.
     *
     * @param args コマンドライン引数 (未使用)
     * @throws SyntaxException 構文例外が発生した場合
     * @throws IOException 入出力例外が発生した場合
     */
    public static void main(String[] args) throws SyntaxException, IOException {
        Reader reader = new InputStreamReader(System.in);
        Parser parser = new Parser(reader);     // パーサを生成.
        parser.parse();                         // コンパイルを実行.
    }
}

字句解析

コンパイラの入力となるのは、言語を表現した文字の列であるが、そのままでは扱いにくいため、一旦言語の構文要素となる「トークン」と呼ばれる構成単位まで分解を行う。この分解処理のことを字句解析と呼ぶ。

通常のフリーフォーマットの言語の場合「123␣+␣456」と言う文字列を、「123」「+」「456」の3トークンに分解することになる。このとき、単語の区切りとしてしか意味を持たないタブや空白、それにコメントなどは除去してしまうことが多い。つまり多くのプログラミング言語において、コメントは構文要素ですらないと言える。(ほとんどの言語の文法規則にコメントは登場しない。)

字句解析プログラムは、技術的にさほど難しい部分はないので、手書きすることも多いが、lexと言うツールを用いて正規表現から生成することもしばしば行われる。

正規表現とFA

余談だが、“regular expression” の訳として、一般的に「正規表現」と呼ばれているが、これは誤訳と言う噂がある。“expression” は確かに「表現」と言う意味を持っているが “regular expression” は、正規文法の記法と言う意味合いを持つ言葉であり、「正規式」と訳すのが適切だったと言う説である。“Arithmetic expression” は「算術式」であって、決して「算術表現」などとは訳さないだろう。

それはさておき、言語理論(正確には形式言語理論)で正規言語と言うと、分かりにくい(だがスマートで)立派な定義があるのだが、実用的には以下の定義が分かりやすい。

正規式 ::= 空 | 文字
         | 正規式 “|” 正規式
         | 正規式 正規式
         | 正規式 “*”
         | “(” 正規式 “)”

※上記定義は記法を定義しているのではない。あくまで言語を定義している。記法の定義、つまり文法としては「曖昧」であるので、あまり真に受けない方がよい。

「空」を本当に空にすると、非常に分かりづらいので、これをε(エプシロン)で表現するのが慣例である。英語のemptyの頭文字と音価が等しいギリシャ文字を当てたものと思われる。

これによって定義される正規言語は、単純な有限(状態)オートマトンで処理できることがわかっている。よくFAもしくはFSAとかFSMと略記されるがどれも同じものを指している。

FAには非決定性有限オートマトンと決定性有限オートマトンの二種類があり、それぞれNFA(ぬふぁ)、DFA(どぅふぁ)と呼ばれている。

NFAは、ある状態で特定の入力があったとき、遷移先の状態が1つに限定されないFAのことである。例えば正規式 “aba” に対して “a” を入力したときのことを考えてみる。これだけでは式の最初の “a” の一部なのか、それとも “ab*” が実は空で、最後の “a” なのか、決定できない。次の入力が “b” であれば、前者でしかありえないし、入力がこれで終わりであれば、後者に決まる。NFAの非決定性と言う言葉はこのような事情を表現している。

これに対してDFAは、ある状態である入力があったとき、遷移先の状態が1つに確定するタイプのFAである。

こう説明すると、NFAとDFAは随分と性質の異なるFAのように感じられるだろうが、どちらも論理的な表現能力としては等価であることが証明できる。そして、どんな正規言語も、FAで処理可能で、逆にFAで処理可能な言語は正規言語と言える。

先の説明で分かるように、正規式は非決定的であるため、これをいきなりDFAに落とすのは難しいが、NFAに落とすのは機械的に実現できる。

image001.png

やたらとたくさんεが登場するが、トリガーがεであるような遷移のことを「ε遷移」と呼ぶ。実際にNFAを構成する際の工夫で、ほとんどのε遷移を省略することも可能だが、まったくなくすことは簡単にはできない。ε遷移を徹底的に排除して表現してみると、以下のようになる。

image003.png

一見、このような簡潔なルールで問題ないように思えるが、穴がある。例えばa|b*を、必要最小限のε遷移で考えてみると、以下のようなNFAとなる。

image004.png

左のε遷移を削り、SaとScを同状態に重ねてみると、そのNFAは元の正規式では受理されない “ba” を受理してしまうようになり、意味が変わってしまう。右のε遷移も同様、ScとSbを同状態に重ねると、今度は “ab” を受理してしまう。

NFAの動作を実際にコンピュータでシミュレートする場合、取り得るすべての状態を記憶しておく必要がある。そして次の入力によって各状態から遷移し得るすべての状態が遷移先となる。このことを注意深く2時間ほど考えると、NFAをDFAへ変換するアルゴリズムを思いつくはず。NFAの特定の状態集合を、DFAの1状態と対応付けて、あらゆるDFAの状態(つまりNFAの状態集合)から、あり得るすべての入力について、遷移先の状態を対応付けて行けばよい。

NFAの構築とパターンマッチングを行うプログラムを紹介する。

FA.java: オートマトンのインタフェース。

package org.creasys.fa;

/** 有限状態オートマトンのインタフェース. */
public interface FA
  {
    /**
     * テキストとのマッチングを調べる.
     *
     * @param text テキスト
     * @return マッチした場合 <code>true</code>
     */
    boolean matches(String text);
  }

NFA.java: 非決定性オートマトンの実装。

package org.creasys.fa;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;

/** 非決定性オートマトン. */
public class NFA implements FA
  {
    /** NFA 状態. */
    public class State
      {
        private int serial;
        private boolean accepted;
        private Map<Character, Set<State>> transitions;

        State(int serial)
          {
            this.serial = serial;
            this.accepted = false;
            this.transitions = new HashMap<>();
          }

        Map<Character, Set<State>> getTransitions()
          {
            return transitions;
          }

        void addTransition(Character ch, State next)
          {
            Set<State> nextStates = transitions.get(ch);
            if (nextStates == null)
              {
                nextStates = new HashSet<>();
                transitions.put(ch, nextStates);
              }
            nextStates.add(next);
          }

        void addEpsilonTransition(State next)
          {
            addTransition(null, next);
          }

        void setAccepted(boolean accepted)
          {
            this.accepted = accepted;
          }

        Set<State> getEpsilonClosure()
          {
            Set<State> closure = new HashSet<>();
            closure.add(this);
            Set<State> nexts = transitions.get(null);
            if (nexts != null)
                nexts.stream().forEach(s->closure.addAll(s.getEpsilonClosure()));
            return closure;
          }

        Set<State> next(Character ch)
          {
            Set<State> next= transitions.containsKey(ch)
                    // 直接の遷移先からε閉包を得る.
                ? transitions.get(ch).stream()
                        .flatMap(s -> s.getEpsilonClosure().stream())
                        .collect(Collectors.toSet())
                : Collections.emptySet();
            return next;
          }

        boolean isAccepted()
          {
            return accepted;
          }

        @Override public String toString()
          {
            return Integer.toString(serial);
          }
      }

    protected int serial;
    protected List<State> states;
    protected State initial;

    protected State createState()
      {
        State state = new State(serial++);
        states.add(state);
        return state;
      }

    protected Set<State> initialStates()
      {
        return initial.getEpsilonClosure();
      }

    /**
     * 正規式より, 非決定性オートマトンを構築する.
     *
     * @param expr 正規式
     */
    public NFA(Expr expr)
      {
        this.serial = 0;
        this.states = new ArrayList<>();
        this.initial = createState();
        if (expr instanceof Epsilon)
            initial.setAccepted(true);
        else
            expr.compile(this, initial, createState()).setAccepted(true);
      }

    /**
     * テキストとのマッチングを調べる.
     *
     * @param text テキスト
     * @return マッチした場合 <code>true</code>
     */
    @Override
    public boolean matches(String text)
      {
        Set<State> from = new HashSet<>();
        from.addAll(initialStates());
        for (Character c : text.toCharArray())
          {
            from = from.stream()
                    .flatMap(state -> state.next(c).stream())
                    .collect(Collectors.toSet());
            if (from.isEmpty())
                break;
          }
        return from.stream().anyMatch(s -> s.isAccepted());
      }

    private String toString(Set<State> set)
      {
        String str = set == null ? "" :
            set.stream()
                .map(state -> state.toString())
                .collect(Collectors.joining(","));
        return str;
      }

    @Override
    public String toString()
      {
        List<Character> chars = states.stream()
            .flatMap(s -> s.getTransitions().keySet().stream())
            .sorted((x, y) ->
                x == null ? y == null ? 0 : -1 : y == null ? 1 : x.compareTo(y)
             )
            .distinct().collect(Collectors.toList());

        StringBuilder strb = new StringBuilder();

        strb.append("STATE | ");
        chars.stream()
            .map(c -> String.format(" %-8s", c == null ? "eps" : c))
            .forEach(s -> strb.append(s));

        strb.append(String.format("%n------+-"));
        strb.append(Utils.repeat("---------", chars.size()));
        strb.append(String.format("%n"));

        states.forEach(state ->
          {
            strb.append(String.format("%5s%c| ", state, state.isAccepted() ? '*' : ' '));
            chars.forEach(ch ->
                strb.append(String.format(" %-8s", toString(state.getTransitions().get(ch))))
            );
            strb.append(String.format("%n"));
          });
        return strb.toString();
      }
  }

正規式はツリー構造をそのまま与える方式である。

Expr.java: 式の抽象クラス。

package org.creasys.fa;

public abstract class Expr
  {
    public enum Precedence {
        PRIMARY,
        STAR,
        CAT,
        UNION
    }

    public static Epsilon EPS = Epsilon.EPS;

    /**
     * NFAにコンパイルして結果状態を返す.
     *
     * @param nfa 構築中のNFAインスタンス
     * @param from 起点となる状態
     * @param next 終点となる状態
     * @return 結果状態
     */
    abstract NFA.State compile(NFA nfa, NFA.State from, NFA.State next);

    /** 優先度を返す. */
    abstract Precedence precedence();
    /**
     * この式が比較対象より優先度が高いか調べる.
     *
     * @param other 比較対象の式
     * @return この式の優先度が高いとき <code>true</code>
     */
    boolean isPrior(Expr other) { return precedence().ordinal() < other.precedence().ordinal(); }
  }

正規式の実装クラスは5個ある。

Epsilon.java: 「空」を表す式。

package org.creasys.fa;

import org.creasys.fa.NFA.State;

public class Epsilon extends Expr
  {
    public static final Epsilon EPS = new Epsilon();

    private Epsilon() { }

    @Override
    State compile(NFA nfa, State from, State next)
      {
        if (from != next)
            from.addEpsilonTransition(next);
        return next;
      }

    @Override
    Precedence precedence() { return Expr.Precedence.PRIMARY; }

    @Override
    public String toString() { return "ε"; }
  }

Char.java: 文字を表す式。

package org.creasys.fa;

/** 正規式の「文字」. */
public class Char extends Expr
  {
    /**
     * 正規式としての文字を生成する.
     *
     * @param ch 文字
     * @return 正規式としての文字
     */
    public static Char of(char ch) { return new Char(ch); }

    private char ch;

    private Char(char ch) { this.ch = ch; }

    /**
     * 文字を NFA にコンパイルする.
     * <p>
     * 文字が C であるとき, コンパイル結果は,
     * <pre>
     * 起点 -> C -> 終点
     * </pre>
     * となる.
     */
    @Override
    NFA.State compile(NFA nfa, NFA.State state, NFA.State next)
      {
        state.addTransition(ch, next);
        return next;
      }

    @Override
    Precedence precedence() { return Expr.Precedence.PRIMARY; }

    @Override
    public String toString() { return Character.toString(ch); }
  }

Cat.java: 連接。

package org.creasys.fa;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/** 正規式の連接. */
public class Cat extends Expr
  {
    /**
     * 引数に指定された式の連接を生成して返す.
     * <p>
     * 引数には {@link Character}, {@link CharSequence}, および {@link Expr}
     * のインスタンスを指定できる.
     *
     * @param args 連接する式
     * @return 生成した連接式
     */
    public static Expr of(Object... args)
      {
        List<Expr> exprs = Arrays.stream(args)
                .<Expr>flatMap(arg ->
                    arg instanceof Epsilon
                        ? Stream.of(Expr.EPS) :
                    arg instanceof Character
                        ? Stream.of(Char.of((char) arg)) :
                    arg instanceof CharSequence
                        ? ((CharSequence) arg).chars()
                            .mapToObj(c -> Char.of((char) c)) :
                    Stream.of((Expr) arg))
                .collect(Collectors.toList());
        return exprs.isEmpty() ? Expr.EPS : new Cat(exprs);
      }

    private List<Expr> exprs;

    private Cat(List<Expr> expr) { this.exprs = expr; }

    /**
     * 連接を NFA にコンパイルする.
     * <p>
     * 連接の要素が C0, C1, ..., Cn であるとき,
     * コンパイル結果は,
     * <pre>
     * 起点 -> C0 -> C1 -> ... -> Cn -> 終点
     * </pre>
     * となる.
     */
    @Override
    NFA.State compile(NFA nfa, NFA.State from, NFA.State next)
      {
        if (exprs.isEmpty())
          {
            // 空の連接はあり得ないが, 仮に空であれば ε遷移を加える.
            from.addEpsilonTransition(next);
            from = next;
          }
        else
          {
            for (int k = 0; k < exprs.size() - 1; ++k)
                from = exprs.get(k).compile(nfa, from, nfa.createState());
            // 最後.
            from = exprs.get(exprs.size() - 1).compile(nfa, from, next);
          }
        return from;
      }

    @Override
    Precedence precedence() { return Expr.Precedence.CAT; }

    @Override
    public String toString()
      {
        return exprs.stream()
            .flatMap(e -> isPrior(e) ?
                    Stream.of("(", e.toString(), ")") :
                    Stream.of(e.toString()))
            .collect(Collectors.joining());
      }
  }

Union.java: 和。

package org.creasys.fa;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/** 正規式の和. */
public class Union extends Expr
  {
    public static Union of(Object... args)
      {
        return new Union(Arrays.stream(args)
            .<Expr>map(arg->
                arg instanceof Character ?
                    Char.of((char) arg) :
                arg instanceof CharSequence ?
                    Cat.of(arg) :
                    (Expr) arg)
            .collect(Collectors.toList()));
      }

    private List<Expr> exprs;

    private Union(List<Expr> expr) { this.exprs = expr; }

    /**
     * 和を NFA にコンパイルする.
     * <p>
     * <pre>
     * S -+->(U1)-+-> N
     *    |       ^
     *    +->(U2)-+
     * </pre>
     */
    @Override
    NFA.State compile(NFA nfa, NFA.State state, NFA.State next)
      {
        exprs.forEach(expr -> expr.compile(nfa, state, next));
        return next;
      }

    @Override
    Precedence precedence() { return Expr.Precedence.UNION; }

    @Override
    public String toString()
      {
        return exprs.stream()
                .flatMap(expr -> isPrior(expr)
                    ? Stream.of("(", expr.toString(), ")")
                    : Stream.of(expr.toString()))
                .collect(Collectors.joining("|"));
      }
  }

Star.java: クリーネ閉包。

package org.creasys.fa;

/** クリーネ閉包 (Kleene closure) 演算式. */
public class Star extends Expr
  {
    public static Star of(Character c) { return new Star(Char.of(c)); }
    public static Star of(CharSequence s) { return new Star(Cat.of(s)); }
    public static Star of(Expr expr) { return new Star(expr); }

    private Expr expr;

    private Star(Expr expr) { this.expr = expr; }

    /**
     * 閉包を NFA にコンパイルする.
     * <p>
     * S, N を開始状態, 終了状態, L を新たに導入するループ状態,
     * (e) でε遷移, (C) を閉包の対象とするとき, コンパイル結果は
     * <pre>
     * S -(e)-> L ----+-(e)-> N
     *          ^     |
     *          +-(C)-+
     * </pre>
     * となる.
     */
    @Override
    NFA.State compile(NFA nfa, NFA.State state, NFA.State next)
      {
        NFA.State loop = nfa.createState();
        state.addTransition(null, loop);
        expr.compile(nfa, loop, loop).addTransition(null, next);
        return next;
      }

    @Override
    Precedence precedence() { return Expr.Precedence.STAR; }

    @Override
    public String toString()
      {
        return isPrior(expr)
                    ? "(" + expr + ")*"
                    : expr + "*";
      }
  }

Utils.java: ユーティリティ。

package org.creasys.fa;

public class Utils
  {

    public static String repeat(CharSequence str, int n)
      {
        StringBuilder strb = new StringBuilder();
        for (int k = 0; k < n; ++k)
            strb.append(str);
        return strb.toString();
      }

  }

FATest.java: デモ用のテスト基底。

package org.creasys.fa;

import java.util.function.Function;
import org.junit.Assert;
import org.junit.FixMethodOrder;
import org.junit.Test;
import org.junit.runners.MethodSorters;

@FixMethodOrder(MethodSorters.NAME_ASCENDING)
public class FATest
  {
    static class Assertion
      {
        String text;
        boolean expected;
      }

    static Assertion t(String text, boolean expected)
      {
        Assertion assertion = new Assertion();
        assertion.text = text;
        assertion.expected = expected;
        return assertion;
      }

    private Function<Expr, FA> gen;

    public FATest(Function<Expr, FA> gen)
      {
        this.gen = gen;
      }

    void asserts(Expr expr, Assertion... pairs)
      {
        FA fa = gen.apply(expr);
        System.out.printf("%nEXPR: %s%nNFA:%n%s", expr, fa);
        for (int k = 0; k < pairs.length; ++k)
          {
            String text = pairs[k].text;
            boolean expected = pairs[k].expected;
            boolean actual = fa.matches(text);
            System.out.printf(
                "%-10s => %-5s (%s)%n",
                text,
                actual,
                expected == actual ? "OK" : "NG");
            Assert.assertEquals(expected, actual);
          }
      }

    @Test
    public void test00Empty()
      {
        asserts(Expr.EPS, t("", true), t("a", false));
      }

    @Test
    public void test01Char()
      {
        asserts(Char.of('A'), t("A", true), t("", false), t("B", false));
      }

    @Test
    public void test02Cat()
      {
        asserts(Cat.of('A', 'B'), t("AB", true), t("AAB", false));
        asserts(Cat.of(Expr.EPS, 'B'), t("B", true), t("AAB", false));
        asserts(Cat.of('A', Expr.EPS), t("A", true), t("AAB", false));
      }

    @Test
    public void test03Union()
      {
        asserts(Union.of('A', 'B', 'C'), t("A", true), t("D", false));
        asserts(Union.of(Expr.EPS, 'A'), t("", true), t("A", true), t("AA", false));
      }

    @Test
    public void test04Star()
      {
        asserts(Star.of('A'), t("", true), t("A", true));
      }

    @Test
    public void test05UnionOfCats()
      {
        asserts(Union.of("he", "his", "she", "her", "hers"),
            t("he", true),
            t("him", false)
        );
      }

    @Test
    public void test06StarOfUnion()
      {
        asserts(Cat.of(Star.of(Union.of('A', 'B')), 'X'),
            t("X", true),
            t("AX", true),
            t("ABABX", true),
            t("XA", false));
      }

    @Test
    public void test07UnionOfStar()
      {
        asserts(Cat.of(Union.of(Star.of('A'), 'B'), 'X'),
            t("X", true),
            t("AX", true),
            t("AAAX", true),
            t("BX", true),
            t("ABX", false),
            t("BBX", false),
            t("BAX", false));
      }

    @Test
    public void test08()
      {
        asserts(Union.of('A', Star.of('B')),
            t("", true),
            t("A", true),
            t("B", true),
            t("BB", true),
            t("AA", false),
            t("AB", false),
            t("BA", false));
      }

    @Test
    public void test09ex1()
      {
        // (a|b)*abb
        asserts(
            Cat.of(Star.of(Union.of('a', 'b')), "abb"),
            t("aab", false),
            t("abb", true),
            t("aabb", true),
            t("abba", false)
        );
      }

    @Test
    public void test09ex2()
      {
        asserts(
            Union.of(Cat.of('a', Star.of('a')), Cat.of('b', Star.of('b'))),
            t("a", true),
            t("aa", true),
            t("ab", false)
        );
      }

    @Test
    public void test09ex3()
      {
        // a(b*|c)d
        asserts(Cat.of('a', Union.of(Star.of('b'), 'c'), 'd'), t("abcd", false), t("abbd", true));
      }

    @Test
    public void testCsv()
      {
        // Q: 引用符
        // C: カンマ
        // A: 通常の文字
        //
        // ε
        // A(A|Q)*
        // Q(A|C|QQ)*Q
        asserts(Union.of("", Cat.of('A', Star.of(Union.of('A', 'Q'))), Cat.of('Q', Star.of(Union.of('A', 'C', "QQ")), 'Q')),
            t("A", true),
            t("QAQ", true));
      }

    @Test
    public void testQ()
      {
        asserts(Cat.of('A', Star.of('B'), Union.of('C', Expr.EPS)),
            t("A", true),
            t("AB", true),
            t("ABB", true),
            t("AC", true),
            t("ABC", true),
            t("B", false));
      }
  }

NFATest.java: NFAのテストケース。

package org.creasys.fa;

import org.junit.FixMethodOrder;
import org.junit.runners.MethodSorters;

@FixMethodOrder(MethodSorters.NAME_ASCENDING)
public class NFATest extends FATest
  {
    public NFATest()
      {
        super(NFA::new);
      }
  }

以上でNFAを扱うプログラムは一通り揃った。以降はDFAの実装。

DFA.java: DFAの本体。

package org.creasys.fa;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.stream.Collectors;

/** 決定性オートマトン. */
public class DFA implements FA
  {
    /** DFA 状態. */
    public class State
      {
        private int serial;
        private boolean accepted;
        private Map<Character, State> transitions;

        State(int serial)
          {
            this.serial = serial;
            this.accepted = false;
            this.transitions = new HashMap<>();
          }

        Map<Character, State> getTransitions()
          {
            return transitions;
          }

        void addTransition(Character ch, State next)
          {
            State o = transitions.put(ch, next);
            if (o != null)
              {
                transitions.put(ch, o);
                throw new IllegalStateException();
              }
          }

        void setAccepted(boolean accepted)
          {
            this.accepted = accepted;
          }

        State next(Character ch)
          {
            State next = transitions.get(ch);
            return next;
          }

        boolean isAccepted()
          {
            return accepted;
          }

        @Override public String toString()
          {
            return Integer.toString(serial);
          }
      }

    protected int serial;
    protected List<State> states;
    protected State initial;

    protected State createState()
      {
        State state = new State(serial++);
        states.add(state);
        return state;
      }

    protected State initialState()
      {
        return initial;
      }

    /**
     * 正規式より, 決定性オートマトンを構築する.
     *
     * @param expr 正規式
     */
    public DFA(Expr expr)
      {
        this(new NFA(expr));
      }

    /**
     * NFA から DFA を構築する.
     *
     * @param nfa NFA
     */
    public DFA(NFA nfa)
      {
        this.serial = 0;
        this.states = new ArrayList<>();
        this.initial = createState();

        // NFA 状態集合に DFA 状態を対応付ける表.
        Map<Set<NFA.State>, State> map = new HashMap<>();
        // 対応表のエントリ.
        class S
          {
            State ds;
            Set<NFA.State> ns;

            S(State ds, Set<NFA.State> ns)
              {
                this.ds = ds;
                this.ns = ns;
                map.put(ns, ds);
              }
          }

        Queue<S> queue = new LinkedList<>();
        // 初期状態をキューに入れる.
        queue.offer(new S(initial, nfa.initialStates()));
        while (!queue.isEmpty())
          {
            S state = queue.poll();
            state.ds.setAccepted(state.ns.stream().anyMatch(s -> s.isAccepted()));
            for (Character c :
                    state.ns.stream()
                            .flatMap(s -> s.getTransitions().keySet().stream())
                            .filter(c -> c != null)
                            .collect(Collectors.toSet()))
              { // 遷移がある全文字について
                // 遷移先の NFA 状態集合を決定する.
                Set<NFA.State> nnext = state.ns.stream()
                        .flatMap(s -> s.next(c).stream())
                        .flatMap(s -> s.getEpsilonClosure().stream())
                        .collect(Collectors.toSet());
                State dnext = map.get(nnext);
                if (dnext == null)
                  {
                    // 初出の状態だった場合, 新たな DFA 状態を対応付ける.
                    dnext = createState();
                    // キューに入れる.
                    queue.offer(new S(dnext, nnext));
                  }
                state.ds.addTransition(c, dnext);
              }
          }
      }

    /**
     * テキストとのマッチングを調べる.
     *
     * @param text テキスト
     * @return マッチした場合 <code>true</code>
     */
    @Override
    public boolean matches(String text)
      {
        State state = initial;
        for (char c : text.toCharArray())
          {
            state = state.next(c);
            if (state == null)
                break;
          }
        return state != null && state.isAccepted();
      }

    @Override
    public String toString()
      {
        // 登場する全文字をソート.
        List<Character> chars = states.stream()
                .flatMap(s -> s.getTransitions().keySet().stream())
                .sorted()
                .distinct()
                .collect(Collectors.toList());

        StringBuilder strb = new StringBuilder();
        strb.append("STATE | ");
        chars.forEach(ch ->
            strb.append(String.format(" %-4s", ch)));
        strb.append(String.format("%n------+-"));
        strb.append(Utils.repeat("-----", chars.size()));
        strb.append(String.format("%n"));
        states.forEach(state ->
          {
            strb.append(String.format("%5s%c| ", state, state.isAccepted() ? '*' : ' '));
            chars.forEach(ch ->
              {
                State next = state.next(ch);
                strb.append(String.format(" %-4s", next != null ? next : ""));
              });
            strb.append(String.format("%n"));
          });
        return strb.toString();
      }
  }

DFATest.java: DFAのテストケース。実体はNFAと共通である。

package org.creasys.fa;

import org.junit.FixMethodOrder;
import org.junit.runners.MethodSorters;

@FixMethodOrder(MethodSorters.NAME_ASCENDING)
public class DFATest extends FATest
  {
    public DFATest()
      {
        super(DFA::new);
      }
  }

正規言語のやや実用的な例として、CSV(の一行)を挙げる。正確な定義を考える際、結局頭の中にせよ、書き下すにせよ、あり得る全状態と、それぞれの状態における入力文字の処理、そしてその後の状態を考える必要があり、そうして完成した絵は、既に正規表現やNFAを通り越して、DFAになっている。

下図で、Aは通常の文字、Cはフィールドセパレータ、Qは引用符、そしてNは改行を意味している。

image005.png

このくらいややこしくなると、これを正規表現で書くのは骨が折れる。とりあえず、1フィールドだけなら、

((Q(A|C|N|QQ)*Q|ε)A(A|Q)*|ε)

などと書けるが、これだけですでに十分意味不明である。

正規表現の限界

grepなどでおなじみの “正規表現” は、実は正規式ではなく、したがって常にFAで処理できるとは限らない。どのような “正規表現” が正規言語を表し、どれがそうでないか、判別するのは簡単ではない。前方参照を利用するとダメだと言う説をたまに見かけるが、必ずしもそうではない。

また、正規言語は「数を数えられない」とか「記憶できない」などと言われる。括弧のネストが登場する数式や、任意の単語を区切りとして指定できるシェルのヒアドキュメントのような構造などは、正規言語とはならない。そもそも正規式自体を正規式では表現できない。

UNIXのライブラリとfgrepについて

完全な余談になる。

UNIXには古くからregex(3)なるライブラリが用意されており、C言語のプログラムからこれを利用することで、簡単に正規表現による検索機能などが実現できるようになっていた。しかしながら、伝統的なこのライブラリは実に素朴なパターンマッチング処理となっていて、恐ろしく効率の悪い実装となっていて、ハッカーたちはこれをそのまま利用するのに抵抗を感じていたようである。

例えばGNUによるe?grep、awkなどは、GNUのregex(これは伝統的なUNIXのregex実装と大差ない)を利用しつつ、効率をよくするためにDFAを併用する実装となっていた。(今はどうか知らない。)

fgrepは、正規表現が扱えない代わりに、任意個の文字列を一度に検索すると言うちょっと変わったツールである。こちらは、伝統的にDFAによる実装となっている。(GNUのは少し違ったような気もする。)このfgrepに使われているアルゴリズムは、とても美しいので一度紹介したいと思っているが、今回は割愛する。その代わり、伝統的なregexの実装の雰囲気を味わうためにワイルドカードのマッチングアルゴリズムを紹介する。

例として、パターン “A*BC” と文字列 “ABABC” の照合を考える。まずは先頭文字同士。

A*BC    ABABC

これは単純な比較である。マッチするため、双方とも一文字進める。

A|*BC   A|BABC

パターンの方は次は “” で、文字列には4文字残っているため、“” とマッチさせるべき文字数は0~4のいずれかとなる。0から試してみる。

A*|BC   A|BABC

これだと最初の文字 “B” は一致するが、それ以降が一致しないため失敗である。次に “*” に1文字マッチさせて試してみる。

A*|BC   AB|ABC

これは直ちに失敗。次に2文字として

A*|BC   ABA|BC

ようやく、“*” 以降のすべての文字がマッチする。

ここで、 “” がいくつか含まれている場合、マッチの仕方が複数個存在することがある。例えば “A” と “BABAB” のマッチングを考えると、最初の “” に “B” を対応させても、 “BAB” を対応させてもマッチは成功する。上記の方法の場合、文字数の少ない方から試行するため、“B” にマッチすることになる。一般的にはこれは逆の方が好ましいのであるが、ワイルドカードの場合、マッチするかしないかの判定のみを目的としているため、気にしても仕方がない。

“*” に出会うたびにマッチさせる文字数を変化させながら、後続のマッチングを試行すると考えると、自然と再帰アルゴリズムとなる。これを素直に書き下すと、以下のようになる。

matches(pat[p..], str[s..]) ::=
     pat[p..].length == 0 & str[s..].length == 0 ⇒ SUCCESS
     pat[p..].length == 0 & str[s..].length != 0 ⇒ FAILURE
     (以下, pat[p..].length != 0 を省略)
     pat[p] != '*' && str[s..].length == 0 ⇒ FAILURE
     pat[p] != '*' && str[s..].length != 0 && pat[p] == str[s] ⇒ matches(pat[p+1..], str[s+1..])
     pat[p] != '*' && str[s..].length != 0 && pat[p] != str[s] ⇒ FAILURE
     (以下, pat[p] == '*' を省略)
     matches(pat[p+1..], str[s..]) == SUCCESS ⇒ SUCCESS
     matches(pat[p+1..], str[s..]) != SUCCESS ⇒ str[s..].length == 0 ⇒ FAILURE
     matches(pat[p+1..], str[s..]) != SUCCESS ⇒ str[s..].length != 0 ⇒ matches(pat[p..], str[s+1..])

※煩雑になるので、“*” 以外のメタ文字は無視して記述している。

ループで済むところはループに直してJavaのプログラムにすると、

public class WildCard {
         private char[] pat;

         public WildCard(String pat) {
                   this.pat = pat.toCharArray();
         }

         public boolean matches(String str) {
                   return matches(0, 0, str.toCharArray());
         }

         private boolean matches(int p, int s, char[] str) {
                   boolean matched = false;
                   for (; ; ) {
                            if (p == pat.length) {
                                     matched = s == str.length;
                                     break;
                            }
                            char cp = pat[p++];
                            if (cp == '*') {
                                     while (!(matched = matches(p, s, str)) &&
                                                        s != str.length)
                                               ++s;
                                     break;
                            }
                            if (s == str.length || cp != str[s++] && cp != '?')
                                     break;
                   }
                   return matched;
         }
}

メタ文字として、“*” と “?” しか考慮していないが、文字クラスやエスケープ文字などの対応は簡単であるため、言及しない。

一見、試行とバックトラックが必須であるように見えるワイルドカードの処理であるが、実はそれは必須ではなく、注意深く考えると再帰を完全に削除することも可能である。

public class WildCard {
    private char[] pat;

    public WildCard(String pattern) {
        this.pat = pattern.toCharArray();
    }

    public boolean matches(String string) {
        boolean matched = false;
        char[] str = string.toCharArray();

        int p = 0;
        int s = 0;
        int p0 = -1;
        int s0 = -1;

        for (; ; ) {
            if (p == pat.length) {
                // パターンが尽きた.
                if (s == str.length) {
                    // ちょうどテキストも尽きていればマッチ成功.
                    matched = true;
                    break;
                }
            } else {
                // パターンはまだ続く.
                char cp = pat[p++];
                if (cp == '*') {
                    // パターンに「*」が現れた. その位置を記憶して続行.
                    // つまり, まずは「*」に0文字マッチさせてみる.
                    p0 = p;
                    s0 = s;
                    continue;
                }
                if (s == str.length)
                    // テキストが尽きた.
                    // 「*」にマッチさせるテキストは短い方から試みているため,
                    // テキストの方が先に尽きるとそれ以上は試みる価値がない.
                    break;
                char cs = str[s++];
                if (cp == cs || cp == '?')
                    continue;
            }
            // 現在のマッチの試みが失敗.
            if (p0 == -1 || s0 == str.length)
                // 「*」の試行中でないか, もうテキストを延ばす余地がなければ諦める.
                break;
            // パターンは「*」の次の文字から
            // テキストは前回のチャレンジの次の文字から再開.
            p = p0;
            s = ++s0;
        }
        return matched;
    }
}

” が複数個現れる場合、最後の “” だけを考えれば十分と言うことに気付けば、このアルゴリズムにたどり着く。すなわち、必要なスタックは1段のみであるため、上のプログラムではそれをp0、s0と言う単純変数で済ませている。

構文解析

構文解析を行う機能のことをパーサなどと呼ぶが、この言葉はすっかりXMLパーサによっておなじみとなった。

先のドラゴンブックの例で扱っている文法は次のようになる。

プログラム ::= ( 式 “;” )*
式 ::= 項 ( ( “+” | “-” ) 項 )*
項 ::= 因子 ( ( “*” | “/” | “DIV” | “MOD” ) 因子 )*
因子 ::= “(” 式 “)” | 数値 | 変数

最初のルールを日本語で言えば、「プログラムとは、式とその後の“;”を任意の数だけつなげたもの」という意味である。このような文法の表現方法は、亜流がいろいろとあるが、おおむね(E)BNFなどと呼ばれている。他に文法の表現方法としてはPascalの教科書やORACLEのマニュアルに見られる構文図がメジャーであるが、(E)BNFはテキストとして簡単に書けると言う大きなメリットがある。

先ほどの例では、上記文法を再帰下降型構文解析によって処理し、その中でコード生成を行っている。

再帰下降型構文解析

言語処理系を手書きする場合、ほぼ間違いなくこの再帰下降型構文解析を利用することになる。上記例の文法を、素直にそのままプログラムに落とすことにより、人間にとって直感的に理解しやすいものとなる。反面、原理的に再帰的な手続き呼び出しとバックトラックを頻繁に行うことになるため、効率は良くない。また、文法が大きくなると、正しくプログラムすることが次第に困難となってくる。

構文解析の手法を分類する上で、この種類の構文解析はLL(型の)構文解析と呼ばれる。最初の “L” は、入力となる言語を左から順に処理していくと言う意味で、次の “L” は左から「導出」していくと言う意味である。

再帰下降型パーサを手で書く際、「先読み」のポリシーをあらかじめ決めておくのが肝である。定石としては、常に1トークン先読みして構文を解析していく手法を取る。

式「123 + 456」を解析しているとき、まず初項を処理するためにメソッドterm()が呼び出されるが、term()ではすでに最初のトークンを読み込み済みであることを想定している。つまり、まだ読んでいない部分は「+ 456」である。そこから最初に呼び出されるfactor()が処理すべき部分式は「123」のみであるが、これもすでに読み込み済みなのでfactor()はただちに数値を処理する機械語を生成することになるが、ここで忘れてはならないのが、factor()自身が必要としていなくても、ポリシーによってfactor()は次のトークンを先読みしてから呼び出し元に制御を戻すと言うことである。

LR構文解析

前節のLL構文解析に対して、LR構文解析と言う手法がある。こちらはその名の通り、左から入力し、右から導出する手法となる。伝統的なパーサジェネレータであるYACCが生成するパーサはこのタイプとなる。多くのプログラミング言語を処理でき、効率も良いパーサが実現できるが、手書きはほとんど不可能と言っていい。

直観的な文法となるLL型に比べて、LR型はかなり慣れが必要で、例えば

式 ::= 項 ( ( “+” | “-” ) 項 )*

は、LR用に書き直すと

式 ::= 項 | 式 ( “+” | “-” ) 項

となる。「式 ::= 式 “+” 項」のような形は左再帰と呼ばれる構造で、LR型文法においては繰り返し構造の鉄則であるが、これを再帰下降型で素朴に実装すると、即無限再帰となり、処理不能である。

LLとLRの導出方向の違いを最左導出と最右導出と言う言い方をするが、これは分かりにくい言葉であると思う。もっとわかりやすい言葉で、トップダウン解析、ボトムアップ解析と言う言い方がある。

「123 + 456」の例で言うと、LLが「式とは、項を1つ以上 “+” でつないだものだから、まず項があるはず」と考えるのに対し、LRは「数値の次に “+” が来た。数値は式と見なせる。…」と言うようにちょうど逆向きに考えて行く。

YACCについては以前の勉強会でも紹介したので、この辺りで切り上げよう。

注意:LLもLRも一長一短あり、特に優劣が決定できるわけではなく、効率が良いなどと言っているのは、あくまでYACCなどが吐き出すパーサの性質のこと。最近はむしろLL型パーサのジェネレータの方が流行っているかもしれない。詳しくは知らないが、きっと効率も悪くないのだろう。

かなり中途半端だが、今回はこの辺で。次回はPL/0か何かをやりたい。