簡単な演算子順位法によるパーサー in Ruby

(Simple Operator Precedence Parser in Ruby)

by Akihiko Koga
11th Feb. 2019 (Update)
11th Feb. 2019 (First)

計算機(主にソフトウェア)の話題 へ
ホームページトップへ戻る

目次

  1. 趣旨
  2. 方針
  3. 簡単な説明
  4. 注意事項
  5. プログラムリスト
  6. 実行例
  7. 変更履歴
  8. 参考文献

趣旨

計算機科学の分野の人は,様々な計算機理論を勉強するのに,やっぱり, 学習していることを実際に動かしてみたいという 衝動に駆られることが多いと思います.一般的に理論は抽象的で,根を詰めてやると, 飽きる辛い楽しくないという状況に陥ります.例えば圏論でプログラムの意味を付ける理論は 読んでいるとその極度の抽象性から逃避したくなるし,計算機に関係の深い言語理論 やラムダ計算だって本を読んでいるだけでは分かったような分からないような, しまいにどうでもよくなってきます.

そんなとき,学習している理論をちょっと実装してみて動かしてみると, 気分が変わるし,学習対象の一点でも深く理解すると周りの理解の糸口も見えてくる かもしれません.人間は止まっているものより,動いているものに注意を払う ものです. というか,動いていないと注意を向けることができないのかもしれません.

で,そういった理論の実装をしてみるのでも,例えば,LISP や Ruby のリストや配列を 使った内部コードっぽい式では 気分がでないので,何となく数学っぽい記法で動くものを作りたいと思いました.

ということで,ここでは,計算機数学の理論をちょっと実装して楽しむときに 使えるような超簡単なパーサーを作ろうと思います. 計算機(主にソフトウェア)の話題 で 前に取り扱ったλ式をコンビネータ論理に変換する話なんかも,こういう パーサーが用意されていたら,もう少し簡単に出来たかもしれません.

ここで作るパーサーは Ruby で動作し,基本的に演算子順位文法の構文を 解析するものですが,多少拡張して,λ式やコンビネータ式も解析できる ようにしました. λ式やコンビネータ式は通常,空白で関数適用をする形式(E1 E2) のような式があるので 演算子順位文法にはなりません(つまりE1 と E2 という式が演算子無しで結合される場合がある).

以下,パーサーの方針,簡単な解説,注意事項,プログラムリストと続きますが,あまり御託を 読みたくない人は,プログラムリストに飛んでもらっても 構いません.

また,この簡易パーサーのプログラムは一般的なものなので, 特に私が権利を主張するようなものでもないので自由に 持って行って改造して使って構いません.ただし,私が使う権利を はく奪する形で権利を主張するのはやめていただきたいです. こまかな注意事項は,注意事項に書きました.

方針

ここに挙げた構文解析プログラムは,出来るだけ簡単で,しかも,十分に計算機理論の学習に利用できる 構文解析プログラムを作ろうという方針で作りました.

具体的には次のような方針で作りました.

  1. 利用を想定する題材
    1. ラムダ式で遊ぶ,コンビネータで遊ぶ
      このページと同じレベルにあるページ コンビネータ論理(Combinatory Logic) のお話 λ式から SKI を使った式への変換のトレース のようなイメージの使い方です.そちらは, ここよりもう少し力業で作って遊んでいました.

    2. 型理論の基礎を学ぶ
      これがこのパーサーを作ろうと思った直接の理由です. よく,圏論の応用として,圏論(Category Theory)を使った 簡易型付きラムダ計算の意味論などをレクチャーノートとして 公開している大学の先生方がいるが,圏論もあまり分からない, 簡易型付きラムダ計算もあまり実感が持てない人(私です)に とっては,興味はあるが,とてもつらいレクチャーノートに なるわけです.せめて,型付きラムダ計算のなにか(型導出系とか ある種の実行系など)を実装してみると,少なくとも 簡易型付きラムダ計算の方は実感が湧くようになるかなと思った 次第です.あとは,圏論を勉強すればよいだけ.

    3. 論理学を学ぶ
      論理式を構文解析できるようにして,例えば,充足可能性とかの 概念を学ぶとか.

    4. 簡単なインタープリタを作って遊ぶ
      小さな lisp 相当の言語で多少シンタクスがユーザに 優しいような言語のインタープリタを作って遊べればよいなっと.

    5. 言語理論を学ぶ
      正規言語やBNFなどを見た目優しく読み込めるようになるとよいかなっと.

      例えば,(a+b)* を有限オートマトンに変換するなどです. 適当な定義のもとに,ここのパーサーを使えば,(a+b)* は,ruby の 配列 [:"*", [:"+", "a", "b"]] に変換されますので,オートマトンの 教科書などをみながら,これを受理するオートマトンを作ってみるのは 良い勉強になります.

  2. 方式と大きさ
    あとで「注意事項」で述べるように,このプログラムは コピー&ペーストして使ってもらうことを考えており,そのため, まあ,せいぜい200行に抑えたい.

    実際に作成した結果としては,演算子の定義,式の表示関数, テスト用のプログラムを含めると250行くらいになりましたが, 構文解析部分だけなら 200 行に納まりました(160行くらいですね. 2019年 2月 10日 時点).

  3. 性能
    2019 年の普通の PC で理論勉強に,普通にイライラせずに応答が返ってくれば OKとする.まあ,大部分の入力に対して,1秒以内で返ってくれば良しと します.現在の計算機は速いですから,手で入力できる入力の解析には 1秒かからないでしょうけど.

簡単な説明

