nginxと奮闘
バグ潰し
卒論発表原稿用意,発表練習

Wordpressのドメイン変更

WordpressはドメインをDBに保持してる。　なので初回インストール時の後に、ドメインを変えるとDBのデータが変わらずそのままになってしまい、 CSS等のリンクがすべて古いものになってしまう。

これの対処

以前何回かやったことがあるが,今日は忘れていて,ググったら変なサイトばかり引っかかって辛かったのでやり方をメモしておく.

サイト URL の変更 - WordPress Codex 日本語版

基本的にはこれに従えば良い。

DBの変更で対応する場合は以下を行う

変更SQL

対象となる場所は wp_optionsテーブルのoption_nameがsiteurl及びhomeのレコードになる

もちろん記事の中で直リンしていたりすると色々なところで変換が必要(よくある全部置換）ではあるのだが、基本的にはここを変えるだけでCSSとかはなんとかなる。

以下クエリで対象は抽出できる

select * from wp_options where option_value = '設定したドメイン( ex https://wordpress.hoge.com)'

mysql> select * from wp_options where option_value = 'https://wp.bs-lab.ks.serviice.cloud.teu.ac.jp'; 
+-----------+-------------+----------------------------------------------+----------+
| option_id | option_name | option_value                                 | autoload |
+-----------+-------------+----------------------------------------------+----------+
|         1 | siteurl     | https://wp.bs-lab.ks.service.cloud.teu.ac.jp | yes      |
|         2 | home        | https://wp.bs-lab.ks.service.cloud.teu.ac.jp | yes      |
+-----------+-------------+----------------------------------------------+----------+
2 rows in set (0.00 sec)

こんな感じで出てくるのでこれをUpdateすればいい

update wp_options  set option_value = '新しいドメイン( ex https://mofumofu.com )'  where option_name = 'siteurl' OR option_name = 'home';

これで使えるようになる.

2018-01-25

Nginxで$argsや$request_uriの情報をサブリクエストに渡したい

今日したこと

nginxと眠い頭で格闘. 結局負けました. 今日はその話を書きます
rubyとか色々書いた
卒論発表スライドアウトラインバトル

Nginxでサブリクエスト

http_auth_requestモジュールを用いると,サブリクエストを行ってその結果でアクセス制御が実現できる.

{
   server_name: hoge.com;
   listen 443;

   location / {
        auth_request /auth;
        error_page 401 = @login_page;
        proxy_pass http://app.hoge.com;
   }
   location /auth {
        proxy_pass http://login.hoge.com/auth;
   }

   location @login_page {
        return 302 https://login.hoge.com/login;
   }
}

こんな具合に. 便利なもん.

ここで、http://hoge.com/?type=hogeのようなアクセスを考える, また認証エンドポイントであるlogin.hoge.comはtypeを内部で利用し401or200を決定する. この場合サブリクエストにtypeの値をなんとかして付与しなければならない.

以下試したこと

proxy_passに$argsを含める

proxy_pass http://login.hoge.com/auth$is_arg$args; こう設定する. $argsはリクエストのクエリパラメータが入るnginxの変数,なのでこれで渡るのではないだろうか？

＝＞　無理 $argsは空となり, http://login.hoge.com/auth に単なるGetが送られる.

$argsを一度適当な変数に代入しておきそれをHTTPヘッダに付与させ送ろう

set $original_arg $args;
location /auth {
   proxy_set_header X-Originl-Args $original_arg;
   proxy_pass http://login.hoge.com/auth;
}

これでlogin側ではHTTPヘッダから$argを取り出せるのではないか？？

＝＞　無理 $original_argは空となり,HTTPヘッダ付与は行われない.

惨敗

そもそもサブリクエスト時にコンテキストが切り替わり、$argとか$request_uriとかはすべてサブリクエスト時の値に切り替わっているっぽいことがわかった. なのでいつもの変数ではもともとの値を引くことができない?. そこそこ調べてもこうしてやった例を見つけることが出来なかった. Lua拡張を用いればおそらく引くことができるとは思うがデフォルトのNginxは変えたくない.

結局,色々とごにょって今回の問題には対処した時間もなかったし...

しかし以下のような解決策っぽいのを発見, 思いついた.

そもそも$request_uriなら取れるよ！

調べているうちに,argsは無理だが,request_uriなら引きずり出す方法を発見した.

stackoverflow.com

つまり. locationを正規表現でマッチさせ,そこでキャプチャを行う. キャプチャしたものを変数にsetする. あとは良しなにやるなるほど思いつかなかった....

proxyを２段階にすればいいじゃない

ブラウザ => nginx(1段) => nginx(2段) => (login , app) という構成にすることでも対応できることに気づいた.

nginxの1段目では$argを適当なHTTPヘッダにセットする,そして上で2段目へproxyする. 2段目はいつもどおりauth_requestを行った後APPへProxyする.

サブリクエスト時にHTTPヘッダは引き継がれるので,loginには(特に落とさなければ)HTTPヘッダとして1段目でセットしたHTTPヘッダが飛んでいくし, サブリクエスト時に参照できなくなる変数は$argとか$request_uriとかだけなので,2段目のnginxのコンフィグではサブリクエストの時の設定で１段目でセットしたヘッダを参照することができる.

どうでもいいはなし

運用中のサービスのDBの根本的変更をやるためにDBのデータとか,各所の設定値とかをすべて変更するスクリプトとか書いててめんどいなーっておもった. もっとちゃんとしっかり考えて作れよーという反省.

ボスがなんか、なまずくんに上げるよー！！っていってくれた.

tgさんがくれた pic.twitter.com/chMBB6M737
— namazu (@namazu510) 2018年1月25日

これは君がほしそうだから！！！　って... まぁ机の上や某所の壁にけもみみタペストリーとかグッズ大量においてればそうなるか... ふたりともかわいい＞＿＜!

2017-12-29

JavaでBasicライク言語のインタプリタ実装 #4 実行編

実践的プログラミング

今日書くこと

昨日の式の解析ができれば構文解析は完成したような物なので、構文解析はできたということで今日は実行の方の解説をしようと思います。なんかあれな理由で時間がないので、軽く書くだけ。

過去記事リンクは以下

namazu-tech.hatenablog.com

今日で完結です。（適当なネタが無くなってしまった）

実行

文字通りプログラムを実行することです。例えば a=1というコードであれば実際に、変数aを用意し、そこに1という値を代入する処理を行います。

また`PRINT "Hello"であればPRINT関数を実行します。

構文木 インスタンスと実行

構文木の要素(LoopBlockクラスなど）はそれ自体がどんな実行をすれば良いかを知っています。つまり、それぞれのクラスに対して、evel()メソッドを実装して、これを呼んでやればインスタンスがよしなにやってくれるようにします。オブジェクト指向って感じがしますね。

例えば、LoopBlockクラスのevel()メソッドは

子のCondNodeをevalしループ実行判定
実行するならStmtListを実行
繰り返す

という処理を行います。

ExprNodeクラスのeval()メソッドであれば単純に式を計算して１つの値を返すようにします。

それぞれの構文要素のクラスにあった計算方法をそれぞれのクラスのevalとして実装することで ProgramNodeのevalを呼ぶと再帰的に実行が行えるようになります。 (programはstmtlistのevalを行い、stmtlistのevalは子それぞれのevalを順々に呼び・・・と)

実行とEnviroment

これまで適当に扱ってきたEnviromentクラスが本気を出し始めます。

このクラスには、

変数テーブル
関数テーブル

を持たせ、変数を問い合わせする処理や新規定義する処理、関数を呼び出す処理などを行います。

実行中の変数テーブルとか関数テーブルをここに作っていくことになります。

関数定義を動的に行うことは今回の言語仕様にないので、関数テーブルについてはコンストラクタで決め打ちにしてしまえばいいと思います。

実装

AssigneStmt.java

代入文のクラスであるAssigneStmtならば、こんな感じにします。式を評価して、その結果をnameの変数に代入

   
    @Override
    public Value eval() {
        // 変数テーブルに入れる
        Value value = exprNode.eval();
        // Debug
        // System.out.println(name + "に" + value.getSValue() + "をいれる！");
        env.setVarValue(name, value);
        return null;
}

ここのenvはenviromentで変数テーブルを持ちます。

Enviroment.java

/**
 * 実行環境を持たせる.
 *
 * 変数名表とか関数テーブルとか
 */
public class Environment {
    
    private LexicalAnalyzer input;
    
    private Hashtable<String, Value> varTable;
    private Hashtable<String, Function> funcTable;
    
    public Environment(LexicalAnalyzer my_input) {
        input = my_input;
        varTable = new Hashtable<>();
        funcTable = new Hashtable<>();
        
        funcInit();
    }
    
    private void funcInit() {
        funcTable.put("PRINT", new PrintFunction());
        funcTable.put("SQRT", new SqrtFunction());
    }
    
    public LexicalAnalyzer getInput() {
        return input;
    }
    
    public void setVarValue(LexicalUnit varName, Value value) {
        varTable.put(varName.getValue().getSValue(), value);
    }
    
    public Value getVarValue(LexicalUnit varName) {
        Value res = varTable.get(varName.getValue().getSValue());
        if (res == null) {
            throw new IllegalStateException("存在しない変数を参照しようとしました！");
        }
        return res;
    }
    
    public void setFunc(LexicalUnit funcName, Function function) {
        funcTable.put(funcName.getValue().getSValue(), function);
    }
    
    public Function getFunction(LexicalUnit name) {
        Function res = funcTable.get(name.getValue().getSValue());
        if (res == null) {
            throw new IllegalStateException("存在しない関数を参照しようとしました！");
        }
        return res;
    }
}

こんなかんじで変数テーブルと関数テーブルを用意しておき、使えば良いでしょう。

関数定義と実行

/**
 * 平方根出す関数
 */
public class SqrtFunction extends Function {
    @Override
    public Value eval(ExprListNode arg) {
        Value val = arg.getValue(0);
        return new ValueImpl(Math.sqrt(val.getDValue()));
    }
}

こんなクラスをつくっておいて、enviromentのコンストラクタで、関数テーブルに登録します。

これで、

FunctionCallNodeクラスのevalで

   @Override
    public Value eval() {
        Function function = env.getFunction(name);
        return function.eval(exprList);
    }

こんな感じで使えるようになります。

IFBlockNode.java

IF文などの条件判定ノードやループノードの実行は小のCondNodeの評価を行って、ループを行ったり、どのStmtを実行するか決めたりすれば良いです。 IF文はIF-ELSEで続いてるときがあって、ちょっと面倒だったけど

@Override
    public Value eval() {
        Value condValue = cond.eval();
        if (condValue.getBValue()) {
            getThenNode().eval();
        } else {
            
            // 連続するIF文を実行する
            // ELSEIFですべてつながってるので順繰りにやっていく
            // どれか実行されたらevalElseIfNodeの戻り値がfalseで抜ける.
            int n = 0;
            while (evalElseIfNode(n)) {
                n++;
            }
            
            // 本体のELSEを実行する.
            if (getElseNode() != null) {
                getElseNode().eval();
            }
        }
        return null;
    }

こんなんでいけます。

さいご

駆け足で実行系を書いちゃったけどこんなんでいけるはずです。

構文木つくれたのなら余裕？。　

そろそろレポートの提出締め切りが近いようですが頑張って下さい。

書いてて思ったけどそんな難しくないけど実装量多いなって思いました。　

アノテーションで文法定義だけ書いてよしなにやる実装とかみたので、そうやるとSyntaxNode部分は大分分量を削れるかなぁと今になって思う。

まぁ頑張ってささっと終わらせちゃって下さい

どうでもいいはなし

今日はコミケ１日目でした。

やる気がないのでビックサイト周辺にいるけどならんでない
— namazu (@namazu510) 2017年12月28日

こんなんで、東京テレポートの方の橋の上に列が来たときに並ぶなんていう物見遊山勢してました。

お使いがけっこうあって、２つくらいいけば終わるはずが、普通に回ってしまいました。　これなら速く入ってさっさと終わらせとけばよかったなぁって今では反省しています。

明後日が本番なので体調に気をつけて準備していきたいですね。

今日は昔から買ってる毎度の藍様本、なぜか１日目にいたけもみみクラスタさん、性癖買いしたFGO本とかを買いました。昔１日目の始発で狙ってた狐サークルさんが艦これをずっと書いててしょぼーんです。　」

てか３日目のオリジナルの半分をどっかに隔離して１日目、２日目にやれば大分平和になると思うんだけどなんでしないんだろう？　

2017-12-28

JavaでBasicライク言語のインタプリタ実装 #3 構文解析編-2

実践的プログラミング

今日書くこと

JavaでBasicライク言語のインタプリタを作る。　講義の解説。今日は式の構文解析と構文木生成のところを細かく書きます。

これまでの記事は↓

namazu-tech.hatenablog.com

今回は式のクラスExprNodeの実装をざっと書きます。

式と構文木

式はBNF記法で

<expr> ::= 
　　　　<expr> <ADD> <expr>
    | <expr> <SUB> <expr>
    | <expr> <MUL> <expr>
    | <expr> <DIV> <expr>
    | <SUB> <expr>
    | <LP> <expr> <RP>
    | <NAME>
    | <INTVAL>
    | <DOUBLEVAL>
    | <LITERAL>
    | <call_func>


<call_func>   ::=
    　<NAME> <LP> <expr_list> <RP>

こう書けます。　つまり

SQRT((b * b) - (4 * a * c))

こんな式に対して

SQRT[SUB[MUL[b,b],MUL[MUL[4,a],c]]]

こんな結果が返ってくるようにすればいい。

式解析の攻略法

とりあえず逆ポーランド記法について知らなければググる。

qiita.com

この辺を参考に理解しましょう。　これがわかればあとは実装すればいいです。

1 + 2 * 3 みたいな標準入力を渡されて計算するプログラムをとりあえず書いてみるのがいいでしょう。

実装

実際にコードにするときには関数呼び出し中のカッコと普通のカッコとか、単項演算子の扱いとかがやっかい。

カッコがきたら対のカッコまでスタックからpopするとか、SUBが真っ先にやってくるor記号の後にSUBがくる場合は単項演算子適用対象みたいなことを考えると実直実装が面倒くさくなってくる。

/**
 * 式を計算.
 *
 * 1式を読みつつ逆ポーランド記法変換する
 * 2逆ポーランド記法の計算アルゴリズムを利用しツリーを生成する
 * 3生成したツリーを自信のインスタンスに適用する
 */
public class ExprNode extends Node {
    
    // 式の末端ならこれ
    private ExprEnd expression;
    
    // ２項式ならこっち
    private ExprEnd ope;
    private ExprNode left, right;
    
    public ExprNode(NodeType type, Environment env) {
        super(type, env);
    }
    
    public ExprNode(Environment env) {
        super(NodeType.EXPR, env);
    }
    
    public static Node isMatch(Environment env, LexicalUnit first) {
        FirstCollection fc = new FirstCollection(
                LexicalType.SUB,
                LexicalType.RP,
                LexicalType.NAME,
                LexicalType.INTVAL,
                LexicalType.DOUBLEVAL,
                LexicalType.LITERAL);
        
        if (fc.contains(first)) {
            Node node = new ExprNode(NodeType.EXPR, env);
            return node;
        }
        
        return null;
    }
    
    // Exprに含まれうる字句
    private static final Set<LexicalType> allowSet = new HashSet() {
        {
            add(LexicalType.NAME);
            
            add(LexicalType.LP);
            add(LexicalType.RP);
            
            add(LexicalType.INTVAL);
            add(LexicalType.DOUBLEVAL);
            add(LexicalType.LITERAL);
            
            add(LexicalType.ADD);
            add(LexicalType.SUB);
            add(LexicalType.MUL);
            add(LexicalType.DIV);
        }
    };
    
    // FunctionCallの時の括弧を式中の括弧か関数を閉じる括弧か見分けるための数値.
    boolean fcCallEnv = false;
    private int nest = 0;
    
    @Override
    public boolean parse() {
        
        // 読みつつ逆ポーランド記法へ
        // LexicalUnitのままだと困るからExprEnd 式末端ノードとして変換する
        
        // 演算子の連続は単項演算子. 数値が来るべき所に単項演算子きたらそれは単項演算子
        // ExprEndは記号を拡張出来るので単項演算子情報をつけておく
        
        // 逆ポーランド記法への変換のアルゴリズムはいくつかあるけどStackを使うやつが楽かな
        
        // 結果格納用
        Deque<ExprEnd> output = new ArrayDeque<>();
        
        // 単項演算子判別用. trueのときにSUBがきたらそれは単項演算子のSUB
        boolean expectValue = true;
        // 単項演算子バッファ.
        Deque<ExprEnd> singleOpeEnd = new ArrayDeque<>();
        
        // 演算子Stack
        Deque<LexicalUnit> opeStack = new ArrayDeque<>();
        while (true) {
            final LexicalUnit in = peekLexicalUnit();
            final LexicalType inType = in.getType();
            
            // 式構成要素じゃないものが飛んできた
            if (!allowSet.contains(inType)) {
                break;
            }
            env.getInput().get();
            
            // CALL SUBの処理
            if (inType == LexicalType.NAME) {
                // NAME -> RP はCALL SUB
                LexicalUnit test = env.getInput().get();
                if (test.getType() == LexicalType.RP) {
                    
                    // 　FCNのparse呼び出すために字句を戻す.
                    env.getInput().unget(in);
                    env.getInput().unget(test);
                    
                    // CALL SUBは必ず１つ値が返るから数値と同じと見なせる
                    // 優先順位０でOutputする
                    FunctionCallNode fcN = new FunctionCallNode(NodeType.FUNCTION_CALL, env);
                    if (!fcN.parse()) {
                        return false;
                    }
                    
                    // CALL SUB全体を末端ノードと見なして出力する
                    output.add(new ExprEnd(fcN, env));
                    
                    expectValue = false;
                    
                    continue;
                }
                env.getInput().unget(test);
            }
            
            if (inType == LexicalType.RP) {
                // RP ( はopeStackに入れる
                opeStack.push(in);
                
                nest++;
                
                continue;
            }
            
            if (inType == LexicalType.LP) {
                // LPが来たらopeStackからRPが出てくるまで出力する
                
                // 関数呼び出し内での閉じ括弧対応
                if (fcCallEnv && nest == 0) {
                    env.getInput().unget(in);
                    break;
                }
                
                LexicalUnit tmp;
                if (opeStack.size() == 0) {
                    return false;
                }
                while ((tmp = opeStack.pop()).getType() != LexicalType.RP) {
                    output.add(new ExprEnd(tmp, env));
                    
                    // （）の組み合わせがおかしい　-> 構文エラー
                    if (opeStack.size() == 0) {
                        return false;
                    }
                }
                
                nest--;
                
                continue;
            }
            
            final int priority = getPriority(inType);
            if (priority != 0) {
                
                // 単項演算子が現れたとき.
                if (expectValue == true) {
                    if (inType == LexicalType.SUB) {
                        // 単項演算子の優先度は最大
                        ExprEnd subEnd = new ExprEnd(in, env);
                        subEnd.isSingleOpe = true;
                        singleOpeEnd.add(subEnd);
                    }
                    continue;
                }
                
                // 優先度最高の単項演算子を全部出す.
                while (singleOpeEnd.size() != 0) {
                    output.add(singleOpeEnd.poll());
                }
                
                // 優先順位の高い演算子をすべて出し
                // スタックにいれる
                while (opeStack.size() != 0 && getPriority(opeStack.peekFirst().getType()) >= priority) {
                    output.add(new ExprEnd(opeStack.pop(), env));
                }
                expectValue = true;
                opeStack.push(in);
            } else {
                // 数値はそのまま出力
                output.add(new ExprEnd(in, env));
                
                expectValue = false;
            }
        }
        // 優先度最高の単項演算子を全部出す.
        while (singleOpeEnd.size() != 0) {
            output.add(singleOpeEnd.poll());
        }
        // 演算子バッファ全出力
        while (opeStack.size() != 0) {
            output.add(new ExprEnd(opeStack.pop(), env));
        }
        
        // DEBUG
        // output.forEach(System.out::println);
        // System.out.println("");
        
        // --------------
        // ここまででoutputに逆ポーランド記法で投入される
        // --------------
        
        // outputをツリーにする.
        
        // この方式思いっきり計算できる
        Deque<ExprNode> nodeStack = new ArrayDeque<>();
        while (output.size() != 0) {
            ExprNode in = output.pop();
            
            if (in instanceof ExprEnd) {
                ExprEnd endElm = (ExprEnd) in;
                if (endElm.isOpe) {
                    
                    // 単項演算子
                    if (endElm.isSingleOpe == true) {
                        if (nodeStack.size() < 1) {
                            // 計算不能だから ^ ^;
                            return false;
                        }
                        ExprNode expr = new ExprNode(env);
                        expr.left = nodeStack.pop();
                        expr.ope = endElm;
                        
                        nodeStack.push(expr);
                        continue;
                        
                    }
                    
                    // ２項演算子
                    if (nodeStack.size() < 2) {
                        // 計算不能だから＾＾；
                        return false;
                    }
                    
                    ExprNode expr = new ExprNode(env);
                    expr.right = nodeStack.pop();
                    expr.left = nodeStack.pop();
                    expr.ope = endElm;
                    
                    nodeStack.push(expr);
                    continue;
                    
                }
                // 演算子以外はスタックに入れる
                nodeStack.push(endElm);
            }
            
        }
        
        // 何で計算しないでツリーにしちゃったのか謎だけど構文木つくらないとだからね・・・
        // とりあえずこれでツリー完成
        
        // 自分のインスタンスに適用する
        ExprNode expr = nodeStack.pop();
        if (expr.isEnd()) {
            this.expression = (ExprEnd) expr;
        } else {
            this.left = expr.left;
            this.right = expr.right;
            this.ope = expr.ope;
        }
        
        // DEBUG:
        // System.out.println(expr);
        
        return true;
    }
    
    private int getPriority(LexicalType type) {
        // 0 は数値
        switch (type) {
        case MUL:
            return 3;
        case DIV:
            return 3;
            
        case SUB:
            return 2;
            
        case ADD:
            return 2;
            
        case RP:
        case LP:
            return -1;
            
        case INTVAL:
        case DOUBLEVAL:
        case LITERAL:
        case NAME:
            return 0;
            
     default:
            throw new IllegalArgumentException("優先度なんてないLexicalType:" + type.name());
        }
    }
    
    /**
    * 与えたLexicalTypeが式のなかで使われる演算子ならtrue
    *  + or - or / or *
    */
    public boolean isOpe(LexicalType lt) {
        Set<LexicalType> opeSet = new HashSet() {
            {
                add(LexicalType.ADD);
                add(LexicalType.SUB);
                add(LexicalType.DIV);
                add(LexicalType.MUL);
            }
        };
        
        return opeSet.contains(lt);
    }
    
    /**
    * このExprが末端かどうか返す.
    * （枝分かれしないかどうか）
    */
    protected boolean isEnd() {
        // TODO: もうちょっとちゃんとチェック
        if (left == null) {
            return true;
        }
        return false;
    }
    

    @Override
    public String toString() {
        // 5 -> 5 , a - 1 -> -[a, 1]
        
        // 末端
        if (isEnd()) {
            return expression.toString();
        }
        
        // 単項
        if (this.right == null) {
            return String.format("%s[%s]", ope.toString(), left.toString());
        }
        
        // 二項
        return String.format("%s[%s,%s]", ope.toString(), left.toString(), right.toString());
    }
    
}

/**
 *　Exprの末端ノード
 */
class ExprEnd extends ExprNode {
    
    // 演算子Nodeか？
    boolean isOpe;
    
    // 単項演算子か？
    boolean isSingleOpe;
    
    // 字句
    LexicalUnit val;
    
    // 関数呼び出し値か？
    boolean isFcval;
    // 関数呼び出しNode
    FunctionCallNode fcval;
    
    public ExprEnd(LexicalUnit val, Environment env) {
        super(env);
        this.val = val;
        this.isOpe = isOpe(val.getType());
    }
    
    public ExprEnd(FunctionCallNode fcN, Environment env) {
        super(env);
        this.fcval = fcN;
        this.isFcval = true;
        isOpe = false;
    }
    
    @Override
    public String toString() {
        if (isFcval) {
            return fcval.toString();
        }
        if (isOpe) {
            return val.getType().name();
        }
        return val.getValue().getSValue();
    }
    
    @Override
    protected boolean isEnd() {
        return true;
    }
}

まぁこんなんでいけます。

さいご

時間がなくて書きなぐり感すごい。

あしたはもっと書きなぐりになる。明日は実行系、eval()メソッドの実装の話を書きます。

2017-12-27

JavaでBasicライク言語のインタプリタ実装 #2 構文解析編-1

実践的プログラミング

今日書くこと

今日は昨日から続いている、「JavaでBasicライクな言語のインタプリタを実装する」の第2回目の記事です。昨日の記事は

namazu-tech.hatenablog.com

こちらになります。

今日は構文解析の部分を解説＆実装していこうと思います。

構文解析

構文解析とは？

構文解析とは、字句の並びから、プログラム言語の文法(Syntax)と照らし合わせAST（抽象構文木)を作ることです。よくあるシンタックスエラー（かっこの対がおかしいとか、for文の使い方が間違ってる）などはこの段階で判明するわけですね。

具体的には

a = 5
DO UNTIL a < 1
PRINT "HELLO"
a = a -1
LOOP
END

このようなプログラムを読み込んで、

f:id:kituneko-510:20171227140051p:plain

のような構文木を構築することです。

Do untilのブロック内に関数実行と代入文があり、代入文はaにa-1の結果を入れる。と言うような意味が発生するようになります。

字句解析の時点では、それぞれどんな字句かだけだったのが、字句の並びと文法規則からそれぞれ意味を持つようになります。

文法

ボスが文法を示してくれるのでそれを参考にしましょう。

https://service.cloud.teu.ac.jp/lecture/CSF/ktago/lecture_prog/syntax.txt

BNF記法で書いてあるやつですね。　これとにらめっこしながら作ります。

構文解析部分攻略方

ファースト集合とかフォロー集合とか、終端記号とか非終端記号とかの単語をちゃんと理解しましょう。 kmd先生の講義を取ればちゃんと教えてくれる上に、構文解析表とかも書けるようになります。

ボスもなんだかんだそれっぽいことを教えてくれるけどね。　

この部分は基本的にひたすら実装なので流れをつかんで時間があるときにやってください。式の部分は明日解説しますが、そこだけちょっと面倒。　

実装

実装方針

非終端要素についてクラスを１つ１つ作ります。それぞれのクラスはNodeクラスを継承するようにします。

Nodeクラスは抽象クラスとしparse()の関数実装を強制します。

Nodeクラスを継承した非終端要素のクラスでisMatch()とparse()を実装します。

isMatchは、与えられた字句が、その非終端要素のファースト集合に含まれるかどうかを判定し、含まれるならば自身をインスタンス化して返します。また、今回の文法はLL2である（２個先まで読まないとどの文法規則を適用すればいいか確定しない cf 代入文(NAME => EQ)と関数呼び出し(NAME => LP))のでそういう重複がありえる非終端要素の場合は確定させるまで読んで返します。

parseは、字句を読み進め、自分の下の要素を構築したりします。

コードで示した方が早そうなので書いていきます。

すべての実装は、

github.com

にあります。　syntax_nodeパッケージが今回の非終端要素のクラス群が入っているところです。

それでは。

Node.java

大本のクラスです。すべての非終端要素のクラスはこれを継承させます。

/**
 * 全構文要素の親クラス.
 * 構文木の非終端要素
 */
public abstract class Node {
    /**
    * Nodeのタイプ.
    */
    public final NodeType type;
    
    /**
    * 実行環境.
    * 変数テーブル. 関数テーブル. 字句解析器等.
    */
    public final Environment env;
    
    public Node(NodeType type, Environment env) {
        this.type = type;
        this.env = env;
    }
    
    public NodeType getType() {
        return type;
    }
    
    /**
    * 文法解析メソッド
    * @return 構文にマッチしないならfalse
    */
    public abstract boolean parse();
    
    // toStringの実装を強制
    public abstract String toString();
    
    /**
    * 次のLexicalUnitを見る Utilメソッド
    */
    protected LexicalUnit peekLexicalUnit() {
        LexicalUnit unit = env.getInput().get();
        env.getInput().unget(unit);
        return unit;
    }
    
    /**
    * 次の字句タイプを見て期待した字句と一致していればその字句を読み飛ばすUtilメソッド
    * NLとかLOOPとかのチェックしないといけないけど無視する字句に使う
    *
    * もし次に現れた字句が期待した物と一致しないのであればfalseを返す
    *
    * @param expectType 複数指定した場合は指定した順番でチェックしつつ読み飛ばす
    * @return 期待した字句と一致しない場合false
    */
    protected boolean skipExpectNode(LexicalType... expectType) {
        for (LexicalType expect : expectType) {
            if (peekLexicalUnit().getType() == expect) {
                env.getInput().get();
                continue;
            }
            return false;
        }
        return true;
    }
}

ポイントとしては、Nodeクラスにある程度のUtilメソッドを含めておくと楽です。　例えばpeekLecicalUnitは単に次の字句を見ることができます。 skipExpcetNodeは字句をチェックしつつ読み流すときに使います。　この処理はなんども後で出てくるので一括してここで定義しておくといいです。

ProgramNode.java

Nodeを継承した、構文木のトップ要素のProgramNodeは以下のように書けます

/**
 * <program>  ::=
 *              <stmt_list>
 *
 */
public class ProgramNode extends Node {
    
    // StmtListNode
    private Node child;
    
    public ProgramNode(NodeType type, Environment env) {
        super(type, env);
    }
    
    static FirstCollection fc = new FirstCollection(
            StmtListNode.fc,
            BlockNode.fc
            );
    
    public static Node isMatch(Environment env, LexicalUnit first) {
        // LexicalUnit first が　First集合に含まれる字句か判断する.
        if (fc.contains(first)) {
            return new ProgramNode(NodeType.PROGRAM, env);
        }
        
        return null;
    }
    
    @Override
    public boolean parse() {
        NextNodeList nextNodeList = new NextNodeList(StmtListNode.class);
        Node chiled = nextNodeList.nextNode(env, peekLexicalUnit());
        if (chiled != null) {
            this.child = chiled;
            return chiled.parse();
        }
        return false;
    }
    
    @Override
    public String toString() {
        return child.toString();
    }
    
}

isMatchではProgramノードのファースト集合に含まれるかを判定させます。ここでProgramノードのファースト集合はStmtListNodeのファースト集合とBlockNodeのファースト集合の和集合であるということに気づくとコードがきれいになります。

この和集合を扱うために以下のようなことをします。

/**
 * First集合のコレクション.
 *
 */
public class FirstCollection {
    List<LexicalType> firstListUnit;
    
    public FirstCollection(LexicalType... firstTypes) {
        this.firstListUnit = Arrays.asList(firstTypes);
    }
    
    public FirstCollection(FirstCollection... firstCollections) {
        this.firstListUnit = new ArrayList<>();
        for (FirstCollection firstCollection : firstCollections) {
            firstListUnit.addAll(firstCollection.firstListUnit);
        }
    }
    
    public boolean contains(LexicalUnit unit) {
        LexicalType type = unit.getType();
        return firstListUnit.contains(type);
    }
}

このようなFirst集合を合わせたりして扱うことができるクラスを用意しておき、上位のfirst集合は直接字句を書かず、子のファースト集合の和集合として定義するときれいです。

   static FirstCollection fc = new FirstCollection(
            StmtListNode.fc,
            BlockNode.fc
            );

こんな感じでね。

parse()は子のisMatch(stmtlistのisMatch)を呼び、自身のフィールドに子のインスタンスを保持するようにします。こうして、ProgramがフィールドにStmtListのインスタンスを持ち、StmtListがフィールドにAssignStmtやLoopBlockのインスタンスを持ち。。。と順々につなげていくことでリンクするように、構文木が表現できます。

またコードをさくっと終わらせるために、一々isMatchを呼び出して確定させる等の処理は面倒（子に持ちうるのが複数の非終端要素の場合があり得て、何個もisMatchを呼ばなきゃいけない）なので、

/**
 * 子になりうるNodeのリスト.
 *
 * first集合の字句を投げて、子のnodeのインスタンスが得られるUtilクラス
 *
 * 必須要件.
 * 登録されたNodeにはisMatchが静的メソッドとして実装されている
 */
public class NextNodeList extends ArrayList<Class<? extends Node>> {
    
    public NextNodeList(Class<? extends Node>... nextNodes) {
        addAll(Arrays.asList(nextNodes));
    }
    
    /**
    * 次の一致するノードを探し出す.
    */
    public Node nextNode(Environment env, LexicalUnit unit) {
        Iterator<Class<? extends Node>> i = iterator();
        while (i.hasNext()) {
            Method isMatch;
            try {
                isMatch = i.next().getMethod("isMatch", Environment.class, LexicalUnit.class);
                Object res = isMatch.invoke(null, env, unit);
                
                if (res != null) {
                    return (Node) res;
                }
                
            } catch (NoSuchMethodException | SecurityException | IllegalAccessException | IllegalArgumentException
                    | InvocationTargetException ex) {
                // programming error
                ex.printStackTrace();
            }
        }
        return null;
    }
}

こんなちょっとごにょってるクラスを作ってしまい、

NextNodeList nextNodeList = new NextNodeList(StmtListNode.class);
Node chiled = nextNodeList.nextNode(env, peekLexicalUnit());

こんな感じで一気に処理すればisMatchをNextNodeListに登録したクラス全部に試行して、確定した子ノードのインスタンスを返してくれるnextNodeメソッドが使えるようになります。

リフレクションしたのは反則感があるけど。

StmtListを作ったら、似たような感じでどんどん構文を下に向かって作っていきます。（ExprNode以外はノリでいけます）

StmtListNode.java

/**
 * <stmt_list>　::=
 *         <stmt>
 *         | <stmt_list> <NL> <stmt>
 *         | <block>
 *         | <block> <stmt_list>
 *
 */
public class StmtListNode extends Node {
    private List<Node> childNodes = new ArrayList<>();
    
    public StmtListNode(NodeType type, Environment env) {
        super(type, env);
    }
    
    static FirstCollection fc = new FirstCollection(
            StmtNode.fc,
            BlockNode.fc
            );
    
    public static Node isMatch(Environment env, LexicalUnit first) {
        if (fc.contains(first)) {
            return new StmtListNode(NodeType.STMT_LIST, env);
        }
        return null;
    }
    
    @Override
    public boolean parse() {
        while (true) {
            // NLを読み飛ばす
            if (peekLexicalUnit().getType() == LexicalType.NL) {
                env.getInput().get();
                continue;
            }
            
            NextNodeList nextNodeList = new NextNodeList(StmtNode.class, BlockNode.class);
            Node chiled = nextNodeList.nextNode(env, peekLexicalUnit());
            if (chiled != null) {
                if (!chiled.parse()) {
                    return false;
                }
                // Stmtの後にはNLが存在する
                if (chiled instanceof StmtNode) {
                    env.getInput().get();
                }
                childNodes.add(chiled);
                continue;
            }
            return true;
        }
    }
    
    @Override
    public String toString() {
        return childNodes
                .stream()
                .map(Node::toString)
                .collect(Collectors.joining(";"));
    }
}

StmtListも同じように、ファースト集合はStmtNodeとBlockNodeのファースト集合の和集合になるので、ProgramNodeと同じように定義します。 parseもStmtListの下はStmtNodeかBlockNodeなので、どちらか調べてさらにそれぞれparseしていきます。子のparseに成功したら、自身のフィールドで子ノードとして保持しておきます。

LoopBlockNode.java

だんだん下のほうの非終端要素になると、終端要素をチェックしたり色々が始まります。 LOOPとかはその最たる例。　DO や　UNTILとかがちゃんと正しい順番で入ってるかチェックしないとだめ

/**
 * <block> ::=
 *         | <WHILE> <cond> <NL> <stmt_list> <WEND> <NL>
 *         | <DO> <WHILE> <cond> <NL> <stmt_list> <LOOP> <NL>
 *         | <DO> <UNTIL> <cond> <NL> <stmt_list> <LOOP> <NL>
 *         | <DO> <NL> <stmt_list> <LOOP> <WHILE> <cond> <NL>
 *         | <DO> <NL> <stmt_list> <LOOP> <UNTIL> <cond> <NL>
 */
public class LoopBlockNode extends Node {
    
    /**
    * Do While 文　つまり１度は走る文かどうか
    */
    private boolean isDo;
    
    /**
    * While文ならtrue Until文ならfalse
    */
    private boolean isWhile;
    
    /**
    * ループ実行条件ノード
    */
    private CondNode condNode;
    
    /**
    * ループブロック本体
    */
    private StmtListNode stmtListNode;
    
    public LoopBlockNode(NodeType type, Environment env) {
        super(type, env);
    }
    
    static FirstCollection fc = new FirstCollection(
            LexicalType.WHILE,
            LexicalType.DO
            );
    
    public static Node isMatch(Environment env, LexicalUnit first) {
        if (fc.contains(first)) {
            return new LoopBlockNode(NodeType.LOOP_BLOCK, env);
        }
        return null;
    }
    
    @Override
    public boolean parse() {
        LexicalUnit first = env.getInput().get();
        // DO
        if (first.getType() == LexicalType.DO) {
            return doParse();
        }
        // WHILE
        if (first.getType() == LexicalType.WHILE) {
            return whileParse();
        }
        return false;
    }
    
    /**
    * Do文を解析
    * @return
    */
    private boolean doParse() {
        isDo = true;
        
        LexicalUnit next = env.getInput().get();
        switch (next.getType()) {
        case WHILE:
        case UNTIL:
            // do - (while or until) - cond -nl -stmtlist - loop - nl
            untilOrWhileHandl(next);
            if (!condHandl()) {
                return false;
            }
            if (!skipExpectNode(LexicalType.NL)) {
                return false;
            }
            if (!stmtListHandl()) {
                return false;
            }
            if (!skipExpectNode(LexicalType.LOOP, LexicalType.NL)) {
                return false;
            }
            return true;
        case NL:
            // do - nl - stmtlist - loop - (while or until) - cond -nl
            if (!stmtListHandl()) {
                return false;
            }
            if (!skipExpectNode(LexicalType.LOOP)) {
                return false;
            }
            if (!untilOrWhileHandl(env.getInput().get())) {
                return false;
            }
            if (!condHandl()) {
                return false;
            }
            if (!skipExpectNode(LexicalType.NL)) {
                return false;
            }
            return true;
     default:
            return false;
        }
        
    }
    
    /**
    * While文を解析
    * @return
    */
    private boolean whileParse() {
        isDo = false;
        isWhile = true;
        
        // while -> cond -> nl -> stmtlist -> loop -> nl
        if (!condHandl()) {
            return false;
        }
        if (!skipExpectNode(LexicalType.NL)) {
            return false;
        }
        if (!stmtListHandl()) {
            return false;
        }
        if (!skipExpectNode(LexicalType.LOOP, LexicalType.NL)) {
            return false;
        }
        return true;
    }
    
    /**
    * Loopブロックの条件式部分を解析
    * @return SyntaxErrorならfalse
    */
    private boolean condHandl() {
        condNode = (CondNode) CondNode.isMatch(env, peekLexicalUnit());
        if (condNode == null || !condNode.parse()) {
            return false;
        }
        return true;
    }
    
    /**
    * LoopブロックのStmtList部分を解析
    * @return SyntaxErrorならfalse
    */
    private boolean stmtListHandl() {
        stmtListNode = (StmtListNode) StmtListNode.isMatch(env, peekLexicalUnit());
        if (stmtListNode == null || !stmtListNode.parse()) {
            return false;
        }
        return true;
    }
    
    /**
    * Until文なのかWhile文なのか調べてインスタンス変数に情報格納
    * @param unit Until or Whileの　LexicalUnit
    */
    private boolean untilOrWhileHandl(LexicalUnit unit) {
        switch (unit.getType()) {
        case WHILE:
            isWhile = true;
            return true;
            
        case UNTIL:
            isWhile = false;
            return true;
        }
        
        return false;
    }
    
    @Override
    public String toString() {
        return "LOOP[" + condNode + "[" + stmtListNode + "]]";
    }
}

こんな感じでいけます。　そろそろ長くなって辛くなってきた。 LOOPのチェックとかがちゃんとできればあとは流れでほかのNodeも作れるでしょ。

さいご

ファースト集合とか、構文解析表とか知ってれば、あとは構文木をどんな感じに構成すればいいか（フィールドに子を持たせる）を思いつけばコードにできますね。

ここはひたすら実装が必要なのでだるいところ。　BNF記法流し込んだら構文木自動構築みたいなことしないかぎり実装はそんな面倒じゃない。

明日は構文木を組み上げるうえで一番面倒くさい式の解析の部分を書こうと思います。

2017-12-26

JavaでBasicライク言語のインタプリタ実装 #1 字句解析編

実践的プログラミング

これから書く記事の概要

実践的プログラミング

弊学では３年次にJavaでBasicライク言語のインタプリタを実装する、「実践的プログラミング」という講義があります。

弊研のボスがやっている、プログラミング力を一気に上げる講義です。　弊研究室に所属した場合、この講義の単位の修得が要求されます。

よく単位とれないと進級できないとかいう嘘を流してる人が居ますが、あれは嘘です。　履修も絶対しなきゃいけないわけじゃないです。進級条件にかかってない適当な枠の講義をの単位をネタにそれで進級させないとかして、ゴネたら面倒になるでしょ。　過去に単位取らずに卒業した人も居ます。

ただ、別に面倒なわけじゃないし＆プログラム将来書くなら役に立つこと間違いなしの講義なので、積極的に受けないって方針は採らなくていいと思います。

講義の扱い的には、「実質強制参加の会社の忘年会」的な扱いだと思って下さい。　わたしはまだ忘年会未経験なので本当に合ってるかはわかりませんけど。

この講義、なんか毎度よくわからんと言い始める人がいっぱい居ます。　今年も研究室で騒いでいる人がいっぱい居るので、ほら簡単やろ？って証明するために去年私が作ったコードをひたすら載せつつ、解説します。

成果物

最終的にこんなのが作れますよ。

PRINT "x^2 -8x -16"
a = 1
b = -8
c = -16

def = SQRT((b * b) - (4 * a * c))
res1 = ( -b - def) / 2 * a
res2 = ( -b + def) / 2 * a

PRINT "x = (" + res1 + "," + res2 + ")"

Syntax parsed ---
PRINT[x^2 -8x -16];a[1];b[SUB[8]];c[SUB[16]];def[SQRT[SUB[MUL[b,b],MUL[MUL[4,a],c]]]];res1[MUL[DIV[SUB[SUB[b],def],2],a]];res2[MUL[DIV[ADD[SUB[b],def],2],a]];PRINT[ADD[ADD[ADD[ADD[x = (,res1],,],res2],)]]
-----------------
-------run!------
x^2 -8x -16
x = (-1.6568542494923806,9.65685424949238)

連載目次

１日で全部書くと長くなるので何日かに分けて書いて公開していこうと思います。

講義の流れとして　字句解析＝＞構文解析＝＞実行系　という形でプログラムを作っていくので、それに添った形で書いていきます。

26日、全体概要&講義の攻略法&字句解析部分
27日、　構文解析部分　その１
28日、　構文解析部分　その２　（式解析部分）
29日、　実行系

というスケジュールで行きます。書きためしてコミケ中のネタ用に数日増やすかもしれません。

さて書いていきます。　今日は講義攻略のおすすめ方針と、第一回のレポートのネタになる字句解析部分のプログラム解説をします。

講義攻略方針

この講義の難易度は、３年次に並行して走ってる kmd先生の「形式言語とオートマトン」 という講義を取ったかどうかで天と地の差が生まれます。基本的にプログラミング言語の構成を知っていればインタプリタの作り方は分かるので、コンパイラの作り方を説明するkmd先生の講義を取り概略をつかめば何をすれば良いか全部分かります。

この講義を取るか、コンパイラの作り方を一度どっかで勉強したことがあれば特に困ることはありません。

逆にしていないとよくわからなくなります。ボスの説明を頑張って聞いて作りましょう。

字句解析

字句解析とは

字句解析とは素のプログラムを読み込んで、書かれている単語のまとまりを作り、１つ１つにどういう意味があるのか判明させる処理です。

具体的には、

a = 1

という素のプログラムから a , = , 1 と分割し、それぞれa(変数名)、=(演算子 Equal)、1(値,整数, 1) というように意味をラベル付けしていきます。

要求される動作

レポートではこれを満たす必要があります。

以下の入力を受け取り

a = 50.1
DO UNTIL a < 1
   PRINT "Hello"
   a = a - 10
LOOP
END

以下の出力を行うこと

NAME: a
EQ
DOUBLEVAL: 50.1
NL
DO
UNTIL
NAME: a
LT
INTVAL: 1
NL
NAME: PRINT
LITERAL: Hello
NL
NAME: a
EQ
NAME: a
SUB
INTVAL: 10
NL
LOOP
NL
END
EOF

字句解析部分の攻略方

kmd先生の講義を取っていれば、字句解析は正規表現と深い関わりがあり、(普通の)正規表現は有限オートマトンで処理できるーということを知ることが出来ます。取ってない人も今知りましたね？　

字句はすべて正規表現で表現が可能です。　

WORD(a, DO, WHILE, END) => ^[a-zA-Z]\\w*
LITERAL("hogehgoe") => ^\"[^\"]*\"?
NUMBER (4423, 4.2) => [0-9.]+
一字のOPERATER( =, + , - +=) => [\\.\n\\+\\-\\*\\/\\)\\(,]

こんな感じですね。(全部は網羅してません＆複数の字句がマッチする場合あり）　

読み込んだプログラムをの状態遷移図を作成し、最適化を施し、その状態遷移を実現するようにJavaのコードを書けば字句判定が完成します。これがお作法っぽい作り方です。　

ただし、状態遷移図からJavaのコードをIFやループを使って生み出すと面倒なので、字句を正規表現で表した後、Javaの標準ライブラリに正規表現処理をさせてやればいいです。

ここで正規表現処理エンジンを作らせたるよう強制しないのがボスの優しさですね。　正規表現エンジンも作ったりした方が良いと思うんだけどなぁ。

アルゴリズム

１つの字句は以下の手順で得られる.

字句の始まりとなり得る文字(英数字, 記号, 改行文字) を得る
その文字が, 変数or 予約語, 数字, リテラル, 演算子のどれに該当するのか判断する
対応する種別に応じて字句に許容されない文字が現れるまでソースを読み, 初めの字から許容されない文字が現れるまでの文字をつなげた物を１字句の内容とする
得られた文字列に対して実際にどのような字句なのか, 予約語なのか, どの演算子なのか等をより細かく見て字句を確定し出力する

ソースコードを読みこみながら、上記手順を繰り返すことでソースコードから字句を１つずつ取り出すことが出来ます。

コードの書きやすさ的には、これを実装に移すのが一番さっくりいくと思います。　実装にJava力をちょっと必要としますが。。。。

実装

すべての実装は

github.com

にあります。lexical_parserパッケージ及びcoreパッケージが字句解析に関連した部分です。

メインエントリポイント

public class Main {
    
    public static void main(String[] args) throws Exception {
        LexicalAnalyzer analyzer = new LexicalAnalyzerImpl("test1.bas");
        
        LexicalUnit unit;
        for (unit = analyzer.get(); unit.type != LexicalType.EOF; unit = analyzer.get()) {
            System.out.println(unit);
        }
        System.out.println(unit);
        
    }
    
}

字句を切り出しLexicalUnit作る処理部分

アルゴリズムに基づいてまず大まかに分けるようにします。　ここを正規表現でやるのがコード簡略化のこつです。

public enum TokenType {
    NUMBER("[0-9.]+"), // 0-9から始まりdotを含んで連続する(笑)
    WORD("^[a-zA-Z]\\w*"), // A-Za-zから始まって単語構成文字が連続する
    LITERAL("^\"[^\"]*\"?"), // "から始まりε　"があったらそれでおしまい.（エスケープシーケンス）
    SINGLE_OPERATOR("[\\.\n\\+\\-\\*\\/\\)\\(,]"), // １文字で構成される字句
    MULTY_OPERATOR("[><=]|=[><]|[><]=|<>"); // 　複数文字で構成されうる演算子 > < = =>　>= =<
                                            // <= <>
    
    private final Pattern pattern;
    
    private TokenType(String regx) {
        this.pattern = Pattern.compile(regx);
    }
    
    public boolean isMatch(String test) {
        return pattern.matcher(test).matches();
    }
}

定義的に正規表現を埋め込んだこのEnumを使って、一気に処理します。　

下のクラスはソースコード（テキスト）を１文字ずつよんで、なんか意味ある始めの一字（EOFやスペースではなく次のTokenを構成する１字）まで読み、上のEnumのマッチを使ってどれか確定させ、tokenにします。

/**
 * Streamを読んでTokenに切り出すクラス.
 * テキストデータを１文字ずつよんでTokenに分割
 */
public class TokenParser {
    
    /**
    * テキストデータ読み込みReader
    */
    private Reader reader;
    private boolean readerIsEOF = false;
    
    public TokenParser(Reader reader) {
        super();
        this.reader = reader;
    }
    
    /**
    * 字句確定のためにreadしちゃった次の字句を持っておく
    */
    private String nextTokenBuff = "";
    
    /**
    * 次のTokenを得ます.
    */
    public Token get() {
        
        if (readerIsEOF == true) {
            return null;
        }
        
        // EOFやスペースではなく次のTokenを構成する１字を得る
        String tokenFirstStr = normalizeStr(nextTokenBuff);
        if (!readerIsEOF && tokenFirstStr.isEmpty()) {
            tokenFirstStr += readNextStr();
        }
        
        // トークン始まりの字にマッチするtokenTypeを得る
        TokenType tokenType = getMatchTokenType(tokenFirstStr);
        
        // マッチが外れ、違う字句になるまで読みTokenの値を得る
        String tokenVal = tokenFirstStr;
        while (!readerIsEOF && tokenType.isMatch(tokenVal)) {
            tokenVal += readNext();
        }
        
        // マッチ外れたときに入ったアルファベットは次の字句の可能性ありありなので保持　
        // cf. a= はa=のときにマッチが外れるが=はそれ自体次の字句
        this.nextTokenBuff = String.valueOf(tokenVal.charAt(tokenVal.length() - 1));
        
        // 出力するトークンからは次の字句の文字は消す
        tokenVal = tokenVal.substring(0, tokenVal.length() - 1);
        
        return new Token(tokenType, tokenVal);
    }
    
    /**
    * TokenTypeからTokenTypeのパラメータに一致するやつ探し出す.
    * <始めの１字がどのトークンタイプか判別する.>
    * @param tokenFirstStr Tokenの初めの１字
    */
    private TokenType getMatchTokenType(String tokenFirstStr) {
        
        Optional<TokenType> tokenTypeOpt = EnumSet.allOf(TokenType.class)
                .stream()
                .filter(t -> t.isMatch(tokenFirstStr))
                .findFirst();
        
        return tokenTypeOpt.get();
    }
    
    /**
    * 文字を標準化
    * CRをスペースに　（LFだけにする）
    * タブはスペースに
    * 最後にスペースは消し去ります
    */
    private String normalizeStr(String str) {
        return str
                .replaceAll("\t", "  ")
                .replace('\r', ' ')
                .replaceAll(" ", "");
    }
    
    /**
    * 次の"字"を１つ読み返すよ
    * (スペースとかは無視されるよ)
    */
    private String readNextStr() {
        String tmp = "";
        while (tmp.isEmpty() && !readerIsEOF) {
            char c = readNext();
            tmp += c;
            tmp = normalizeStr(tmp);
        }
        
        return tmp;
    }
    
    /**
    * ストリームから１"文字"読みます. (スペースとかが返ってくるよ）
    * もしEOFだったらisEOFをtrueにして0を返します...
    */
    private char readNext() {
        
        if (this.readerIsEOF == true) {
            return 0;
        }
        
        int ci = 0;
        try {
            ci = reader.read();
        } catch (IOException ex) {
            ex.printStackTrace();
        }
        
        // EOF
        if (ci == -1) {
            this.readerIsEOF = true;
            
            try {
                reader.close();
            } catch (IOException ex) {
                ex.printStackTrace();
            }
            
            return 0;
        }
        
        return (char) ci;
    }
    
}

これで１字句分がTokenインスタンスとして切り出せます。 EnumのSetに対してストリームAPIを利用し一気にマッチ処理をさせるのがポイントです。

とれたTokenクラスは

/**
 * Token
 * ソースコードから切り出したトークン
 *
 * SorceCode -> Token -> LexcalUnit
 * @author namaz
 *
 */
public class Token {
    
    private TokenType type;
    private String value;
    
    Token(TokenType type, String value) {
        this.type = type;
        this.value = value;
    }
    
    public TokenType getType() {
        return type;
    }
    
    public String getValue() {
        return value;
    }
    
    /**
    * このトークンをタイプに応じて解析し,
    * より詳しく細分化されたLexicalUnitへ変換します.
    */
    public LexicalUnit parseLexicalUnit() {
        
        // それぞれのトークン種別に応じて解析.
        LexicalUnit res = null;
        switch (type) {
        case NUMBER:
            res = parseNumberToken();
            break;
        
        case WORD:
            res = parseWordToken();
            break;
        
        case LITERAL:
            res = parseLiteralToken();
            break;
        
        case SINGLE_OPERATOR:
        case MULTY_OPERATOR:
            res = parseOperatorToken();
            break;
        
        }
        
        return res;
    }
    
    private LexicalUnit parseWordToken() {
        // 予約語の抽出.
        Optional<ReservedWord> reservedWordOpt = EnumSet.allOf(ReservedWord.class)
                .stream()
                .filter(t -> t.isMatch(value))
                .findFirst();
        
        if (reservedWordOpt.isPresent()) {
            // 予約語とマッチした.
            LexicalType type = reservedWordOpt.get().getType();
            return new LexicalUnit(type);
        }
        
        // 予約語とマッチしない　単語　->　変数.
        return new LexicalUnit(LexicalType.NAME, new ValueImpl(value));
    }
    
    private LexicalUnit parseNumberToken() {
        // Double
        if (value.contains(".")) {
            return new LexicalUnit(LexicalType.DOUBLEVAL, new ValueImpl(value));
        }
        
        // Intval
        return new LexicalUnit(LexicalType.INTVAL, new ValueImpl(value));
        
        // TODO: もっと精巧な.とかの処理. 指数部とか　+ - とかの符号もね
        
    }
    
    private LexicalUnit parseLiteralToken() {
        // 　”を消す
        String literalVal = value.replaceAll("\"", "");
        return new LexicalUnit(LexicalType.LITERAL, new ValueImpl(literalVal));
    }
    
    private LexicalUnit parseOperatorToken() {
        // オペレーター種別の識別.
        Optional<Operator> operatorOpt = EnumSet.allOf(Operator.class)
                .stream()
                .filter(t -> t.isMatch(value))
                .findFirst();
        
        if (operatorOpt.isPresent()) {
            // 値に該当するオペレーターが存在した
            LexicalType type = operatorOpt.get().getType();
            return new LexicalUnit(type);
        }
        
        // 該当しないはずがない
        return null;
    }
}

こんな感じで、より詳細に調べてLexicalUnitを作ります。

LexicalAnalyzerImpl

こうしてToken => LexicalUnitとすることで, ボスが渡してくるLexicalAnalyerImplは

public class LexicalAnalyzerImpl implements LexicalAnalyzer {
    
    private TokenParser tokenParser;
    
    public LexicalAnalyzerImpl(String filePath) throws Exception {
        tokenParser = new TokenParser(new FileReader(filePath));
    }
    
    @Override
    public LexicalUnit get() {
        
        Token nextToken = tokenParser.get();
        
        // TokenをLexicalUnitへ
        if (nextToken == null) {
            // nullが返ってきたらEOF
            return new LexicalUnit(LexicalType.EOF);
        }
        return nextToken.parseLexicalUnit();
    }
}

こんな風に書けます。

予約語とか演算子のLexicalTypeとの関連付け判定

文字から予約語や、記号からどの記号のLexicalTypeになるか？とかいう部分については下のように、全ての演算子を網羅したEnumを用意しておき。。。

/**
 * すべての演算子の列挙　及びLexcalTypeとの関連付け
 * 一時決まりの字句とかもここだよ.
 */
public enum Operator {
    EQ(LexicalType.EQ, "="),
    LT(LexicalType.LT, "<"),
    GT(LexicalType.GT, ">"),
    LE(LexicalType.LE, "<=", "=<"),
    GE(LexicalType.GE, ">=", "=>"),
    NE(LexicalType.NE, "<>"),
    ADD(LexicalType.ADD, "+"),
    SUB(LexicalType.SUB, "-"),
    MUL(LexicalType.MUL, "*"),
    DIV(LexicalType.DIV, "/"),
    LP(LexicalType.LP, ")"),
    RP(LexicalType.RP, "("),
    COMMA(LexicalType.COMMA, ","),
    
    NL(LexicalType.NL, "\n"),
    DOT(LexicalType.DOT, ".");
    
    private final String[] vals;
    private final LexicalType type;
    
    private Operator(LexicalType type, String... vals) {
        // 　>= => とかが同じ意味なので配列にしときます.
        this.vals = vals;
        this.type = type;
    }
    
    /**
    * 与えられた文字列と字句の決まり字が一致するかどうか
    */
    public boolean isMatch(String test) {
        for (String string : vals) {
            if (string.equals(test)) {
                return true;
            }
        }
        return false;
    }
    
    public LexicalType getType() {
        return type;
    }
}

この全ての定義を見て、確定させる処理を

// オペレーター種別の識別.
Optional<Operator> operatorOpt = EnumSet.allOf(Operator.class)
    .stream()
    .filter(t -> t.isMatch(”Tokenの文字”))
    .findFirst();
    
if (operatorOpt.isPresent()) {
    // 値に該当するオペレーターが存在した
    LexicalType type = operatorOpt.get().getType();
    return new LexicalUnit(type);
}

こんな感じで一気に行うのが楽しい。　全部Mapに突っ込んで引くという方法もあるけどね。

valueimpl

これを作れーってボスが言いますがまぁ

public class ValueImpl implements Value {
    
    private ValueType type;
    // 全部stringで持っとけ・・・
    private String val;
    
    public ValueImpl(String s) {
        type = ValueType.STRING;
        val = s;
    }
    
    public ValueImpl(int i) {
        type = ValueType.INTEGER;
        val = i + "";
    }
    
    public ValueImpl(double d) {
        type = ValueType.DOUBLE;
        val = d + "";
    }
    
    public ValueImpl(boolean b) {
        type = ValueType.BOOL;
        val = b + "";
    }
    
    @Override
    public String getSValue() {
        return val;
    }
    
    @Override
    public int getIValue() {
        return Integer.parseInt(val);
    }
    
    @Override
    public double getDValue() {
        return Double.parseDouble(val);
    }
    
    @Override
    public boolean getBValue() {
        return Boolean.parseBoolean(val);
    }
    
    @Override
    public ValueType getType() {
        return type;
    }
    
}

こんなんで良いでしょう。　値はString形式で常に持っておくとわざわざ面倒な処理を書かなくてもいい。

字句解析まとめ

字句の正規表現が考えられさえすれば、あとはいろいろな方法でコードにできるでしょう。何も難しいことなし。

一年経った今になって考えると、もっとざばっと単純明快に処理する方法を思いついていて、あーーーってなりながら今日書きました。 LexicalTypeってEnumを渡されるので、そこに手を入れて、すべて正規表現を書き、他の字句と一致した場合の優先度とかも書けば、LexicalTypeを一回見るだけで特定が可能じゃんって。。。　　無駄に２段階挟んだりしてやらなくてもよかった。

明日

明日は、絶賛レポート締め切りが近いらしい、構文解析部分の実装を書いていこうと思います。　一気に構文解析部分を書くのは辛いので、式部分以外を明日は書こうかな。　それでは。

2017-12-25

環境破壊した話と今年のアドベントカレンダー個人まとめ

AdventCalender2017

きょうやったこと

最重要案件をすっぽかす

卒論バトルをボスとしようと思って大学に行ったのです。

大学着いた時点では寝ぼけていて、ボスが「それじゃもういくからねー。」っていうのに「はーい。」って返事してた。ボスに7kくらい立て替えて貰うはずだったのにそれも忘れてた。

お金立て替えてもらうの忘れた。。。。明日も大学行かなあかんくなった
— namazu (@namazu510) 2017年12月25日

結局明日も行かなければならなくなった。　だるいにゃぁ。。。。

環境破壊神の影響を受けた

某所のサービスを復旧させてたらNginxが起動しなかった。　なんかライブラリがぶっ壊れたっぽい。再度プロビジョニングしてやりました。　Ansibleでぜんぶやってるとこういうのに対して、１からやり直すっていう作戦が気負いなく選べていいです。

Nginxは結構すぐ治りました。

そのあと、なんか研究室k8sのワーカーノードGTX460*2SLI構成の古い子が、ICMP応答しないので、見に行きました。

死んでました。　ゴミでした。　古いマシンなので１１階から地面に向けて投げ捨てようかと思いました。　

OS再インストールしようとしたらPXEからインストール出来ないし、インストーラの画面も出てこなくなったので、オタク部屋でアニソン大音量で流してごろごろしてました。

俺も環境破壊神になってしまったかーと最悪な気分でした。

何もかもうまく動かんしカタケンに飛行機つっこんでぜんぶおしゃかになれって気分
— namazu (@namazu510) 2017年12月25日

結局、カーネルのリストを全部試したら上から４番目のカーネルで起動したっぽい（画面は出ないけどSSH接続できる）

グラボは使えなくなったのでcut-terにあげました。　遊ぶらしいです。　ゴミの４６０でも２枚あればそこそこ働けると思います。　環境破壊神に貢ぎ物をしたので、これでもうなんかこわれたにゃぁ。。。ってならないで欲しいです。

さっきkube-06(1080Tiの刺さった新品ちゃん)のICMP応答が帰ってこなくなった事を知りました。死にたいです。　

アドベントカレンダー終日

もう２５日かーという気分です。　Twitterや渋にはコミケのお品書きや表紙イラストがいっぱい流れてますね。さっきTwitterでとってもエロ可愛いにゃんこちゃんの表紙イラストが流れてきて最高になりました。　

今年書いたアドベントカレンダーでも振り返ってみようと思います。

参加したのは以下。　

研究室
同期
大学のなんかやってたやつ

この辺に書きました。

adventar.org

書いた記事は、こんなところです。

namazu-tech.hatenablog.com

最後の方日和った感がありますね。まぁ卒論バトルしてたりいろいろで調子が上手くいってなかったので、仕方ないところあるけれど。。。

来年はもっと強い記事書きたい

社会人になるので１年修行した成果が現れるような記事を書きたいですね。　

どうでもいいはなし

なんか色々ぐうたら動きすぎて成果が生まれていない気がします。　体力がないんすよね。　なんか。　最近物理で動かないと進捗が出ない案件がある程度あり、それの対応に体力がないせいで動くのを躊躇し、結局ぐうたらでgdgdということをしてる。

性格的に、ある程度上手くいかないとフラストレーションが溜まってきて、進捗が生まれにくい行動に走るのでよくない。カタケンと研Aの間を特になにも感じずさらっと移動できるくらいの体力と精神力と肉体が欲しいです。

筋トレとかしたほうがいいんすかね？　しませんけど。

きょうしたこと

Wordpressのドメイン変更

変更SQL

今日したこと

Nginxでサブリクエスト

proxy_passに$argsを含める

$argsを一度適当な変数に代入しておきそれをHTTPヘッダに付与させ送ろう

そもそも$request_uriなら取れるよ！

proxyを２段階にすればいいじゃない

どうでもいいはなし

今日書くこと

実行

構文木インスタンスと実行

実行とEnviroment

実装

AssigneStmt.java

Enviroment.java

関数定義と実行

IFBlockNode.java

さいご

どうでもいいはなし

今日書くこと

式と構文木

式解析の攻略法

実装

さいご

今日書くこと

構文解析とは？

文法

構文解析部分攻略方

実装

実装方針

Node.java

ProgramNode.java

StmtListNode.java

LoopBlockNode.java

さいご

これから書く記事の概要

実践的プログラミング

成果物

連載目次

講義攻略方針

字句解析

字句解析とは

要求される動作

字句解析部分の攻略方

実装

メインエントリポイント

字句を切り出しLexicalUnit作る処理部分

LexicalAnalyzerImpl

予約語とか演算子のLexicalTypeとの関連付け判定

valueimpl

字句解析まとめ

明日

きょうやったこと

最重要案件をすっぽかす

環境破壊神の影響を受けた

アドベントカレンダー終日

どうでもいいはなし