2017年12月17日日曜日

Standard MLで予測型構文解析表を作る

これはML Advent Calendar 2017の17日目の記事です。

TL;DR

Standard MLで予測型構文解析表を生成できるようにした。

コードはGitHubにある。

詳しいことは文献(プログラミング言語 Standard ML入門, 最新コンパイラ構成技法)を読んでほしい。

Standard ML

Standard MLはML(Meta Language)の一つであり,"The Definition of Standard ML" [1]において定義が記述されている。

言語への入門は「プログラミング言語 Standard ML入門」[2]などが詳しい。

処理系にはStandard ML of New Jersey(SML/NJ),MLtonMoscow MLSML#などがある。

どの処理系にも共通してThe Standard ML Basis Libraryというライブラリが実装されており,また処理系固有のライブラリ(例えばSML/NJだとこれ)も存在する。

構文解析

記号と生成文法

記号(symbol)には終端記号(nonterminal symbol)と非終端記号(terminal symbol)がある。

終端記号はこれ以上生成規則により置換されない記号であり,文法のつくる言語のアルファベットとなる。

記号のうち終端記号でないものは非終端記号である。非終端記号は変数とも呼ばれる。

  • $N$; 非終端記号(nonterminal symbol)の有限集合
  • $T$; 終端記号(terminal symbol)の有限集合
  • $\Sigma^*$; $\Sigma$のクリーネ閉包(Kleene closure),すなわち$\Sigma$の要素の(0回以上の)繰り返しがつくる記号列全体を表す
ただし,$N \cap T = \emptyset$である。

生成文法(generative grammar)とは生成規則によって作られる文法である。

生成規則は記号列($(N \cup T)^*$)上の二項関係$\rightarrow \subseteq (N \cup T)^* \times (N \cup T)^*$である。

文脈自由文法(Context Free Grammar, CFG)

文脈自由文法(context free grammar)とは生成文法のうち,生成規則の左辺がただ一つの非終端記号からなる文法をいう。

従って,文脈自由文法の生成規則は非終端記号と記号列の二項関係$\rightarrow \subseteq N \times (N \cup T)^*$である。

文脈自由とは,ある非終端記号に対して,文脈(前後関係)を使わずに生成規則を適用できるという意味である。

  • $P$; 生成規則(production)の有限集合
  • $S$; 開始記号(start symbol) ($S \in N$)
を用いて文法$G$は,四つ組(4-tuple)$G=(N, T, P, S)$として表現できる。

実際に,src/rule.smlでは記号と生成規則を次のように定義した。

datatype Symbol =    TerminalSymbol of string 
                | NonTerminalSymbol of string;

type Rule = Symbol * Symbol list;
導出

文法の生成規則を適用することで,ある終端記号からなる列がある言語に属しているかを判定したい。この判定法には大別して二つの方法がある。

一つは,終端記号列から生成規則を右辺から左辺に向けて繰り返し適用することで,開始記号へ戻ることを確認する再帰的推論(recursive inference)である。

もう一つは,開始記号から生成規則を左辺から右辺に向けて繰り返し適用することで,入力の終端記号の列を得ることができるかを確認する方法である。文法規則をこのように使うことを導出(derivation)という。

導出の過程を記述するために,文脈自由文法$G$に対して,新たな二項関係$\underset{G}{\Rightarrow}$を定義しよう。

文脈自由文法$G=(N, T, P, S)$について,ある生成規則$A \rightarrow \gamma \in P$を考える。

文法$G$において,記号列$\alpha A \beta$から生成規則$A \rightarrow \gamma$を適用して$\alpha \gamma \beta$が導出できることを,二項関係$\alpha A \beta \underset{G}{\Rightarrow} \alpha \gamma \beta$と表すことにする。

(あるいは,$\alpha A \beta \underset{G}{\Rightarrow} \alpha \gamma \beta \overset{\textrm{def}}{\Longleftrightarrow} A \rightarrow \gamma \in P$と定義してもよい。)

さらに,導出を0回以上繰り返し用いて記号列$\alpha$から$\beta$となることを$\alpha \underset{G}{\overset{*}{\Rightarrow}} \beta$と表す。

文脈自由言語

文脈自由文法$G$の生成する言語$L(G)$は開始記号$S$から生成規則を繰り返し用いることで導出される終端記号列全体の集合である。 $$ L(G) = \left\{ w \in T^* \mid ~ S \underset{G}{\overset{*}{\Rightarrow}} w \right\} $$ 文脈自由文法$G$の言語$L(G)$は文脈自由言語(context free language)と呼ばれる。

例示1

文脈自由文法$G_1 = (N, T, P, S)$として次のようなものを考える。

  • $N = \left\{ S \right\}$
  • $T = \left\{ \textrm{a}, \textrm{b} \right\}$
  • $P = \left\{ S \rightarrow \varepsilon, S \rightarrow \textrm{a}S\textrm{b} \right\}$

特に指示がなければ,$\varepsilon$は空列を表す($\left| \varepsilon \right| = 0$)。

val S = NonTerminalSymbol "S";

val non_terminal_symbols = [S];

val a = TerminalSymbol "a";
val b = TerminalSymbol "b";

val terminal_symbols = [a, b];

val rule1 = (S, [a, S, b]);
val rule2 = (S, nil);

val rule_list = [rule1, rule2] : Rule list;

この文法$G_1$の生成する言語$L(G_1)$は$\textrm{a}$を$n$回繰り返した後,同じ回数($n$回)だけ$\textrm{b}$を繰り返す記号列全体の集合$L(G_1) = \left\{ \textrm{a}^n \textrm{b}^n \mid n \geq 0 \right\}$である。

終端記号列$\textrm{aaabbb}$が言語$L(G_1)$に属するかを判定するために,実際に導出過程を記してみる。 $$\begin{align*} S & \underset{G_1}{\Rightarrow} \textrm{a} S \textrm{b} & (S \rightarrow \textrm{a} S \textrm{b}) \\ & \underset{G_1}{\Rightarrow} \textrm{a} \textrm{a} S \textrm{b} \textrm{b} & (S \rightarrow \textrm{a} S \textrm{b}) \\ & \underset{G_1}{\Rightarrow} \textrm{a} \textrm{a} \textrm{a} S\textrm{b} \textrm{b} \textrm{b} & (S \rightarrow \textrm{a} S \textrm{b}) \\ & \underset{G_1}{\Rightarrow} \textrm{a} \textrm{a} \textrm{a} \textrm{b} \textrm{b} \textrm{b} & (S \rightarrow \varepsilon) \end{align*}$$ $S \underset{G_1}{\overset{*}{\Rightarrow}} \textrm{aaabbb}$ゆえ,$\textrm{aaabbb} \in L(G_1)$である。

なお,ある終端記号列$w$が文脈自由文法$G$の生成する言語$L(G)$に含まれるか($w \in L(G)$)を判定する問題をメンバーシップ問題という。この問題はCYK法やEarley法というアルゴリズムで解くことができる。

先程の導出を開始記号を根とする根付き木として表すと下図のようになる。これを導出木(derivation tree)又は構文木(parse tree)という。

例示2 (曖昧な文法)

文脈自由文法$G_2 = (N, T, P, E)$として次のようなものを考える。

  • $N = \left\{ E \right\}$
  • $T = \left\{ -, x, y, z \right\}$
  • $P = \left\{ E \rightarrow E - E, E \rightarrow x, E \rightarrow y, E \rightarrow z \right\}$

val E = NonTerminalSymbol "E";

val non_terminal_symbols = [E];

val minus = TerminalSymbol "-";
val x     = TerminalSymbol "x";
val y     = TerminalSymbol "y";
val z     = TerminalSymbol "z";

val terminal_symbols = [minus, x, y, z];

val rule1 = (E, [E, minus, E]);
val rule2 = (E, [x]);
val rule3 = (E, [y]);
val rule4 = (E, [z]);

val rule_list = [rule1, rule2, rule3, rule4] : Rule list;

開始記号を左辺とする規則が複数あり,開始記号を明確に制限したいときは,新たな非終端記号$S \notin N$を導入して,新たな文法${G_2}' = (N \cup \{ S \}, T, P \cup \{ S \rightarrow E \}, S)$を定義すればよい。この新たな文法${G_2}'$を文法$G_2$の拡大文法(augmented grammar)という。