内容
  1. どんな言語をどんな表現に変換するのか
  2. 言語の定義方法などの簡単な説明
    1. 演算子の定義
    2. 括弧の定義
    3. 暗黙の演算子
    4. 文字列の扱い
    5. いくつかの補足
  3. プログラムの簡単な説明
    1. 主な関数
    2. 主な大域変数

  1. どんな言語をどんな表現に変換するのか

    まず,演算子順位文法とはどんな文法かと言うことを簡単に説明しておきます. ここで掲載するプログラムは,典型的には

    入力 "a*b - c/d" を,[:-, [:*, "a", "b"], [:/, "c", "d"]] に解析
    (:-, :* は Ruby の記法でそれぞれ,- と * というシンボルです.
    Prolog の ":-" ではありません)
    するプログラムです. 以下,ちょっとだけ形式言語の理論っぽいことを説明します.

    ここでは2項演算までを考えることにします.以下,文法そのものの説明でなく, そのような文法で表すことができる言語について説明します.大雑把に言って, 二項までの演算子を使った演算子優先順位文法では次の BNF で生成できる ような言語を表現できます.

    	Exp ::= BasicToken | 
                    PrefixOp Exp |
                    Exp PostfixOp |
                    Exp InfixOp Exp |
                    ( Exp )
    
    ここで BasicToken は予め定められた Exp になるデータがあると思ってください. 実際のプログラミング言語では,数や文字列などの定数とか,変数名とかがこれに あたります.また,PrefixOp は前置される演算子,PostfixOp は後置される演算子, InfixOp は中置される演算子を表し,予めどんなものがあるかは特定されているとします.

    この文法は曖昧性を持ちます.例えば,op が二項演算子,a が BasicToken とすると, a op a op a は,(a op a) op a とも解釈されるし,a op (a op a) とも解釈されます. 演算子順位文法は演算子の優先順位という概念を 使って,この曖昧性を解消できる文法です.例えば,普通の加減乗除を使った式では 掛け算が足し算や引き算より結合力が強いとして扱われ,例えば

    x*y+z*w は (x*y) + (z*w) として解釈されます

    (x*(y+z)*w や x*(y + (z*w)) などではなく)

    となります.ここでは演算子に対して結合力を表す数値や結合の型,例えば,

    左結合的なら x + y + z + w は ((x + y) + z ) + w と結合される

    などの結合の型を指定することにより,パーサーに構文解析の方法を指示するタイプの パーサーを作成します.

    言語は Ruby を使って書きます.文字列の式は Ruby の配列などのデータに変換することに します.例えば,上の例でいうと,下に掲載したプログラムを使うと

    x*y+z*w は [:"+", [:"*", "x", "y"], [:"*", "z", "w"]] に

    変換されます.つまり,

    [2項演算子, 最初の式の内部構造, 次の式の内部構造]

    [1項演算子, 式の内部構造]

    の組み合わされた木構造に変換されるわけです.ここで,:"+" は,"+" という表示名を持つシンボルです(これは文字列 ":" を使ってもよいのですが,涙を飲んで,シンボルに しました.これについては後で書きます).この形だと,ある程度 Ruby を書ける人は 再帰的な関数を書くことにより,色々な処理を記述することができると思います.

    非常に大雑把な説明でしたので,演算子順位文法,演算子順位法の構文解析に ついて正しく知りたい人は参考文献に挙げてある文献等 を参照してください.

  2. 演算子指定の簡単な説明

    ここで作る演算子順位パーサーでは,非演算子の最小単位は文字列であり,非演算子のほかに 2つの種類のもの,つまり,演算子括弧を定義することにより文法を規定します.ここでは,これら二つと,もう一つ,暗黙の演算子について説明します.

    1. 言語の定義方法などの簡単な説明
    2. 括弧の定義
    3. 暗黙の演算子
    4. 文字列の扱い
    5. いくつかの補足

    演算子の定義

    まず,演算子の定義について説明します.

    後に掲載しているプログラムリストから,それら二つの定義部分を抜き出してみましょう. これは演算子定義のサンプルのために最初から入れてある演算子定義です.これを 書き直すことにより,自分が望む形の式を構文解析できるようになります.

    いまから作るパーサーは,Ruby の大域変数 $sop_ops に連想配列(ハッシュ)として 演算子を定義することにより,その演算子を使った式が構文解析できるようになります. 例えば,定義の最初の方をみると, 演算子 "->" は優先度 1000 で,右結合的な演算子 (:xfy) として定義されています. これは,

    A->B->C->D という文字列があれば,(A->(B->(C->D))) と解釈され,

    [:"->", "A", [:"->", "B", [:"->", "C", "D"]]] のように構文解析される

    ことを意味します.

    $sop_ops = {
      # in_name  => [out_name, priority, op_type]
      :"->"      => ["->", 1000, :xfy],
      :"*"       => ["*",   400, :yfx],
      :"/"       => ["/",   400, :yfx],
      :"+"       => ["+",   500, :yfx],
      :"+/pre"   => ["+",   200, :fy],
      :"-"       => ["-",   500, :yfx],
      :"-/pre"   => ["-",   200, :fy],
      :"="       => ["=",  1500, :xfy],
      :";/post"  => [";",  1800, :yf],
      :";"       => [";",  1800, :yfx],
      :","       => [",",  1400, :xfy],
      :"#apply#" => ["#apply#", 1300, :yfx], # implicit operator
      :"#list#"  => ["#list#", 200, :fy],    # list marker  
      :"#set#"   => ["#set#",  200, :fy],    # set marker
      
      # paren =>
      #  [out_name, priority, paren_type, [pair_paren, ...], valOf(), marker
      :"("       => ["(", 10000, :open,  [:")"], "0",  nil],
      :")"       => [")", 10000, :close, [:"("]],
      :"["       => ["[", 10000, :open,  [:"]"], [], :"#list#"],
      :"]"       => ["]", 10000, :close, [:"["]],
      :"{"       => ["{", 10000, :open,  [:"}"], :"empty", :"#set#"],
      :"}"       => ["}", 10000, :close, [:"{"]],
    }
    

    :"->" の後ろに :"*" があります.こちらは,優先度 400 で型が左結合的 (:yfx) の 演算子であることを表しています.優先度は少ない方が強く結合すると解釈します. ここらあたりは,論理型言語 Prolog の方式を採用しており,一般の演算子順位文法の 優先度とは大小が逆かもしれません.とにかく,ここでは数値が小さいほど結合度が強く, 数値が大きいほど結合度が小さいと解釈します.したがって,

    A*B->C は (A*B)->C と解釈され,[:"->", [:"*", "A", "B"], "C"] というデータに変換されます
    ということになります.また,* は -> と違って左結合的 (:yfx) なので,
    A*B*C は (A*B)*C と解釈される
    ことになります.+ や - など,我々が数学で使う多くの演算子は左結合的です.

    演算子は連想配列(ハッシュ) $sop_ops の中で次のように定義してください.

        内部名 => [外部名, 優先度, 演算子型 [, 表示名]],
    
    この一番最後の [, 表示名] はオプショナルで,あっても無くても 結構です.下に掲載したプログラムの中ではつかっていません.通常の演算子では ここはあまり使いません. 例えば,二項演算子 "+" は次のように定義されています.
        :"+" => ["+", 500, :yfx],
    
    それぞれの項目について説明します.

    括弧の定義

    次は括弧の定義について説明します. あとで挙げるプログラムリストの中には3種類の括弧,(), [], {} が予め定義されています. 当面,これで間に合うことも多いので,ここはざっと目を通しておいて,必要になったら 読むのでも構いません.

    予め組み込まれている括弧の定義を次に示します.

    $sop_ops = {
    
       ... #演算子の定義列
    
      # paren =>
      #  [out_name, priority, paren_type, [pair_paren, ...], valOf(), marker
      :"("       => ["(", 10000, :open,  [:")"], "0",  nil],
      :")"       => [")", 10000, :close, [:"("]],
      :"["       => ["[", 10000, :open,  [:"]"], [], :"#list#"],
      :"]"       => ["]", 10000, :close, [:"["]],
      :"{"       => ["{", 10000, :open,  [:"}"], :"empty", :"#set#"],
      :"}"       => ["}", 10000, :close, [:"{"]],
    

    括弧はこのように,

        内部名 => [外部名, 優先度, 括弧の型, 対応括弧列, ()の値, マーカー
    

    の形で定義されます.

    それぞれを説明します.

    暗黙の演算子

    ここで作成するのは演算子順位法によるパーサーですが,ここで応用例として挙げている 中で,λ計算の式は,演算子順位法によっては解析できません.これは

    E1 E2
    のような構文があるためです.これは関数 E1 を E2 に適用することを表します. λ計算の理論ではこれを一々,apply(E1, E2) のように書きたくないので,単に E1 と E2 を並べて書きます.上の例では二つの式の間に空白がありますが, 明確に二つが分離できる場合は空白も書きません.例えば,(λx.x)(λx.x) など です.

    この場合をうまく扱えるように,ここではこういう,式が並べて書いてあるところに 演算子を挿入していく方法をとります.これは最初に,入力を演算子や非演算子の列に 分解した後,式が二項演算子無しに隣り合っているところに,予め決めておいた 二項の演算子を挿入します.挿入される演算子は,Ruby の大域変数

    $sop_implicit_op
    に入っている値とします.最初は,この変数には :"#apply#" が入っていますので,例えば,
    (a b c)+1 は [:"+", [:"#apply#", "a", [:"#apply#", "b", "c"]], "1"]
    に解析されます.

    文字列の扱い

    λ計算やコンビネータ論理などの実験ではほとんど出てくることがありませんが, 時々,文字列を扱えたらよいと思うことがあります. それは非常に簡単な言語のインタープリタを作るときなどです.後に 挙げたプログラムでも,ごくごく簡単な文字列だけ最初から組み込んであります. これはユーザがカスタマイズすることができるものではありませんが, "..." は常に文字列として扱われて,構文解析後,「"」で始まって「"」で終わる文字列 として分離されています.ただし,... の部分は任意の文字列で,「"」を含ませたい 場合は,「\」でエスケープしてください.例えば,

    "the symbol"+"* is star" は
    [:"+", "\"the symbol\"", "\"* is star\""] として

    構文解析されます.

    いくつかの補足

    1. プログラムを読んでもらえばわかるのですが,ここに挙げたプログラムでは トークンに区切る処理をかなりサボっているため,演算子として定義した文字列は 他の文字列の部分文字列として含まれていると,その部分も演算子として認識されます. 例えば,"if" を :xfy 型の演算子として定義してしまうと,"diff + delta" は "d if f + delta" のように解釈されてしまいます.これは簡易なパーサーで,所詮, 計算理論の実験をするためのやっつけ仕事と割り切って使うと言うことでご容赦ください.

      ただし,この欠点は逆手にとって活用することもできます.例えば,"S", "K", "I" を それぞれ,:f 型の演算子として定義すれば,続けて書いた SKI コンビネータ式 SKI(KKS) などが S K I (K K S) のように分離されて入力されますので,コンビネータの 教科書などの式(空白が入っていないことが多い)を直接確かめることができます.

      また次の項で説明するように if を演算子にするのではなく,何か一文字,特殊な文字を 足して #if などを演算子にすることで 先ほどの,"diff + delta" が意図しないところで分割されるという問題を 回避することが出来ます.

    2. 「"」と「#」は特別な意味を持たせていますので,演算子や括弧の外部名としては 使わないでください.ただし,「#」については,他の文字列と組み合わせれば 使っても結構です.例えば,"def" を演算子にしてしまうと,"def1"などの 名称が使えなくなってしまいますので,"#def"を演算子の外部名として使うことで そのような制限を取り去ることができます.

    3. 「(」と「)」の定義は変更しないでください.今の作りは,入力の先頭と最後に この括弧を入れることにより,構文解析がすべて終わるように作っていますので, これを変えると動かなくなります.

    4. あと,空白も演算子や文字列以外の非演算子に含めることはできません.

  3. プログラムの簡単な説明

    主な関数

    1. sop_split(str, implicit_op_mode = $sop_implicit_op_mode)
      定義されている演算子の下に,与えられた文字列をトークン(文字列,演算子, 括弧)の列に変換します.implicit_op_mode が false でないときは, 式と式が隣り合わせの箇所には暗黙の演算子(大域変数 $sop_implicit_op の 内容)が挿入されます.この関数をユーザが直接使うことは少ないと思います. せいぜい,与えられた文字列がどんなトークン列に変換されているか確認 するときくらいでしょう.

    2. sop_parse(str, implicit_op_mode = $sop_implicit_op_mode)
      定義されている演算子の下に,与えられた文字列を構文解析してその 結果を返します.implicit_op_mode が false でないときは 式と式が隣り合わせの箇所には暗黙の演算子(大域変数 $sop_implicit_op の 内容)が挿入されてから構文解析されます.

      内部処理は

        def sop_parse(str, implicit_op_mode = true)
          begin
            sop_parse2(sop_split(str, implicit_op_mode))
          rescue
            :error
          end
        end

      のようになっていて,まず,sop_split() でトークン列に変換された 結果を,関数 sop_parse2() で構文木に変換する.その際,エラーが あれば,error というシンボル(:error)を返すようになっています.

    3. sop_parse2(tlist)
      この関数が実際にトークン列を構文解析して構文木を作る関数です.

      この解説はまた時間ができたときにします.当面はじぶんで読んで下さい.

    4. sop_print(code, nl = true)
      構文解析した結果の code を元のような式としてプリントします. 演算子の優先度と型を加味して必要がなければ,括弧は省略します. 第二引数 nl に false を入れれば,最後に改行を出力しません.第二引数に なにも入れなければ,つまり,code だけを指定すれば,式を出力した後,改行を出力します.

    5. test
      入力がどのように構文解析されるかを確かめるための簡単な プログラムです.test と呼び出すと,コマンドは q または d または 任意の文字列です.

      q と d 以外の入力は式の文字列が入力されている多として,それを構文解析した 結果が表示されます.表示は,解析結果の Ruby のデータそのものと,それを 演算子を考慮して表示したものです.後者は大部分の場合,入力と同じでしょう.

      q を入力すると test を終わることができます. d はデバッグモードの ON/OFF を切り替えます.デバッグモードでは, まず,入力がどのようなトークン列に変換されたかを表示し,あとは, 入力を一つ読むごとの内部状態が表示され,どのように構文木が作られていくかの 過程が分かるようになっています.

    主な大域変数

    1. $sop_ops
      演算子,括弧の定義が格納されている重要な大域変数です. この定義を変えることによって,構文解析できる式や結果が変わってきます. 下のプログラムでは初期値として与えてありますが,
        $sop_ops[:"=>"] = ["=>", 1200, :xfy]
      
      のように入れることもできます. 関数 sop_parse() は呼ばれるたびに,内部で,この変数から動作のためのデータを 作り出しますから,データを変えれば,即,新しい定義が適用されます.

    2. $sop_implicit_op_mode
      入力を構文解析するとき,識別子と識別子の間などに暗黙の演算子を挟むか どうかを表します.これを false (あるいは nil)にすると,このような余計な暗黙の演算子は 挟まず,実際の入力の演算子だけで構文解析が行われます.したがって, a, b が演算子として定義されていない場合は,a b は構文エラーです.

      それに対して,$sop_implicit_op_mode が false や nil 以外なら, このような識別子と識別子の間などに暗黙の演算子が挟み込まれます. 暗黙の演算子はデフォルトでは :"#apply#" ですから,さきほどの a b は a #apply# b と書いてあるとみなされ,[:"#apply#", "a", "b"] という構文解析 結果が得られます.これは,コンビネータの解釈実行系を作るときなどに 便利です.例えば,

      (S I I) は [:"#apply#", [:"#apply#", "S", "I"], "I"] と
      構文解析されます.

    3. $sop_implicit_op
      式と式の間に挿入される暗黙の演算子が入っています.初期値としては "#apply#" が入っています.この内容を変えることで,挿入される暗黙の演算子を 指定できます.この変数に設定した演算子は $sop_ops でも宣言されているものにして 下さい.

    4. $sop_debug_mode
      この変数の値が true なら構文解析のとき,その過程を表示します. false のときは表示しません.初期値は false です.

    5. $sop_follow
      各型の演算子の直後に許される演算子の型のリストが指定されています. パーサープログラムの誤り修正の目的以外でこれを変更することは あまり無いと思われます.これは,識別子間に挿入される暗黙の演算子が 無いとして設定されています.従って,$sop_implicit_op の値が nil の ときは,このまま使われますが, $sop_implicit_op が nil 以外のときは, 一部の演算子の型に対して,直後に取り得る型が追加されます. 追加される型は,:close, :f, :yf に対してであり,これらの直後に 大域変数 $sop_follow2 に入っている [:f, :fy, :open] が追加されます.

    6. $sop_follow2
      $sop_follow に書いてあるように,演算子無しでつながれた識別子間などに 暗黙の演算子を挿入するモードで,一部の型の演算子の後,取り得るように なる演算子の型のリストが入っています.

    プログラムの中身の簡単な説明

    (時間ができたら説明するかもしれません)

注意事項

  1. このパーサープログラムはコピーして改造して使って結構です.

  2. ただし,プログラムを改造して使用した結果,例えば,製品化するなどで, 私自身にこのプログラムの使用制限がかかるような形態の使用方法は やめてください.

  3. このプログラムはバグがある可能性はあります.万が一,このプログラムの 利用によってなんらかの損害が生じたとしても私はその責任を負いません. ソースファイルが読める程度の小さなプログラムですので,しっかり理解して 使ってください.

  4. ファイルを添え付けると知らぬ間に不正なプログラムを混入されて流通 されないとも限らないので,ここでコピー&ペーストという形で, 常にソースファイルが見えている状態で提供します.

    以上 2019年2月11日 Akihiko Koga

プログラムリスト

次の囲みの中のプログラムを選択してファイルとして セーブして,そのファイルを Ruby のインタープリタ(irb など)に 読み込んでください.私は sop.rb というファイル名を付けています. このプログラムの中にはテスト用の関数 test があります. 次の実行例で使い方が分かると思います.

こちらで使用した Ruby のバージョンは

ruby 2.3.3p222 (2016-11-21 revision 56859) [x64-mingw32]
です.あまり高等な機能は使っていませんので,もう少し前のバージョンでも実行できると 思います.

# Simple Operator Precedence Parser
#     by Akihiko Koga
#     Version 0.83 2019.02.11
$sop_ops = {
  # in_name  => [out_name, priority, op_type]
  :"->"      => ["->", 1000, :xfy],
  :"*"       => ["*",   400, :yfx],
  :"/"       => ["/",   400, :yfx],
  :"+"       => ["+",   500, :yfx],
  :"+/pre"   => ["+",   200, :fy],
  :"-"       => ["-",   500, :yfx],
  :"-/pre"   => ["-",   200, :fy],
  :"="       => ["=",  1500, :xfy],
  :";/post"  => [";",  1800, :yf],
  :";"       => [";",  1800, :yfx],
  :","       => [",",  1400, :xfy],
  :"#apply#" => ["#apply#", 1300, :yfx], # implicit operator
  :"#list#"   => ["#list#", 200, :fy],   # list marker  
  :"#set#"    => ["#set#",  200, :fy],   # set marker
  
  # paren =>
  #  [out_name, priority, paren_type, [pair_paren, ...], valOf(), marker
  :"("       => ["(", 10000, :open,  [:")"], "0",  nil],
  :")"       => [")", 10000, :close, [:"("]],
  :"["       => ["[", 10000, :open,  [:"]"], [], :"#list#"],
  :"]"       => ["]", 10000, :close, [:"["]],
  :"{"       => ["{", 10000, :open,  [:"}"], :"empty", :"#set#"],
  :"}"       => ["}", 10000, :close, [:"{"]],
}

$sop_follow = { # possible tokens that follow each token
  :start => [:f, :fy, :open],
  :open  => [:f, :fy, :open, :close],
  :close => [:yf, :yfx, :xfy, :close], # + $sop_follow2 if implicit_op_mode
  :f     => [:yf, :yfx, :xfy, :close], # same as above
  :yf    => [:yf, :yfx, :xfy, :close], # same as above
  :fy    => [:f, :fy, :open],
  :xfy   => [:f, :fy, :open],
  :yfx   => [:f, :fy, :open],
}
$sop_follow2 = $sop_follow.clone
  $sop_follow2[:close] += [:f, :fy, :open]
  $sop_follow2[:f]     += [:f, :fy, :open]
  $sop_follow2[:yf]    += [:f, :fy, :open]
$sop_implicit_op_mode = true
$sop_implicit_op = :"#apply#"
$sop_debug_mode = false
$sop_no_error_msg = false

def sop_split(str, implicit_op_mode = $sop_implicit_op_mode)
  # strings are replaced by temporary names first
  ops, dic, prefix, i = {}, {}, "###", 0
  str = str.gsub(/"([^"\\]|\\.)*"/) {|u|
    tmp_name = prefix + i.to_s; i += 1
    dic[tmp_name] = u
    " " + tmp_name + " "
  }
  # gather out_names in $sop_ops and assign them temporary names seperated
  # by space, split to tokens, rename temprary names to original names again
  $sop_ops.sort{|a,b| b[1][0].length <=> a[1][0].length}.each {|op|
    # op ::= [in_name, [out_name, ...]]
    out_name = op[1][0]
    if ops[out_name] == nil then
      tmp_name = prefix + i.to_s; i += 1
      dic[tmp_name] = out_name
      ops[out_name] = []
      str = str.gsub(out_name, " " + tmp_name + " ")
    end
    ops[out_name].push(op)
  }
  tlist = str.split(" ").map {|x| if dic[x] then dic[x] else x end}
  
  # decide op_type and replace out_name by in_name
  tlist2, prev, n = [], :start, tlist.length
  n.times{|i|
    x = tlist[i]
    oplist = ops[x] # ::= nil | [[in_name, [out_name, priority, op_type]], ...]
    if oplist == nil then
      in_name, type = x, :f
    else
      if i == n-1 then fols = [:close]
      elsif ops[tlist[i+1]] == nil then fols = [:f]
      else fols = ops[tlist[i+1]].map {|u| u[1][2]}  end
      
      op2 = sop_choose_op(oplist, prev, fols, $sop_follow)
      if op2 == nil && implicit_op_mode then
        op2 = sop_choose_op(oplist, prev, fols, $sop_follow2)
      end
      if op2 == nil then sop_error_at(tlist, i, "***SyntaxError1***") end
      in_name, type = op2[0], op2[1][2]
    end
    if [:close, :yf, :f].index(prev) && [:open, :fy, :f].index(type) then
      if implicit_op_mode then
        tlist2.push($sop_implicit_op)
      else
        sop_error_at(tlist, i, "***BinaryOpRequiredBeforeThis***")
      end
    end
    prev = type
    tlist2.push(in_name)
  }
  tlist2
