AOJ 1314

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1314

構文解析といえばこの問題みたいなところあるよね。

まず左再帰を取り除きます。

assignment ::= var "=" expr "."
var ::= "A" | "B" | "C"

expr ::= term expr'
expr' ::= "+" term expr' | "-" term expr' | "e"

term ::= factor term'
term' ::= "*" factor term' | "e"

factor ::= primary | "-" factor

primary ::= inum primary' | var primary' | matrix primary' | "(" expr ")" primary'
primary' ::= "(" expr "," expr ")" primary' | "'" primary' | "e"

matrix ::= "[" row-seq "]"

row-seq ::= row row-seq'
row-seq' ::= ";" row row-seq' | "e"

row ::= expr row'
row' ::= " " expr row' | "e"

inum ::= digit inum'
inum' ::= digit inum' | "e"

digit ::= "0" | "1" | "2"

みたいになります。このBNFがLL1であることを証明します。つまり1文字読むだけで条件分岐が判別できることを示します。

First集合Follow集合は以下になります。First集合は下から、Follow集合は上から求める感じで計算すると楽です。

first(program) = {"A", "B", "C"}
first(program') = {"A", "B", "C"}
first(assignment) = {"A", "B", "C"}
first(var) = {"A", "B", "C"}
first(expr) = {"0", "1", "2", "A", "B", "C", "[", "(", "-"}
first(expr') = {"+", "-", "e"}
first(term) = {"0", "1", "2", "A", "B", "C", "[", "(", "-"}
first(term') = {"*", "e"}
first(factor) = {"0", "1", "2", "A", "B", "C", "[", "(", "-"}
first(primary) = {"0", "1", "2", "A", "B", "C", "[", "("}
first(primary') = {"(", "'", "e"}
first(matrix) = {"["}
first(row-seq) = {"0", "1", "2", "A", "B", "C", "[", "(", "-"}
first(row-seq') = {";", "e"}
first(row) = {"0", "1", "2", "A", "B", "C", "[", "(", "-"}
first(row') = {" ", "e"}
first(inum) = {"0", "1", "2"}
first(inum') = {"0", "1", "2", "e"}
first(digit) = {"0", "1", "2"}

follow(program) = {"$"}
follow(program') = {"$"}
follow(assignment) = {"A", "B", "C"}
follow(var) = {"=", "(", "'", "*", "+", "-", ".", ")", ",", " ", ";", "]"}
follow(expr) = {".", ")", ",", " ", ";", "]"}
follow(expr') = {".", ")", ",", " ", ";", "]"}
follow(term) = {"+", "-", ".", ")", ",", " ", ";", "]"}
follow(term') = {"+", "-", ".", ")", ",", " ", ";", "]"}
follow(factor) = {"*", "+", "-", ".", ")", ",", " ", ";", "]"}
follow(primary) = {"*", "+", "-", ".", ")", ",", " ", ";", "]"}
follow(primary') = {"*", "+", "-", ".", ")", ",", " ", ";", "]"}
follow(matrix) = {"(", "'", "*", "+", "-", ".", ")", ",", " ", ";", "]"}
follow(row-seq) = {"]"}
follow(row-seq') = {"]"}
follow(row) = {";", "]"}
follow(row') = {";", "]"}
follow(inum) = {"(", "'", "*", "+", "-", ".", ")", ",", " ", ";", "]"}
follow(inum') = {"(", "'", "*", "+", "-", ".", ")", ",", " ", ";", "]"}
follow(digit) = {"0", "1", "2", "(", "'", "*", "+", "-", ".", ")", ",", " ", ";", "]"}

ここからDirector集合を求めるんですが、'が付いている項にはFirst集合に"e"が含まれてないことがわかります。
なので'がついているもののみについて考えればよくて、

director(program') = {"A", "B", "C"} and {"$"} = empty
director(expr') = {"+", "-"} and {"{", ".", ")", ",", " ", ";", "]"} = empty
directort(term') = {"*"} and {"+", "-", ".", ")", ",", " ", ";", "]"} = empty
director(primary') = {"(", "'"} and {"*", "+", "-", ".", ")", ",", " ", ";", "]"} = empty
director(row-seq') = {";"} and {"]"} = empty
director(row') = {" "} and {";", "]"} = empty
director(inum') = {"0", "1", "2"} and {"(", "'", "*", "+", "-", ".", ")", ",", " ", ";", "]"} = empty

となります。全て空集合なのでこのBNFはLL1です。

あとは実装します。返り値をstate(mat, int)みたいにして、行列の値とどこまで解析したかのindexを持つようにしました。indexを持たせずに実装することもできるんですが、それだとデバッグがつらくなります。
あと'の付いている項は全て末尾再帰になっているので実装の際は単なる繰り返しに言い換えました。

string str;
string show(int a, int b) {
    return string(str.begin() + a, str.begin() + b);
}
map<char, mat> dict;
void program(int at);
state assignment(int at);
state expr(int at);
state term(int at);
state factor(int at);
state primary(int at);
state matrix(int at);
state rowseq(int at);
state row(int at);
state inum(int at);
 
void program(int at) {
    state s = assignment(at);
    rep(i, 0, sz(s.fst)) {
        rep(j, 0, sz(s.fst[0])) {
            cout << s.fst[i][j] << (j != sz(s.fst[0]) - 1 ? " " : "\n");
        }
    }
    while(s.sec < sz(str)) {
        s = assignment(s.sec);
        rep(i, 0, sz(s.fst)) {
            rep(j, 0, sz(s.fst[0])) {
                cout << s.fst[i][j] << (j != sz(s.fst[0]) - 1 ? " " : "\n");
            }
        }
    }
    // debug("program", show(at, s.sec));
}
state assignment(int at) {
    char c = str[at];
    state s = expr(at + 2);
    s.sec++;
    dict[c] = s.fst;
    // debug("assignment", show(at, s.sec));
    return s;
}
state expr(int at) {
    state s = term(at);
    mat res = s.fst;
    while(s.sec < sz(str) && (str[s.sec] == '+' || str[s.sec] == '-')) {
        if(str[s.sec] == '+') {
            s.sec++;
            s = term(s.sec);
            rep(i, 0, sz(res)) {
                rep(j, 0, sz(res[0])) {
                    ADD(res[i][j], s.fst[i][j]);
                }
            }
        }
        else {
            s.sec++;
            s = term(s.sec);
            rep(i, 0, sz(res)) {
                rep(j, 0, sz(res[0])) {
                    ADD(res[i][j], mod - s.fst[i][j]);
                }
            }
        }
    }
    // debug("expr", show(at, s.sec));
    return state(res, s.sec);
}
state term(int at) {
    state s = factor(at);
    mat res = s.fst;
    while(s.sec < sz(str) && str[s.sec] == '*') {
        s.sec++;
        s = factor(s.sec);
        if(sz(res) == 1 && sz(res[0]) == 1) {
                swap(res, s.fst);
        }
        if(sz(s.fst) == 1 && sz(s.fst[0]) == 1) {
            rep(i, 0, sz(res)) {
                rep(j, 0, sz(res[0])) {
                    MUL(res[i][j], s.fst[0][0]);
                }
            }
        }
        else {
            mat tmp(sz(res), vi(sz(s.fst[0]), 0));
            rep(i, 0, sz(res)) {
                rep(j, 0, sz(s.fst[0])) {
                    rep(k, 0, sz(s.fst)) {
                        ADD(tmp[i][j], res[i][k] * s.fst[k][j] % mod);
                    }
                }
            }
            res = tmp;
        }
    }
    // debug("term", show(at, s.sec));
    return state(res, s.sec);
}
state factor(int at) {
    state s;
    if(str[at] == '-') {
        s = factor(at + 1);
        rep(i, 0, sz(s.fst)) {
            rep(j, 0, sz(s.fst[0])) {
                s.fst[i][j] = (mod - s.fst[i][j]) % mod;
            }
        }
    }
    else s = primary(at);
    // debug("factor", show(at, s.sec));
    return s;
}
state primary(int at) {
    state s;
    if('0' <= str[at] && str[at] <= '9') {
        s = inum(at);
    }
    else if('A' <= str[at] && str[at] <= 'Z') {
        s.fst = dict[str[at]];
        s.sec = at + 1;
    }
    else if(str[at] == '[') {
        s = matrix(at);
    }
    else {
        s = expr(at + 1);
        s.sec++;
    }
    mat res = s.fst;
    while(s.sec < sz(str) && (str[s.sec] == '(' || str[s.sec] == '\'')) {
        if(str[s.sec] == '(') {
            s.sec++;
            s = expr(s.sec);
            mat a = s.fst;
            s.sec++;
            s = expr(s.sec);
            mat b = s.fst;
            s.sec++;
            mat tmp(sz(a[0]), vi(sz(b[0]), 0));
            rep(i, 0, sz(a[0])) {
                rep(j, 0, sz(b[0])) {
                    tmp[i][j] = res[a[0][i] - 1][b[0][j] - 1];
                }
            }
            res = tmp;
        }
        else {
            s.sec++;
            mat tmp(sz(res[0]), vi(sz(res), 0));
            rep(i, 0, sz(res)) {
                rep(j, 0, sz(res[0])) {
                    tmp[j][i] = res[i][j];
                }
            }
            res = tmp;
        }
    }
    // debug("primary", show(at, s.sec));
    return state(res, s.sec);
}
state matrix(int at) {
    state s = rowseq(at + 1);
    s.sec++;
    // debug("matrix", show(at, s.sec));
    return s;
}
state rowseq(int at) {
    state s = row(at);
    mat res = s.fst;
    while(str[s.sec] == ';') {
        s.sec++;
        s = row(s.sec);
        mat tmp(sz(s.fst) + sz(res), vi(sz(res[0]), 0));
        rep(i, 0, sz(res)) {
            rep(j, 0, sz(res[0])) {
                tmp[i][j] = res[i][j];
            }
        }
        rep(i, 0, sz(s.fst)) {
            rep(j, 0, sz(s.fst[0])) {
                tmp[i + sz(res)][j] = s.fst[i][j];
            }
        }
        res = tmp;
    }
    //debug("rowseq", show(at, nat));
    return state(res, s.sec);
}
state row(int at) {
    state s = expr(at);
    mat res = s.fst;
    while(str[s.sec] == ' ') {
        s.sec++;
        s = expr(s.sec);
        mat tmp(sz(res), vi(sz(res[0]) + sz(s.fst[0]), 0));
        rep(i, 0, sz(res)) {
            rep(j, 0, sz(res[0])) {
                tmp[i][j] = res[i][j];
            }
        }
        rep(i, 0, sz(s.fst)) {
            rep(j, 0, sz(s.fst[0])) {
                tmp[i][j + sz(res[0])] = s.fst[i][j];
            }
        }
        res = tmp;
    }
    // debug("row", show(at, s.sec));
    return state(res, s.sec);
}
state inum(int at) {
    int res = 0;
    int nat = at;
    while(nat < sz(str) && '0' <= str[nat] && str[nat] <= '9') {
        res *= 10;
        ADD(res, (str[nat] - '0'));
        nat++;
    }
    // debug("inum", show(at, nat));
    return state(mat(1, vi(1, res)), nat);
}
 
void solve() {
    while(true) {
        int Q; cin >> Q;
        if(Q == 0) break;
        str.clear();
        dict.clear();
        string s; 
        getline(cin, s);
        while(Q--) {
            getline(cin, s);
            str += s;
        }
        program(0);
        cout << "-----\n";
    }
}