言語$L(G)$は三つの文字$x$,$y$,$z$をオペランドとする減法($-$)からなる数式を表す記号列全体をなす。

実際,終端記号列$x - y - z$は$L(G_2)$に含まれる。実際$E \overset{*}{\Rightarrow} x - y - z$は,例えば, $$\begin{align*} E & \Rightarrow E - E & (E \rightarrow E - E) \\ & \Rightarrow E - E - E & (E \rightarrow E - E) \\ & \Rightarrow E - y - E & (E \rightarrow y) \\ & \Rightarrow E - y - z & (E \rightarrow z) \\ & \Rightarrow x - y - z & (E \rightarrow x) \end{align*}$$ のように導出できる。文法$G$が明らかな場合は,導出$\underset{G}{\Rightarrow}$を単に$\Rightarrow$で表せる。

ところで,記号列の導出はただ一通りであるとは限らない。

いま,一回の導出$\Rightarrow$によって現れた記号列の最も左にある非終端記号に対して,次の導出を行うことを考えよう。 この方法による導出を先程の終端記号列に対して行うと次のようになる。 $$\begin{align*} E & \Rightarrow E - E & (E \rightarrow E - E) \\ & \Rightarrow x - E & (E \rightarrow x) \\ & \Rightarrow x - E - E & (E \rightarrow E - E) \\ & \Rightarrow x - y - E & (E \rightarrow y) \\ & \Rightarrow x - y - z & (E \rightarrow z) \end{align*}$$ このような導出の方法を最左導出(leftmost derivation)といい,$\overset{*}{\underset{lm}{\Rightarrow}}$と表す。

対して,一回の導出$\Rightarrow$によって現れた記号列の最も右にある非終端記号に対して,次の導出を行うことを考える。 この方法による導出を先程の終端記号列に対して行うと次のようになる。 $$\begin{align*} E & \Rightarrow E - E & (E \rightarrow E - E) \\ & \Rightarrow E - z & (E \rightarrow z) \\ & \Rightarrow E - E - z & (E \rightarrow E - E) \\ & \Rightarrow E - y - z & (E \rightarrow y) \\ & \Rightarrow x - y - z & (E \rightarrow x) \end{align*}$$ このような導出の方法を最右導出(rightmost derivation)といい,$\overset{*}{\underset{rm}{\Rightarrow}}$と表す。

例示2ではじめに上げた導出は最左導出でも最右導出でもない。

一般に導出$S \underset{G}{\overset{*}{\Rightarrow}}\gamma$が存在すれば,それと同等の結果をもたらす最左導出$S \overset{*}{\underset{G,lm}{\Rightarrow}} \gamma$と最右導出$S \overset{*}{\underset{G,rm}{\Rightarrow}} \gamma$がそれぞれ存在する。

上の最左導出と最右導出それぞれに対する導出木は下図のようになる。

このように,文法$G$について少なくとも一つ記号列$w \in L(G)$に対する導出木が2つ以上あるとき,この文法は曖昧(ambiguous)であるという。逆に,任意の記号列$w \in L(G)$について導出木がただ一つに定まるならば,この文法は曖昧でない(unambiguous)という。

従って例示2の文法$G_2$は曖昧である。例示1の文法$G_1$は曖昧ではない。

(注意) 次のような導出を考える。 $$\begin{align*} E & \Rightarrow E - E & (E \rightarrow E - E) \\ & \Rightarrow E - E - E & (E \rightarrow E - E) \\ & \Rightarrow x - E - E & (E \rightarrow x) \\ & \Rightarrow x - y - E & (E \rightarrow y) \\ & \Rightarrow x - y - z & (E \rightarrow z) \end{align*}$$ この導出において,$\class{math-yellow}{E} - E \Rightarrow \class{math-yellow}{E - E} - E$は左辺における左側の$E$に対して生成規則の適用が行われたとする。 すると,この導出は定義より明らかに最左導出である。(紛らわしいが,この導出の導出木は上図で最右導出とした(b)と一致する。)

このように曖昧な文法に対しては最左導出や最右導出が複数存在しえる。 なお,同様に上述の最右導出とは異なった最右導出をつくることができる。 逆に,曖昧でない文法では最左導出も最右導出もそれぞれただ一つに定まる。

例示3 (曖昧でない文法)

文脈自由文法$G_3 = (N, T, P, E)$として次のようなものを考える。

  • $N = \left\{ E, I \right\}$
  • $T = \left\{ -, x, y, z \right\}$
  • $P = \left\{ E \rightarrow E - I, E \rightarrow I, I \rightarrow x, I \rightarrow y, I \rightarrow z \right\}$

val E = NonTerminalSymbol "E";
val I = NonTerminalSymbol "I";

val non_terminal_symbols = [E, I];

val minus = TerminalSymbol "-";
val x     = TerminalSymbol "x";
val y     = TerminalSymbol "y";
val z     = TerminalSymbol "z";

val terminal_symbols = [minus, x, y, z];

val rule1 = (E, [E, minus, I]);
val rule2 = (E, [I]);
val rule3 = (I, [x]);
val rule4 = (I, [y]);
val rule5 = (I, [z]);

val rule_list = [rule1, rule2, rule3, rule4, rule5] : Rule list;

先程の例示2と同様に,$x - y - z \in L(G_3)$である。

この終端記号列に対する最左導出は $$\begin{align*} E & \Rightarrow E - I & (E \rightarrow E - I) \\ & \Rightarrow E - I - I & (E \rightarrow E - I) \\ & \Rightarrow I - I - I & (E \rightarrow I) \\ & \overset{*}{\Rightarrow} x - y - z & (I \rightarrow x, I \rightarrow y, I \rightarrow z) \end{align*}$$ であり,最右導出は $$\begin{align*} E & \Rightarrow E - I & (E \rightarrow E - I) \\ & \Rightarrow E - z & (I \rightarrow z) \\ & \Rightarrow E - I - z & (E \rightarrow E - I) \\ & \Rightarrow E - y - z & (I \rightarrow y) \\ & \overset{*}{\Rightarrow} x - y - z & (E \rightarrow I, I \rightarrow x) \end{align*}$$ となる。 これらの導出は共に右図のような導出木で表される。


この文法$G_3$は曖昧ではない。すなわち,任意の終端記号列$w \in L(G_3)$に対して導出木が一意に定まる。

(従って,先程の終端記号列$x - y- z$に対する最左導出,最右導出はそれぞれ先程挙げた導出一つのみである。)

実際に,算術式としてこれらの記号列を捉えると,減算($-$)が左に結合しており,計算結果も期待通りのものになる。 もし,生成規則$E \rightarrow E - I$を$E \rightarrow I - E$と取り替えると,減算は右結合となり,計算結果も直感とは反することになる。

文脈自由文法上の計算

この後,曖昧でない文脈自由文法よりさらに狭い文法を対象として構文解析(下降型構文解析)を行うための手法について述べる。 そのための準備として,$\textrm{nullable}$(空可能性),$\textrm{FIRST}$,$\textrm{FOLLOW}$という3つの文法上の関数(実装上はテーブル)を定義し,それらを構成するアルゴリズムを与える。

$\textrm{nullable}[X]$は記号$X$が空列を導出できるか否かを表す。

そして,$\textrm{nullable}(\gamma)$は記号列$\gamma$が空列を導出できるか否かを表す。