end

def sop_choose_op(oplist, prev, fols, follow)
  oplist.each {|op| # [in_name, [out_name, priority, op_type]]
    op_type = op[1][2]
    if follow[prev].index(op_type) && (follow[op_type] & fols) != [] then
      return op
    end
  }
  return nil
end

# parser

def sop_parse(str, implicit_op_mode = $sop_implicit_op_mode)
  begin
    sop_parse2([:"("] + sop_split(str, implicit_op_mode) + [:")"])
  rescue
    :error
  end
end

def sop_parse2(tlist)
  if $sop_debug_mode then printf("token_list= %s\n", tlist.to_s) end
  arg_stack, op_stack = [], []
  tlist.length.times{|i|
    x = tlist[i]
    if $sop_debug_mode then
      printf("args: %s\nops: %s\ntoken: %s\n----\n", arg_stack, op_stack, x)
    end
    op_data = $sop_ops[x]          # [in_name, priority, type, ...]
    if op_data == nil || op_data[2] == :f then  # identifier
      arg_stack.unshift(x)
    elsif op_data[2] == :open then # open parenthesis
      arg_stack.unshift(x)
      op_stack.unshift(x)
    else                           # operator or close parenthesis
      while x != nil && x != :error && sop_op_less(op_stack[0], x) do
        arg_stack, op_stack, x = sop_reduce(arg_stack, op_stack, x)
      end
      if x == :error then
        sop_error_at(tlist, i, "***SyntaxError2***")
      elsif x != nil then
        arg_stack.unshift(x)
        op_stack.unshift(x)
      end
    end
  }
  if arg_stack.length != 1 then
    sop_error_at(tlist, tlist.length-1, "***ExpNotCompleted***")
  end
  return arg_stack[0]
end

def sop_op_less(op1, op2)
  p1, t1 = $sop_ops[op1][1], $sop_ops[op1][2]
  p2, t2 = $sop_ops[op2][1], $sop_ops[op2][2]
  return t2 == :close ||
         (t2 != :open &&
          ((p1 < p2) || ((p1 == p2) && [:yf, :yfx].index(t2))))
end

def sop_error_at(tlist, i, msg)
  if !$sop_no_error_msg then
    p (i > 0?tlist[0..i-1]:[]) + [[msg, tlist[i]]] + tlist[i+1..-1]
  end
  raise msg
end

def sop_reduce(arg_stack, op_stack, op)
  last_op = sop_shift(op_stack)
  inf = $sop_ops[last_op] # [out_name, priority, op_type]
  type = inf[2]
  if type == :fy then
    arg_stack[1] = [last_op, arg_stack[0]]
    sop_shift(arg_stack);
  elsif type == :yf then
    arg_stack[1] = [last_op, arg_stack[1]]
    sop_shift(arg_stack);
  elsif type == :xfy || type == :yfx then # binary operator
    arg_stack[2] = [last_op, arg_stack[2], arg_stack[0]]
    sop_shift(arg_stack); sop_shift(arg_stack);
  elsif type == :open && inf[3].index(op) then
    # open paren and op is its close paren
    if arg_stack[0] == last_op then # form of (), []
      arg_stack[0] = inf[4]
    else
      arg_stack[1] = arg_stack[0]
      sop_shift(arg_stack)
      if inf[5] != nil then arg_stack[0] = [inf[5], arg_stack[0]] end
    end
    op = nil
  else
    return arg_stack, op_stack, :error
  end
  return arg_stack, op_stack, op