今,各記号$X \in (N \cup T)$に対して$\textrm{nullable}[X]$が計算されているとき, $$ \textrm{nullable}(\gamma) = \left\{ \begin{array}{ll} \textrm{true} & (\gamma = \varepsilon) \\ \textrm{nullable}[Y_1] \wedge \textrm{nullable}[Y_2] \wedge \cdots \wedge \textrm{nullable}[Y_k] & (\gamma = Y_1 Y_2 \cdots Y_k) \end{array} \right. $$ と計算できる。

$\textrm{nullable}$の求め方 (src/nullable.sml)

  1. はじめに各記号$X \in (N \cup T)$に対して$\textrm{nullable}[X] \leftarrow \textrm{false}$と初期化する。
    fun initialize_nullable symbols = 
      List.foldl 
        (fn (symbol, nullable) => Nullable.insert (nullable, symbol, false)) 
        Nullable.empty symbols;
    
  2. 各生成規則$X \rightarrow \gamma$毎に,
    • $\gamma = \varepsilon$ならば,$\textrm{nullable}[X] \leftarrow \textrm{true}$とする。
    • $\gamma = Y_1 Y_2 \cdots Y_k$ならば,$\textrm{nullable}[X] \leftarrow \textrm{nullable}[X] \vee\left( \textrm{nullable}[Y_1] \wedge \textrm{nullable}[Y_2] \wedge \cdots \wedge \textrm{nullable}[Y_k] \right)$とする。
    fun do_refresh_nullable nullable ((x, nil) : Rule) = Nullable.insert (nullable, x, true)
      | do_refresh_nullable nullable ((x,  ys) : Rule) = let
        val f = List.all (fn x => x) (List.map (fn y => Nullable.find (nullable, y)) ys);
        val g = Nullable.find (nullable, x);
      in Nullable.insert (nullable, x, (f orelse g)) end;
    
  3. 2.の操作を$\textrm{nullable}$が変化しなくなるまで繰り返し行う。
    fun refresh_nullable nullable rule_list = let
      val new_nullable = List.foldl (fn (rule, hash) => do_refresh_nullable hash rule) nullable rule_list;
    in 
      if Nullable.equal (op =) (nullable, new_nullable)
        then new_nullable
        else refresh_nullable new_nullable rule_list
    end;
    

$\textrm{FIRST}[X]$は,記号$X$から導出される終端記号列$w$の最初の記号となれる終端記号の集合である。

そして,$\textrm{FIRST}(\gamma)$は記号列$\gamma$から導出される終端記号列$w$の最初の記号となれる終端記号の集合である。

今,各記号$X \in (N \cup T)$に対して$\textrm{FIRST}[X]$が計算されているとき, $$ \textrm{FIRST}(Y \gamma) = \left\{ \begin{array}{ll} \textrm{FIRST}[Y] & (\textrm{nullable}[Y] = \textrm{true}) \\ \textrm{FIRST}[Y] \cup \textrm{FIRST}(\gamma) & (\textrm{nullable}[Y] = \textrm{false}) \end{array} \right. $$ と計算できる。

$\textrm{FIRST}$の求め方 (src/first.sml)

  1. はじめに,各記号$X \in (N \cup T)$毎に,
    • $X \in N$ならば,$\textrm{FIRST}[X] \leftarrow \emptyset$
    • $X \in T$ならば,$\textrm{FIRST}[X] \leftarrow \{ X \}$
    と初期化する。
    fun initialize_first symbols = 
      List.foldl
        (
          fn (symbol, first) => 
            First.insert 
            (
              first, 
              symbol,
              (
                case (symbol)
                  of (   TerminalSymbol s) => SymbolSet.add (SymbolSet.empty, symbol)
                   | (NonTerminalSymbol s) => SymbolSet.empty
              )
            )
        )
        First.empty
        symbols;
    
  2. 各生成規則$X \rightarrow Y_1 Y_2 \cdots Y_k$毎に,
    • $k = 0$(つまり,$X \rightarrow \varepsilon$)のとき,何もしない。($\textrm{FIRST}[X] \leftarrow \textrm{FIRST}[X]$)
    • $k \geq 1$のとき,

      各$i \in [1, k]$に対して$\textrm{nullable}(Y_1 Y_2 \cdots Y_{i - 1})$が真ならば $$\textrm{FIRST}[X] \leftarrow \textrm{FIRST}[X] \cup \textrm{FIRST}[Y_i]$$

      これはすなわち,$Y_1$から始まる$\textrm{nullable}[Y_i] = \textrm{true} ~ (1 \leq i < j)$を満足する最長部分列$Y_1 Y_2 \cdots Y_{j - 1}$に対して $$\textrm{FIRST}[X] \leftarrow \textrm{FIRST}[X] \cup \left( \textrm{FIRST}[Y_1] \cup \textrm{FIRST}[Y_2] \cup \cdots \cup \textrm{FIRST}[Y_j] \right)$$ とすることと同じである。(ただし,$j - 1 = k$のときは,$\textrm{FIRST}[Y_j] = \emptyset$と約束する。)

      この計算は,生成規則$X \rightarrow Y_1 Y_2 \cdots Y_k$の初めの$i -1$個から成る列$Y_1 \cdots Y_{i-1}$が空列を導出する可能性があるならば,非終端記号$X$の最初に現れるような終端記号の集合$\textrm{FIRST}[X]$には記号$Y_i$の最初に現れるような終端記号の集合$\textrm{FIRST}[Y_i]$を部分集合にもつことを表している。

    fun do_refresh_first first nullable ((x, ys) : Rule) = let
      val first_x_set = First.find (first, x);
      
      fun subList pred nil = nil
        | subList pred (y::ys) = if (pred y) then y::(subList pred ys) else [y];
    
      val zs = subList (fn y => Nullable.find (nullable, y)) ys;
       
      val first_x_set = List.foldl 
        (
          fn (symbol, set) => 
            SymbolSet.union(set, First.find(first, symbol))
        )
        first_x_set zs;
    in First.insert (first, x, first_x_set) end
    
  3. 2.の操作を$\textrm{FIRST}$が変化しなくなるまで繰り返し行う。
    fun refresh_first first nullable rule_list = let
      val new_first = List.foldl 
        (
          fn (rule, hash) => 
            do_refresh_first hash nullable rule
        )
        first rule_list;
    in
      if First.equal SymbolSet.equal (first, new_first)
        then new_first
        else refresh_first new_first nullable rule_list
    end;
    

$\textrm{FOLLOW}[X]$は記号$X$の直後に来ることのできる終端記号の集合である。

$\textrm{FOLLOW}$の求め方(src/follow.sml)

  1. はじめに各記号$X$毎に,$\textrm{FOLLOW}[X] \leftarrow \emptyset$と初期化する。
    fun initialize_follow symbols = 
      List.foldl
        (fn (symbol, hash) => Follow.insert (hash, symbol, SymbolSet.empty))
        Follow.empty
        symbols;
    
  2. 各生成規則$X \rightarrow Y_1 Y_2 \cdots Y_k$毎に,
    1. 各$i \in [1, k]$に対して,$\textrm{nullable}(Y_{i+1} Y_{i+2} \cdots Y_k) = \textrm{true}$であるならば, $$ \textrm{FOLLOW}[Y_i] \leftarrow \textrm{FOLLOW}[Y_i] \cup \textrm{FOLLOW}[X] $$

      これはすなわち,$Y_k$で終わる$\textrm{nullable}[Y_j] = \textrm{true} ~ (i < j \leq k)$を満足する最長部分列$Y_{i + 1} Y_{i + 2} \cdots Y_k$に対して $$ \textrm{FOLLOW}[Y_i] \leftarrow \left( \textrm{FOLLOW}[Y_i] \cup \textrm{FOLLOW}[Y_{i + 1}] \cup \cdots \cup \textrm{FOLLOW}[Y_k] \right) \cup \textrm{FOLLOW}[X] $$ とすることと同じである。(関数refresh_follow_1に相当する。)

      この計算は,生成規則$X \rightarrow Y_1 Y_2 \cdots Y_k$の最後の$k - i$個からなる列$Y_{i + 1} \cdots Y_k$が空列を導出する可能性があるならば, $Y_i$の直後に来ることのできる終端記号の集合$\textrm{FOLLOW}[Y_i]$は生成規則の左辺である非終端記号$X$の直後に来ることのできる終端記号の集合$\textrm{FOLLOW}[X]$を部分集合としてもつことを表している。

      例えば生成規則$W \rightarrow \alpha X \beta$があり,この導出の過程で先程の生成規則$X \rightarrow Y_1 Y_2 \cdots Y_i Y_{i+1} \cdots Y_k$を用いることを考えれば,$Y_i$の直後に来れる終端記号の集合$\textrm{FOLLOW}[Y_i]$は$X$の直後に来れる終端記号の集合$\textrm{FOLLOW}[X]$を部分集合として含む(そして,これはおそらく次のiiの計算から$\textrm{FIRST}(\beta)$となるだろう)ことが直感的に読み取れるだろう。

    2. 各$i \in [1, k]$,$j \in [i + 1, k]$に対して,$\textrm{nullable}(Y_{i+1} Y_{i+2} \cdots Y_{j - 1}) = \textrm{true}$であるならば, $$ \textrm{FOLLOW}[Y_i] \leftarrow \textrm{FOLLOW}[Y_i] \cup \textrm{FIRST}[Y_j] $$ (関数refresh_follow_2に相当する。)

      この計算は,生成規則$X \rightarrow Y_1 Y_2 \cdots Y_k$の右辺の記号列の部分列$Y_{i+1} \cdots Y_{j - 1}$が空列を導出する可能性があるならば,$Y_i$の直後に来ることのできる終端記号の集合$\textrm{FOLLOW}[Y_i]$は,$Y_j$の最初に現れる記号の集合$\textrm{FIRST}[Y_j]$を部分集合として含むことを表している。

    fun do_refresh_follow follow first nullable ((x, ys) : Rule) = let
      fun isNullableList ys = let
          val zs = List.map (fn y => Nullable.find (nullable, y)) ys;
      in List.all (fn x => x) zs end
      and refresh_follow_1 follow ((x, ys) : Rule) = let
        fun subList v = let
          val f = fn v => List.tabulate (List.length v, (fn x => x));
          val u = List.map (fn n => List.drop (v, n)) (f v);
          val u = List.map (fn t => (hd t, tl t)) u;
        in u end;
        
        val zs = List.filter (fn (y, ys) => isNullableList ys) (subList ys);
        
        val follow = List.foldl
          (
            fn ((y, ys), follow) => 
              Follow.insert
                (
                  follow,
                  y,
                  (
                    SymbolSet.union
                    (
                      Follow.find (follow, y), 
                      Follow.find (follow, x)
                    )
                  )
                )
          )
          follow zs;
      in follow end
      and refresh_follow_2 follow ((x, ys) : Rule) = let
        fun subList v = let
          val f0 = fn v => List.tabulate (List.length v, (fn x => x + 0));
          val f1 = fn v => List.tabulate (List.length v, (fn x => x + 1));
          
          fun g (x::xs) = let
            val ys = List.rev xs;
            val y = List.hd ys;
            val ys = List.rev (List.tl ys);
          in (x, ys, y) end;
          
          val u = List.map (fn n => List.take (v, n)) (f1 v);
          val u = List.map (fn v => List.map (fn n => List.drop (v, n)) (f0 v)) u;
          val u = List.foldl List.@ nil u;
          val u = List.filter (fn v => List.length v > 1) u;
          val u = List.map (fn v => g v) u;
        in u end;
        
        val zs = List.filter (fn (x1, ys, x2) => isNullableList ys) (subList ys);
        
        val follow = List.foldl 
          (
            fn ((x1, ys, x2), follow) => 
              Follow.insert
                (
                  follow,
                  x1,
                  (
                    SymbolSet.union
                    (
                      Follow.find (follow, x1),
                      Follow.find (first,  x2)
                    )
                  )
                )
          )
          follow
          zs;
      in follow end;
      
      val follow = refresh_follow_1 follow ((x, ys) : Rule);
      val follow = refresh_follow_2 follow ((x, ys) : Rule);
    in follow end;
    
  3. 2.の操作を$\textrm{FOLLOW}$が変化しなくなるまで繰り返し行う。
    fun refresh_follow follow first nullable rule_list = let
      val new_follow = List.foldl 
        (
          fn (rule, hash) => 
            do_refresh_follow hash first nullable rule
        )
        follow rule_list;
    in
      if Follow.equal SymbolSet.equal (follow, new_follow)
        then new_follow
        else refresh_follow new_follow first nullable rule_list
    end;
    
再帰降下型構文解析

下降型構文解析(top-down parsing)とは開始記号に対して導出を行うことで,入力として与えられた終端記号列を得ることができるかを調べる方法である。 下降型構文解析の代表的な方法としてLL法がある。

逆に,入力した終端記号列に生成規則を右辺から左辺に向かって適用することで,開始記号を得ることができるかを調べる方法は上昇型構文解析(bottom-up parsing)という。 上昇型構文解析の代表的な方法としてLR法がある。

LL文法もLR文法も曖昧でない文脈自由文法の真なサブクラスである。

再帰降下型構文解析(recursive descent parsing)は下降型構文解析を再帰的な方法(通常は相互再帰的に定義された関数乃至手続き)によって実現する方法である。 この方法では,ある非終端記号を導出する際に,どの生成規則を適用するかを選ぶ必要がある。

生成規則の選び方にはいくつかの手法が存在する。

一つはバックトラックを用いる方法である。 この方法では,可能性のある生成規則を試行し,成功した生成規則を採用する。

もう一つは,トークンを先読みすることで,生成規則が一意に定まる文法を用いる方法である。 このとき,未消費な入力の終端記号列の初め$k$個を読めば,使うべき生成規則が一意に定まるような文法を$\textrm{LL}(k)$文法という。 いくつかのトークンを先読みすれば使うべき生成規則が一意に定まるという意味で,このような構文解析は予測的(predictive)であるという。

予測型構文解析表

曖昧でない文脈自由文法$G = (N, T, P, S)$を考える。 このとき,ある非終端記号$X \in N$と,先読みできる$k$個の終端記号からなる列$t \in T^k$の組$(X, t)$を定めれば生成規則の部分集合$\left\{ X \rightarrow \gamma, \cdots \right\} \subseteq P$を求めることができる。 これを非終端記号$X$を行,終端記号列$t$を列とした表として記述したものを予測型構文解析表(predictive parsing table)という。

ここでは,$\textrm{LL}(1)$文法を念頭に,$|t| = 1$であるような予測型構文解析表を作る。 (もし,$k > 1$なLL文法を解析する場合は,先程の$\textrm{FIRST}$,$\textrm{FOLLOW}$を更に拡張させる必要がある。)

予測型構文解析表を作るために次のようにすればよい。(src/parsing_table.sml)

全ての生成規則$X \rightarrow \gamma \in P$について以下の操作を行う。

  • 生成規則$X \rightarrow \gamma$を$X$行の$t \in \textrm{FIRST}(\gamma)$であるような$t$列に加える。(関数process1に相当する。)
  • もし$\textrm{nullable}(\gamma) = \textrm{true}$ならば,$X$行の$t \in \textrm{FOLLOW}[X]$を満たす$t$列に加える。(関数process2に相当する。)
fun do_build_parsing_table nullable first follow parsing_table rule_list symbol = let
  val rules = List.filter (fn (x, ys) => x = symbol) rule_list;
  
  fun parsing_table_insert parsing_table key value = let
    val old_set = ParsingTable.find (parsing_table, key);
    val new_set = RuleSet.add (old_set, value);
  in ParsingTable.insert (parsing_table, key, new_set) end;
  
  fun process1 parsing_table rules = let
    fun get_first_symbols ys = let
      val zs = List.map (fn y => (First.find (first, y), Nullable.find (nullable, y))) ys;
      
      fun do_get_first_symbols               nil = SymbolSet.empty
        | do_get_first_symbols ((set, flag)::vs) = 
          if flag 
            then SymbolSet.union (set, (do_get_first_symbols vs)) 
            else set;
    in do_get_first_symbols zs end;
    
    val zs = List.map (fn (x, ys) => ((x, ys), get_first_symbols ys)) rules;
    
    fun q (x, ys) symbols parsing_table = 
      List.foldl
        (fn (symbol, parsing_table) => parsing_table_insert parsing_table (x, symbol) (x, ys))
        parsing_table
        (SymbolSet.listItems symbols);
    
    val parsing_table = 
      List.foldl 
        (fn ((rule, symbols), parsing_table) => q rule symbols parsing_table) 
        parsing_table
        zs;
  in parsing_table end;
  
  fun process2 parsing_table rules = let
    fun isNullableList ys = Nullable.find (nullable, (hd ys)) handle Empty => true;
    
    val nullable_rules = List.filter (fn (x, ys) => isNullableList ys) rules;
    
    fun q (x, ys) parsing_table = let
      val follow_x = Follow.find (follow, x);
      val parsing_table = 
        List.foldl 
          (fn (symbol, parsing_table) => parsing_table_insert parsing_table (x, symbol) (x, ys))
          parsing_table
          (SymbolSet.listItems follow_x);
    in parsing_table end;
    
    val parsing_table = 
      List.foldl 
        (fn ((x, ys), parsing_table) => q (x, ys) parsing_table) 
        parsing_table
        nullable_rules;
  in parsing_table end;
  
  val parsing_table = process1 parsing_table rules;
  val parsing_table = process2 parsing_table rules;
in parsing_table end;

fun build_parsing_table non_terminal_symbols terminal_symbols rule_list nullable first follow = 
  List.foldl 
    (
      fn (symbol, parsing_table) => 
        do_build_parsing_table 
          nullable first follow 
          parsing_table rule_list symbol
    ) 
    (initialize_parsing_table non_terminal_symbols terminal_symbols) 
    non_terminal_symbols;

もし,与えられた文法が$\textrm{LL}(1)$文法ならば,この表の各セルにある生成規則は高々一つである。 逆に,この表が複数の生成規則を含むセルを持つならば,与えられた文法は$\textrm{LL}(1)$文法でない。

例示4 (LL(1)文法ではない文法)

例示3で挙げた,文脈自由文法$G_3 = (N, T, P, E)$を考える。

  • $N = \left\{ E, I \right\}$
  • $T = \left\{ -, x, y, z \right\}$
  • $P = \left\{ E \rightarrow E - I, E \rightarrow I, I \rightarrow x, I \rightarrow y, I \rightarrow z \right\}$

更に,記号列の終端を表す特別な終端記号$\$$を加えた文法$G_4 = (N, T, P, E)$を考える。

  • $N = \left\{ E, I \right\}$
  • $T = \left\{ -, x, y, z, \$ \right\}$
  • $P = \left\{ E \rightarrow E - I \$, E \rightarrow I \$, I \rightarrow x, I \rightarrow y, I \rightarrow z \right\}$

val E = NonTerminalSymbol "E";
val I = NonTerminalSymbol "I";

val non_terminal_symbols = [E, I];

val minus  = TerminalSymbol "-";
val x      = TerminalSymbol "x";
val y      = TerminalSymbol "y";
val z      = TerminalSymbol "z";
val dollar = TerminalSymbol "$";

val terminal_symbols = [minus, x, y, z, dollar];

val rule1 = (E, [E, minus, I, dollar]);
val rule2 = (E, [I, dollar]);
val rule3 = (I, [x]);
val rule4 = (I, [y]);
val rule5 = (I, [z]);

val rule_list = [rule1, rule2, rule3, rule4, rule5] : Rule list;

$\textrm{nullable}$,$\textrm{FIRST}$,$\textrm{FOLLOW}$をそれぞれ計算し,予測型構文解析表を作ると次のようになる。

nullable = [E: false, I: false]
FIRST    = [E: [x, y, z], I: [x, y, z]]
FOLLOW   = [E: [-], I: [$]]
\
-
x
y
z
$
E
E -> E - I $
E -> I $
E -> E - I $
E -> I $
E -> E - I $
E -> I $
I
I -> x
I -> y
I -> z

この構文解析表は重複を含むセルが存在する。 従って,この文法$G_4$は$\textrm{LL}(1)$文法ではない。 (すなわち,$k = 1$個のトークンを先読みするだけでは,使うべき生成規則が一意に定まらない。)

例示5 (LL(1)文法)

文脈自由文法$G_5 = (N, T, P, E)$として次のようなものを考える。

  • $N = \left\{ E, E', I \right\}$
  • $T = \left\{ -, x, y, z, \$ \right\}$
  • $P = \left\{ E \rightarrow I E' \$, E' \rightarrow - I E', E' \rightarrow \varepsilon, I \rightarrow x, I \rightarrow y, I \rightarrow z \right\}$

val E  = NonTerminalSymbol "E";
val Ed = NonTerminalSymbol "E'";
val I  = NonTerminalSymbol "I";

val non_terminal_symbols = [E, Ed, I];

val minus  = TerminalSymbol "-";
val x      = TerminalSymbol "x";
val y      = TerminalSymbol "y";
val z      = TerminalSymbol "z";
val dollar = TerminalSymbol "$";

val terminal_symbols = [minus, x, y, z, dollar];

val rule1 = (E, [I, Ed, dollar]);
val rule2 = (Ed, [minus, I, Ed]);
val rule3 = (Ed, nil);
val rule4 = (I, [x]);
val rule5 = (I, [y]);
val rule6 = (I, [z]);

val rule_list = [rule1, rule2, rule3, rule4, rule5, rule6] : Rule list;

$\textrm{nullable}$,$\textrm{FIRST}$,$\textrm{FOLLOW}$をそれぞれ計算し,予測型構文解析表を作ると次のようになる。

nullable = [E: false, E': true, I: false]
FIRST    = [E: [x, y, z], E': [-], I: [x, y, z]]
FOLLOW   = [E: [], E': [$], I: [$, -]]
\
-
x
y
z
$
E
E -> I E' $
E -> I E' $
E -> I E' $
E'
E' -> - I E'
E' -> 
I
I -> x
I -> y
I -> z

従って,この文法$G_5$は$\textrm{LL}(1)$文法である。

この文法$G_5$を解析するための$\textrm{LL}(1)$パーサは,例えば次のように書ける。

exception ParseError;

fun parse tokens = let
  val stack = ["E"];
  val (tokens, stack) = parseE tokens stack;
in tokens = nil andalso stack = nil end
and parseE tokens stack = let
  val () = if (hd stack) = "E" then () else raise ParseError;
in
  case (hd tokens)
  of "x" => let 
      val stack = "I"::"E'"::(tl stack);
      val (tokens, stack) = parseI  tokens stack;
      val (tokens, stack) = parseEd tokens stack;
    in (tokens, stack) end
   | "y" => let 
      val stack = "I"::"E'"::(tl stack);
      val (tokens, stack) = parseI  tokens stack;
      val (tokens, stack) = parseEd tokens stack;
    in (tokens, stack) end
   | "z" => let 
      val stack = "I"::"E'"::(tl stack);
      val (tokens, stack) = parseI  tokens stack;
      val (tokens, stack) = parseEd tokens stack;
    in (tokens, stack) end
   | _   => raise ParseError
end
and parseEd tokens stack = let
  val () = if (hd stack) = "E'" then () else raise ParseError;
in
  (
    case (hd tokens)
    of "-" => let
        val stack = "I"::"E'"::(tl stack);
        val tokens = eatToken "-" tokens;
        val (tokens, stack) = parseI  tokens stack;
        val (tokens, stack) = parseEd tokens stack;
      in (tokens, stack) end
     | _   => raise ParseError
  )
  handle Empty => (tokens, (tl stack))
end
and parseI  tokens stack = let
  val () = if (hd stack) = "I" then () else raise ParseError;
in
  case (hd tokens)
  of "x" => let 
      val tokens = eatToken "x" tokens;
      val stack = tl stack;
    in (tokens, stack) end
   | "y" => let 
      val tokens = eatToken "y" tokens;
      val stack = tl stack;
    in (tokens, stack) end
   | "z" => let 
      val tokens = eatToken "z" tokens;
      val stack = tl stack;
    in (tokens, stack) end
   | _   => raise ParseError
end
and eatToken expect tokens = if (hd tokens) = expect then tl tokens else raise ParseError;

val f1 = parse ["x"];
(* val f1 = true : bool *)

val f2 = parse ["x", "-", "y"];
(* val f2 = true : bool *)

val f3 = parse ["x", "-", "y", "-", "z"];
(* val f3 = true : bool *)

val g = parse ["x", "-"];
(* val g = false : bool *)

ただし,この文法の通りに構文木をつくると減算($-$)が右結合となり,計算結果は直感と反することになる。

例示6

文脈自由文法$G_6 = (N, T, P, S)$として次のようなものを考える。

  • $N = \left\{ S, E, E', T, T' F \right\}$
  • $T = \left\{ (, ), \textrm{num}, \$ \right\}$
  • $P = \left\{ \begin{array}{lll} S \rightarrow E \$, & & \\ E \rightarrow T E', & & \\ E' \rightarrow + T E', & E' \rightarrow - T E', & E' \rightarrow \varepsilon, \\ T \rightarrow F T', & & \\ T' \rightarrow * F T', & T' \rightarrow / F T', & T' \rightarrow \varepsilon, \\ F \rightarrow ( E ), & F \rightarrow \textrm{num} & \end{array} \right\}$

val S  = NonTerminalSymbol "S";
val E  = NonTerminalSymbol "E";
val Ed = NonTerminalSymbol "E'";
val T  = NonTerminalSymbol "T";
val Td = NonTerminalSymbol "T'";
val F  = NonTerminalSymbol "F";

val non_terminal_symbols = [S, E, Ed, T, Td, F];

val plus   = TerminalSymbol "+";
val minus  = TerminalSymbol "-";
val star   = TerminalSymbol "*";
val slash  = TerminalSymbol "/";
val lparen = TerminalSymbol "(";
val rparen = TerminalSymbol ")";
val num    = TerminalSymbol "num";
val dollar = TerminalSymbol "$";

val terminal_symbols = [plus, minus, star, slash, lparen, rparen, num, dollar];

val rule1  = (S,  [E, dollar]);
val rule2  = (E,  [T, Ed]);
val rule3  = (Ed, [plus,  T, Ed]);
val rule4  = (Ed, [minus, T, Ed]);
val rule5  = (Ed, []);
val rule6  = (T,  [F, Td]);
val rule7  = (Td, [star,  F, Td]);
val rule8  = (Td, [slash, F, Td]);
val rule9  = (Td, []);
val rule10 = (F,  [lparen, E, rparen]);
val rule11 = (F,  [num]);

val rule_list = [rule1, rule2, rule3, rule4, rule5, rule6, rule7, rule8, rule9, rule10, rule11] : Rule list;

この文法$G_6$は$\textrm{num}$に対する括弧を含む四則演算を実現する。

$\textrm{nullable}$,$\textrm{FIRST}$,$\textrm{FOLLOW}$をそれぞれ計算し,予測型構文解析表を作ると次のようになる。

nullable = [S: false, E: false, E': true, T: false, T': true, F: false]
FIRST    = [S: [(, num], E: [(, num], E': [+, -], T: [(, num], T': [*, /], F: [(, num]]
FOLLOW   = [S: [], E: [$, )], E': [$, )], T: [$, ), +, -], T': [$, ), +, -], F: [$, ), *, +, -, /]]
\
+
-
*
/
(
)
num
$
S
S -> E $
S -> E $
E
E -> T E'
E -> T E'
E'
E' -> + T E'
E' -> - T E'
E' -> 
E' -> 
T
T -> F T'
T -> F T'
T'
T' -> 
T' -> 
T' -> * F T'
T' -> / F T'
T' -> 
T' -> 
F
F -> ( E )
F -> num

従って,この文法$G_6$は$\textrm{LL}(1)$文法である。

結論

文脈自由文法の定義から,$\textrm{nullable}$,$\textrm{FRIST}$,$\textrm{FOLLOW}$を計算する手法を紹介し,$\textrm{LL}(1)$文法の予測型構文解析表を構築する方法について述べた。

参考文献

  1. Robin Milner, Mads Tofte, Robert Harper and David MacQueen. "The Definition of Standard ML (Revised)", The MIT Press, 1997.
    http://sml-family.org/sml97-defn.pdf
  2. 大堀淳. "プログラミング言語 Standard ML入門", 共立出版社, 2001.
    https://www.amazon.co.jp/dp/4320120248
  3. John E. Hopcroft,‎ Jeffrey D. Ullman and‎ Rajeev Motwani. "オートマトン 言語理論 計算論 Ⅰ", サイエンス社, 2003.
    https://www.amazon.co.jp/dp/4781910262
  4. Andrew W. Appel. "最新コンパイラ構成技法", 翔泳社, 2009.
    https://www.amazon.co.jp/dp/4798114685

2017年12月8日金曜日

ガゲァスAdvent Calender 8日目

ガゲマックシャッフラーをセキュアにする

前回の投稿で「APIキーをヘッダに入れて叩きたいが,IFTTT側が未対応でできなかった。」という旨の投稿をした。

今回はカスタムオーソライザーを使ってAPIに認証機構をつける。

認証機構となるLambda関数を作る

認証機構となるLambda関数を作る。

コードは以下のような感じ。

# アクセストークンを適当に生成して貼り付ける
correct_access_token = '***'

def generate_policy(principalId, effect, resource):
    authResponse = {}
    authResponse['principalId'] = principalId
    
    policyDocument = {};
    policyDocument['Version'] = '2012-10-17'
    policyDocument['Statement'] = []
    
    statementOne = {}
    statementOne['Action'] = 'execute-api:Invoke'
    statementOne['Effect'] = effect
    statementOne['Resource'] = resource
    
    policyDocument['Statement'] = [statementOne]
    
    authResponse['policyDocument'] = policyDocument
    
    return authResponse

def lambda_handler(event, context):
    # TODO implement
    access_token = event['queryStringParameters']['access_token']
    if access_token == correct_access_token:
        authResponse = generate_policy('user', 'Allow', event['methodArn'])
    else:
        authResponse = generate_policy('user', 'Deny',  event['methodArn'])
    return authResponse

IAMロールの設定

ここで少し嵌ったのだが,ロールの「信頼関係」にAPI Gatewayが指定されていないとLambda関数が実行できないらしい。

IAMのロールから信頼関係タブを開き,信頼関係の編集を行う。

"Service""apigateway.amazonaws.com"を追加する。

API Gatewayにオーソライザーを追加する

API Gatewayにオーソライザーを追加する。

タイプはLambda関数,IDソースにはクエリ文字列,"access_token"などと追加する。

後はリソースタブからメソッドリクエスト画面で,認証に先程作ったカスタムオーソライザーを指定する。

IFTTT側の設定

エンドポイントのURLに"access_token=***"を付けてアクセスするよう変更する。

結論

懸念事項だったセキュリティが少し堅牢になった(はず)。

セキュリティに配慮できる高度クラウド文字列シャッフル人材なので完全週休2日制,年収1千万円の職がほしい。

謝辞

本記事の一部はAmazon Web Serviceの無料利用枠で書かれた。

2017年12月2日土曜日

ガゲァスAdvent Calender 2日目

クラウドを使ってサーバーレスでガゲマックをシャッフルする

サーバレスっていうのが流行っているらしいので,雑にガゲマックをシャッフルしていく。

概要

IFTTTのDate&TimeトリガーでWebhookを使ってAWS API Gatewayで作成したAPIのエンドポイントを叩く。

AWS Lambdaで文字列をシャッフルする。

Lambda内の処理でIFTTTのWebhookを叩いて,Twitterでツイートする。

1. ツイートするレシピを作る

  • Webhookのエンドポイントを確認する
  • {event}となっている部分にイベント名を入力すると,いい感じにエンドポイントのURLが出てくる(便利)。

  • レシピを作る
  • thisはWebhook,thatはTwitterで作る。

2.AWS Lambda

実際にシャッフルを行う関数を作成する。

  • 新しい関数の作成
  • 記事執筆時点でC#,Java8,Node.js 4.3,Node.js 6.10,Python 2.7,Python 3.6が使える。今回はPython 3.6を使う。

  • 関数(実行するコード)の作成
  • import urllib.request
    import random
    
    def string_shuffle(str):
        ls = list(str)
        random.shuffle(ls)
        return "".join(ls)
    
    def ifttt_request(values):
        # WebhookのエンドポイントURLを指定する
        ifttt_url_endopoint = 'https://maker.ifttt.com/trigger/*****'
        data = urllib.parse.urlencode(values).encode('ascii')
        req = urllib.request.Request(ifttt_url_endopoint, data)
        with urllib.request.urlopen(req) as response:
            charset = response.headers.get_content_charset()
            content = response.read().decode(charset)
        return content
    
    def lambda_handler(event, context):
        values = {
            'value1': string_shuffle(event['message']), 
            'value2': event['message']
        }
        content = ifttt_request(values)
        return content
    

3.AWS API Gateway

APIを作る。

  • 新しいAPIの作成
  • 新しいAPI→API名等を入力するだけ。

  • メソッドの作成
  • アクション→メソッドの作成→「GET」を選択→(✓)をクリックする。

    統合タイプは「Lambda関数」,LambdaリージョンをLambda関数のリージョンに設定する。

    Lambda関数は作った関数の名前を入れる。

    すると一通りの流れが出来上がる。

  • パラメータの追加
  • シャッフルする文字列はリクエストから指定できると汎用性がある。

    今回はURLのクエリ文字列で指定する。("/?message=~~~"とする。)

    まずメソッドリクエストからURLクエリ文字列パラメータとして"message"を追加する。

    追加したパラメータの必須チェックボックスをtrueにし,さらにリクエスト時の検証を行うよう設定する。

    次に統合リクエストから本文マッピングテンプレートを用いて"Content-type: application/json"に対して

    {
      "message": "$input.params("message")"
    }
    

    と入力し,保存する。

  • APIのデプロイ
  • APIをデプロイする。今回は本番環境のみとして,ステージ名はprodにした。

    アクション→APIのデプロイから,デプロイされるステージ: [新しいステージ],ステージ名: prodと設定する。

    デプロイに成功すると,ステージエディタが開く。メソッドスロットリングの設定などを変更し,保存する。

4. 指定した時になったらAPIを叩くレシピを作る

thisがDate&Timeで,thatがTwitter→postと指定する。

結論

流行りに乗ってサーバーレスにしてみたが,意外と簡単にできた。AWSさんはすごいのだ。

本当はAPIキーで認証を掛けようと思ったのだが,IFTTTからヘッダ付きでAPIを叩く方法がわからないのでダメだった…

高度クラウド文字列シャッフル人材なので完全週休2日制,年収1千万円の職がほしい。

謝辞

本記事の一部はAmazon Web Serviceの無料利用枠で書かれた。

2013年12月8日日曜日

mikutterの起動スクリプト

mikutterの起動スクリプト

概要

タイトルまんまで,mikutterの起動スクリプトを書いた。 シェルで

$ ruby mikutter.rb
してもいいのだが,それだけのためにshellを使うのもアレだし,
$ ruby mikutter.rb &
とすると,今度は余計な親切なメッセージが出力される。

あと,rubyの複数バージョンを入れておいてalternativesしてたりすると,どのバージョンで起動するかも考慮しないといけない。 いろいろ面倒なので,それっぽく解決するスクリプトを書いた。

まぁ,mikutter使ってる人はだいたいそういうのを自前で持ってそうだから公開する必要もなさそうだが,忘備録的に残しておく。

スクリプト

実物はgithubにある。

$ git clone https://github.com/gofer/mikutter_run.git
とでもすれば,そのまま最新版が落ちてくる。 Readmeに書いてあること,それがすべてだ。

参考文献

mikutter:
http://mikutter.hachune.net

2013年6月23日日曜日

平成25年度 春期 応用情報技術者試験 結果

AP受けました。受かりました。
だからなんだって話ですけどね。

一応経緯をさらっと述べると,
旧試のFE受かる
→旧試のSW落ちる
→やーめた
→悠久の時の流れ(超えられない壁)
→新試AP合格
みたいな。

んで,結果。

得点
午前75.00点
午後82.00点

午前分野別得点
ストラテジ系15.00点 / 25.00点 (60.0%)
マネジメント系11.25点 / 12.50点 (90.0%)
テクノロジ系48.75点 / 62.50点 (78.0%)

午後の問題選択分野
2(アルゴリズム),
4(システムアーキテクチャ),
5(ネットワーク),
7(エンベデッド),
8(システム開発),
9(セキュリティ)

総括: 午前のテクノロジもっと取りたかった(85%くらい)。

2013年2月15日金曜日

Compiled gcc4.7.2

gcc4.7(.2)の環境つくった忘備録

意外と面倒なgccのコンパイル。
最新版のgccであれこれ楽しもう的な。
環境はCentOS 6。
その忘備録。



用意するもの

pplとcloog(cloog-ppl)以外はそれぞれ最新版のソースをもってくる。
pplとcloog(cloog-ppl)はどうもバージョンの指定があり,依存があるらしい。
詳しくはgccのソースを展開してINSTALLディレクトリのドキュメントを参照すればいい。
というか,gccのインストールに必要なことはだいたいそこに書かれいてる。
  • binutils (2.23.1)
  • gmp (5.1.1)
  • mpfr (3.1.1)
  • mpc (1.0)
  • ppl (0.11)
  • cloog / cloog-ppl (cloog-ppl-0.15.11)
  • gcc (4.7.2)

以下全部スーパーユーザで作業します。

1. binutils

# tar zxvf binutils-2.23.1.tar.gz
# cd binutils-2.23.1
# mkdir build; cd build
# ../configure
# make
# make check
# make install


2. GMP

--enable-cxxを付け忘れるとPPLのmakeで痛い目に遭う。
# tar jxvf gmp-5.1.1.tar.bz2
# cd gmp-5.1.1
# mkdir build; cd build
# ../configure --enable-cxx
# make
# make check
# make install
そんでもって,これを忘れてハマった!
環境変数の設定。
# export LD_LIBRARY_PATH=/usr/local/lib:$LD_LIBRARY_PATH
# export LD_RUN_PATH=/usr/local/lib:$LD_RUN_PATH


3. MPFR

# tar jxvf mpfr-3.1.1.tar.bz2
# cd mpfr-3.1.1
# mkdir build; cd build
# ../configure --with-gmp=/usr/local
# make
# make check
# make install


4. MPC

# tar zxvf gmp-1.0.tar.gz
# cd gmp-1.0
# mkdir build; cd build
# ../configure --with-gmp=/usr/local --with-mpfr=/usr/local
# make
# make check
# make install


5. PPL

たしか,多重定義エラーでmakeがこけるので,/usr/local/include/gmpxx.hのほうをコメントアウトで解決する。
# tar zxvf ppl-0.11.tar.gz
# cd ppl-0.11
# mkdir build; cd build
# ../configure --with-gmp-prefix=/usr/local
# make
# make check
# make install


6. cloog / cloog-ppl

# tar zxvf cloog-ppl-0.15.11.tar.gz
# cd cloog-ppl-0.15.11
# mkdir build; cd build
# ../configure  --with-gmp=/usr/local --with-ppl=/usr/local
# make
# make check
# make install


7. GCC

# tar zxvf gcc-4.7.2.tar.gz
# cd gcc-4.7.2
# mkdir build; cd build
# ../configure --with-gmp=/usr/local --with-mpfr=/usr/local --with-mpc=/usr/local --with-ppl=/usr/local --with-cloog=/usr/local --program-suffix=-4.7
# make
# make check
# make install


これで
# gcc-4.7 -v
とでもすればうまくいったと確認できる。

2012年9月20日木曜日

週刊 TD4をFPGAで創る 第5号 「命令デコーダを創る」

週刊 TD4をFPGAで創る 第5号 「命令デコーダを創る」

第9章からです。
ついにシミュレーション編完結!!

命令デコーダがどのような経緯でIC2つに収まったかは渡波(2003)をご参照くださいな。

Amazon.co.jp - 渡波 郁 「CPUの創りかた」 毎日コミュニケーションズ (2003)

1.74HC10

まずは3入力NAND3つ入り!

module LOGIC_74HC10(A1, B1, C1, Y1, A2, B2, C2, Y2, A3, B3, C3, Y3);
 input A1, B1, C1, A2, B2, C2, A3, B3, C3;
 output Y1, Y2, Y3;
 
 assign Y1 = ~(A1 & B1 & C1);
 assign Y2 = ~(A2 & B2 & C2);
 assign Y3 = ~(A3 & B3 & C3);
endmodule

テストベンチはいらないよね?

2.74HC32

次に2入力OR4つ入り!

module LOGIC_74HC32(A1, B1, Y1, A2, B2, Y2, A3, B3, Y3, A4, B4, Y4);
 input A1, B1, A2, B2, A3, B3, A4, B4;
 output Y1, Y2, Y3, Y4;
 
 assign Y1 = A1 | B1;
 assign Y2 = A2 | B2;
 assign Y3 = A3 | B3;
 assign Y4 = A4 | B4;
endmodule

これもテストベンチはいらないよね?

3.命令デコーダ

いよいよ命令デコーダづくり!
気合入れていきましょう。

module InstructionDecoder(OPERATION_CODE, C_FLAG_BAR, LOAD_0, LOAD_1, LOAD_2, LOAD_3, SELECT_A, SELECT_B);
 input [3:0] OPERATION_CODE;
 input C_FLAG_BAR;
 output LOAD_0, LOAD_1, LOAD_2, LOAD_3, SELECT_A, SELECT_B;
 
 reg Vcc = 1;
 reg GND = 0;
 
 wire [1:0] w;
 
 assign SELECT_B = OPERATION_CODE[1];
 
 LOGIC_74HC32 logic_74hc32 (
  OPERATION_CODE[2], OPERATION_CODE[3], LOAD_0, 
  w[0], OPERATION_CODE[3], LOAD_1, 
  OPERATION_CODE[0], OPERATION_CODE[3], SELECT_A, 
  OPERATION_CODE[0], C_FLAG_BAR, w[1]
  );
 
 LOGIC_74HC10 logic_74hc10 (
  OPERATION_CODE[2], Vcc, Vcc, w[0], 
  Vcc, w[0], OPERATION_CODE[3], LOAD_2, 
  OPERATION_CODE[2], OPERATION_CODE[3], w[1], LOAD_3
  );
endmodule

はい!出来上がり!

テストベンチはこんな感じ!

module instruction_decoder_test;
 reg  [3:0] OPCODE;
 reg  C_FLAG_BAR;
 wire LOAD_0, LOAD_1, LOAD_2, LOAD_3, SELECT_A, SELECT_B;
 
 InstructionDecoder decoder(OPCODE, C_FLAG_BAR, LOAD_0, LOAD_1, LOAD_2, LOAD_3, SELECT_A, SELECT_B);
 
 initial begin
  $dumpfile("instruction_decoder_test.vcd");
  $dumpvars(0, instruction_decoder_test);
  $monitor ("%t: OPCODE = %b%b%b%b, C_FLAG_BAR = %b, (SELECT_B, A, LOAD_0, 1, 2, 3) = %b %b %b %b %b %b", 
   $time, OPCODE[3], OPCODE[2], OPCODE[1], OPCODE[0], C_FLAG_BAR, 
   SELECT_B, SELECT_A, LOAD_0, LOAD_1, LOAD_2, LOAD_3);

   OPCODE = 4'b0000; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b0001; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b0010; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b0011; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b0100; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b0101; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b0110; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b0111; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b1001; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b1011; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b1110; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b1110; C_FLAG_BAR = 1'b1;
  #10 OPCODE = 4'b1111; C_FLAG_BAR = 1'b0;
  #10 $finish;
 end
endmodule

出力結果をよーく本と見比べてね!

4.そして,完成へ…

長かったCPUづくりもいよいよ一段落です。
すべてのパーツを組み合わせましょう。

module Processor(RESET, CLOCK, INPUT, OUTPUT);
 input RESET, CLOCK;
 input [3:0] INPUT;
 output [3:0] OUTPUT;
 
 reg  Vcc = 1'b1;
 reg  GND = 1'b0;
 wire [5:0] NOT_IN_USE;
 
 wire [3:0] ROM_ADDRESS;
 wire [7:0] ROM_DATA;
 wire [3:0] OPERATION_CODE;
 wire [3:0] IMEEDIATE_DATA;
 
 wire LOAD_0, LOAD_1, LOAD_2, LOAD_3, SELECT_A, SELECT_B;
 
 wire [3:0] REGISTER_IN;
 wire [3:0] REGISTER_A_OUT;
 wire [3:0] REGISTER_B_OUT;
 wire [3:0] REGISTER_C_OUT;
 wire [3:0] REGISTER_D_OUT;
 wire [3:0] ALU_IN_A;
 wire [3:0] ALU_IN_B;
 wire CARRY_OUT, C_FLAG, C_FLAG_BAR;
 
 assign ROM_ADDRESS = REGISTER_D_OUT;
 assign OPERATION_CODE = ROM_DATA[7:4];
 assign IMEEDIATE_DATA = ROM_DATA[3:0];
 assign ALU_IN_B = IMEEDIATE_DATA;
 assign OUTPUT = REGISTER_C_OUT;
 
 ROM_16WORD  ROM(ROM_ADDRESS, ROM_DATA);
 
 InstructionDecoder Instruction_Decoder (OPERATION_CODE, C_FLAG_BAR, 
  LOAD_0, LOAD_1, LOAD_2, LOAD_3, SELECT_A, SELECT_B);
 
 LOGIC_74HC161 Register_A (RESET, CLOCK, 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  GND, LOAD_0, GND, 
  REGISTER_A_OUT[0], REGISTER_A_OUT[1], REGISTER_A_OUT[2], REGISTER_A_OUT[3], 
  NOT_IN_USE[0]);
  
 LOGIC_74HC161 Register_B (RESET, CLOCK, 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  GND, LOAD_1, GND, 
  REGISTER_B_OUT[0], REGISTER_B_OUT[1], REGISTER_B_OUT[2], REGISTER_B_OUT[3], 
  NOT_IN_USE[1]);
  
 LOGIC_74HC161 Register_C (RESET, CLOCK, 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  GND, LOAD_2, GND, 
  REGISTER_C_OUT[0], REGISTER_C_OUT[1], REGISTER_C_OUT[2], REGISTER_C_OUT[3], 
  NOT_IN_USE[2]);
  
 LOGIC_74HC161 Register_D (RESET, CLOCK, 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  Vcc, LOAD_3, Vcc, 
  REGISTER_D_OUT[0], REGISTER_D_OUT[1], REGISTER_D_OUT[2], REGISTER_D_OUT[3], 
  NOT_IN_USE[3]);
 
 LOGIC_74HC153 Register_Selector_0 (SELECT_A, SELECT_B, GND, GND, 
  REGISTER_A_OUT[0], REGISTER_B_OUT[0], REGISTER_C_OUT[0], GND, 
  REGISTER_A_OUT[1], REGISTER_B_OUT[1], REGISTER_C_OUT[1], GND,
  ALU_IN_A[0], ALU_IN_A[1]);
  
 LOGIC_74HC153 Register_Selector_1 (SELECT_A, SELECT_B, GND, GND, 
  REGISTER_A_OUT[2], REGISTER_B_OUT[2], REGISTER_C_OUT[2], GND, 
  REGISTER_A_OUT[3], REGISTER_B_OUT[3], REGISTER_C_OUT[3], GND, 
  ALU_IN_A[2], ALU_IN_A[3]);
 
 LOGIC_74HC283 ALU (GND, 
  ALU_IN_A[0], ALU_IN_A[1], ALU_IN_A[2], ALU_IN_A[3], 
  ALU_IN_B[0], ALU_IN_B[1], ALU_IN_B[2], ALU_IN_B[3], 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  CARRY_OUT);
 
 LOGIC_74HC74 C_Flag (RESET, CARRY_OUT, CLOCK, Vcc, C_FLAG, C_FLAG_BAR, 
  GND, GND, GND, GND, NOT_IN_USE[4], NOT_IN_USE[5]);
 
endmodule

完成!!!!!!!!!

実際に動かしてみよう!
テストベンチは次の通り。

module processor_test;
 reg  RESET, CLOCK;
 reg  [3:0] INPUT;
 wire [3:0] OUTPUT;
 
 Processor processor(RESET, CLOCK, INPUT, OUTPUT);
 
 initial begin
  $dumpfile("processor_test.vcd");
  $dumpvars(0, processor_test);
  $monitor ("%t: CLOCK = %b, RESET = %b, INPUT = %b%b%b%b, OUTPUT = %b%b%b%b", 
   $time, CLOCK, RESET, 
   INPUT[3], INPUT[2], INPUT[1], INPUT[0], 
   OUTPUT[3], OUTPUT[2], OUTPUT[1], OUTPUT[0]);
  
  CLOCK = 0;
  RESET = 1;
  INPUT = 4'b0000;
  #400 $finish;
 end
 
 always #1
  CLOCK = ~CLOCK;
endmodule

LEDチカチカとラーメンタイマーそれぞれ動いたでしょうか?
これにて一段落。

次回予告

次回は実際にFPGAに実装してみたいと思います。(多分)

Amazon.co.jp - 渡波 郁 「CPUの創りかた」 毎日コミュニケーションズ (2003)