end

def sop_shift(x)
  if x == []  then raise "***** shift of []" else x.shift end
end

def sop_print(code, nl = true)
  sop_prin2(code)
  if nl then printf("\n") end
end

def sop_prin2(code, priority = 100000)
  if code.class != Array then printf("%s", code.to_s)
  elsif code == [] then printf("[]")
  else
    op = $sop_ops[code[0]] # [out_name, priority, op_type]
    if op == nil then printf("%s", code.to_s); return; end
    if op[1] > priority then printf("(") end
    if [:fy].index(op[2]) then
      printf("%s", op[3]?op[3]:(op[0]))
      sop_prin2(code[1], op[1])
    elsif [:yf].index(op[2]) then
      sop_prin2(code[1], op[1])
      printf("%s", op[3]?op[3]:(op[0]))
    elsif [:xfy, :yfx].index(op[2]) then
      if op[2] == :xfy then d1,d2 = 1,0 else d1,d2 = 0,1 end
      sop_prin2(code[1], op[1]-d1)
      printf("%s", ((code[0]==$sop_implicit_op) ? " " : (op[3]?op[3]:(op[0]))))
      sop_prin2(code[2], op[1]-d2)
    end
    if op[1] > priority then printf(")") end
  end
end

def test
  printf("Welcome to SopTest\n  :q for quit\n  :d for toggling debug mode\n")
  printf("  :i for toggling implicit op mode\n  Otherwise, parsed and printed\n")
  while true
    printf("input> ")
    $input = readline.strip
    if $input == ":q"
      break
    elsif $input == ":d" then
      $sop_debug_mode = !$sop_debug_mode
      printf("debug mode = %s\n", $sop_debug_mode)
    elsif $input == ":i" then
      $sop_implicit_op_mode = !$sop_implicit_op_mode
      printf("implicit op mode = %s\n", $sop_implicit_op_mode)
    else
      $output = sop_parse($input)
      printf("  %s\n", $output.to_s)
      printf("  print-form = "); sop_print($output)
    end
  end
end

実行例

次の実行例は,上のプログラムを"sob.rb" という名前をファイルにセーブして 実行したものです.test という関数が入っているので,これを動かすと, すでに定義されている演算子で何が解析できるかを確認できます.

test はコマンドとして,

  :q ... test から抜ける
  :i ... 暗黙の演算子モードのON/OFFを切り替える.最初は ON
  :d ... デバッグモードの ON/OFFを切り替える.ON だと,構文解析の
         様子が多少表示される.最初は OFF
の3つだけを持ち,他の入力は式として構文解析され,その結果が表示されます.

c:\0-ruby\sop>irb
irb(main):001:0> load "sop.rb"
=> true
irb(main):006:0> test
Welcome to SopTest
  :q for quit
  :d for toggling debug mode
  :i for toggling implicit op mode
  Otherwise, parsed and printed
コマンドとしては :q, :d, :i が可能で,ほかは全部構文解析されて結果が表示されます.

input> a*b-c/d
  [:-, [:*, "a", "b"], [:/, "c", "d"]]
  print-form = a*b-c/d
 a*b-c/d の構文解析の結果とそれを式として表示したところです.構文解析結果の先頭の :- は,単に - というシンボルで,:"-" と一緒です.Ruby のプリントはRubyの表示上問題ないときは"を付けないみたいですね.

input> A->B->C->D
  [:"->", "A", [:"->", "B", [:"->", "C", "D"]]]
  print-form = A->B->C->D
input> A->(B->C)->D
  [:"->", "A", [:"->", [:"->", "B", "C"], "D"]]
  print-form = A->(B->C)->D
演算子 -> は :xfy の二項演算子として定義されていますので,何も括弧を指定しないと右側から括弧がついて構文解釈されますが,明示的に括弧を使うと,そこが先に構文解析されます.

input> (f x y) + (g x)
  [:+, [:"#apply#", [:"#apply#", "f", "x"], "y"], [:"#apply#", "g", "x"]]
  print-form = (f x y)+(g x)
これは暗黙の演算子の例です.(f x y) は演算子で結ばれていないので,演算子文法としては間違った書き方なのですが, f と x の間と x と y の間に関数適用の演算子 "#apply#" があるとみなして構文解析します."#apply#" は :yfx の演算子として定義していますので,f を x に適用した結果の (f x) が何らかの関数と見て,それを y に適用するという意味の構文解析結果になっています.

input> :i
implicit op mode = false
暗黙の演算子モードを解除しました(:i ごとに ON/OFF が切り替わる).

input> (f x y)+(g x)
["(", "f", ["***BinaryOpRequiredBeforeThis***", "x"], "y", ")", "+", "(", "g", "x", ")"]
  error
  print-form = error
直前に構文解析できていた式が構文エラーになります.エラーメッセージはあまり親切ではありません.

input> :d
debug mode = true
デバッグモードをONにしました.こちらも ON/OFF の切り替えです.以下,最初に,入力がどのようなトークン列に分解されたかが示され,その後は1トークンごとの解析過程が示されます.入力の終わりや閉じ括弧はかなり沢山の還元(reduction)が行われるため,もしかしたらソースプログラムに手を入れて,もう少し詳細に見せても良いかもしれません.

input> a*b+c*d
token_list= [:"(", "a", :*, "b", :+, "c", :*, "d", :")"]
args: []
ops: []
token: (
----
args: [:"("]
ops: [:"("]
token: a
----
args: ["a", :"("]
ops: [:"("]
token: *
----
args: [:*, "a", :"("]
ops: [:*, :"("]
token: b
----
args: ["b", :*, "a", :"("]
ops: [:*, :"("]
token: +
次のトークンが「+」で」一つ前のトークン「*」より優先度が低いので次で「*」の方がまとめられます.

----
args: [:+, [:*, "a", "b"], :"("]
ops: [:+, :"("]
token: c
はい,まとめられました.

----
args: ["c", :+, [:*, "a", "b"], :"("]
ops: [:+, :"("]
token: *
----
args: [:*, "c", :+, [:*, "a", "b"], :"("]
ops: [:*, :+, :"("]
token: d
----
args: ["d", :*, "c", :+, [:*, "a", "b"], :"("]
ops: [:*, :+, :"("]
token: )
入力がすべて終わった(次のトークンがすべての式を閉じる「)」)なのですべての演算子がまとめられます.
----
  [:+, [:*, "a", "b"], [:*, "c", "d"]]
  print-form = a*b+c*d

次は暗黙の演算子モードに戻して,デバッグモードで実行してみます
input> :i
implicit op mode = true
input> f x+y
token_list= [:"(", "f", :"#apply#", "x", :+, "y", :")"]
は,"#aply#" が入力に挿入されていることがわかりますね.

args: []
ops: []
token: (
----
args: [:"("]
ops: [:"("]
token: f
----
args: ["f", :"("]
ops: [:"("]
token: #apply#
----
args: [:"#apply#", "f", :"("]
ops: [:"#apply#", :"("]
token: x
----
args: ["x", :"#apply#", "f", :"("]
ops: [:"#apply#", :"("]
token: +
----
args: [:+, "x", :"#apply#", "f", :"("]
ops: [:+, :"#apply#", :"("]
token: y
----
args: ["y", :+, "x", :"#apply#", "f", :"("]
ops: [:+, :"#apply#", :"("]
token: )
----
  [:"#apply#", "f", [:+, "x", "y"]]
  print-form = f x+y
input> :d
debug mode = false

次はリストの解析例を示してこの実行例を終わります.
input> [a,b,c]
  [:"#list#", [:",", "a", [:",", "b", "c"]]]
  print-form = #list#(a,b,c)
input> [a, b+1, a->c*d]
  [:"#list#", [:",", "a", [:",", [:+, "b", "1"], [:"->", "a", [:*, "c", "d"]]]]]
  print-form = #list#(a,b+1,a->c*d)
input> :q
=> nil
irb(main):007:0>

変更履歴

上が最近です.

  1. 2019年 2月 11日(月)
    ver. 0.83 2019.02.11 版を公開

参考文献

    一般的な構文解析の知識(特に演算子優先順位文法のことが書いてある本)

    ある程度の分量がある大抵のコンパイラの本には演算子順位法は出ていると思いますが, あまり具体的な本を知らないので,とりあえずは, 中田育男先生と渡邊坦先生の本を紹介しておきます.

  1. 中田 育男:コンパイラ (コンピューターサイエンス・ライブラリー) , 産業図書 (1981/1/1), 278ページ
    これは私が持っているコンパイラの本なのですが,もう,かなり昔の本になってしまいました.

  2. 中田 育男:コンパイラの構成と最適化, 朝倉書店; 第2版 (2009/11/1), 601ページ
    こちらはかなり分厚くて,私は買っていませんが,私が住んでいる市の図書館に あったので時々借りています.私が某会社にいたときの知り合いの話では 他の本ではあまり扱っていない最適化をきちんと扱っているので,ときどき参照して いるとのことでした.

    あと,某筋の情報によると,中田先生の本では,次の本が評判が良いらしいです.

  3. 中田 育男:コンパイラ (新コンピュータサイエンス講座), オーム社 (1995/6/1), 193ページ

  4. 渡邊坦:コンパイラの仕組み, 朝倉書店, 1998年04月01日, 196ページ
    第4章が「演算子順位による構文解析」ですね.ただ,この本は後の LL(1) 文法の 方がメインのようです.Tiny C という言語のコンパイラを実際に作って学ぶ スタイルのようです.

    その他にも構文解析やコンパイラの本は世の中に沢山ありますから,探して 自分に合いそうな本を見つけてください.私の本だなや近くの図書館には, 演算子順位法の載っている本(で,かつ,今でも絶版になってない本 :-))としては, 次の本がありました.

  5. 宮本街市 : はじめてのコンパイラ 原理と実践, 森北出版株式会社, 2007

    
    

    本格的なコンパイラを 作る手法としては主流ではありませんので,中には省略している本もあります. このページでは構文解析やコンパイラ作成がメインの目的ではなく,ちょっとした 言語を簡単に導入して,計算機科学の実験をすることがメインの目的なので 演算子順位法を使いました.


    
    

    Prolog の演算子優先順位パーサーについての情報

    ここで作成したパーサは演算子の右結合や左結合をxfy, yfx という記号で 表現していました.これは DEC-10 Prolog などに組み込んである演算子順位 パーサの流儀です.

  6. Prolog マニュアル
    特に本やサイトを特定することはできないのですが,DEC-10 系統の Prolog は op(precedence, type, symbol_list) という述語で演算子の優先度と型を定義します. したがって,Prolog の詳しい本や特にマニュアルには,この記述方法と意味が 書かれているはずです.これを書いている時点(2019年2月8日)で,SWI-Prolog という Prolog の処理系が Simplified BSD license で配布されていますので, 例えば,SWI-Prolog, xfy, op くらいのキーワードで 検索してみると SWI-Prolog のマニュアルが見つかると思います.あるいは,検索 のキーワードの最後に PDF をつけると,PDF 形式のマニュアルが見つかりやすくなりますし,もう少し,Prolog の種類を増やそうと思えば,SWI- をとるとかやってみるとよいでしょう.

  7. 笹川賢一 : Prolog処理系を作ろう Kindle版, 出版社: 笹川賢一; 2版 (2016/10/23)
    これは著者がいろいろ試行錯誤しながら Prolog の処理系を作った話だそうです. 上のタイトルはちょっと変な書き方ですが,これは紙の本が一度絶版になって,いろいろな要望があったので Kindle 版として最低価格で販売することにしたとのこと. Prolog の C コードは Github から 利用可能とのこと.著者名とタイトルで google などで検索してみてください. ソースコードなどの情報が見つかると思います.この著者は Kindle から, 他にも「やさしいLispの作り方: C言語で作るミニミニLisp処理系」とか出してますね.

計算機(主にソフトウェア)の話題 へ

圏論を勉強しよう へ
束論を勉強しよう へ
半群論を勉強しよう へ
ホームページトップ(Top of My Homepage)