優先順位を自由定義できる中置演算子の実装方法を考えるmemo

Haskellとかでやってる中値演算子の結合や優先度をコード内で指定できるような、自分の言語を作るための実装について考えてみる。

たぶん、中値演算子は構文的に区別できるので、パーズ時には優先度や結合度関係なしに式の単調の二項演算子ツリーをつくる。そして評価時には、まず演算子の優先度データベースをつくり、それを元に式ツリーをたどるパーザーを作って、その中で評価させるんだろう。

BNF的には

exp = infixexp
infixexp = uniexp infix infixexp
         | uniexp
uniexp = "(" exp ")"
       | num
infix = <infix pattern>
num = <num pattern>

この構文だと、中値演算は単調に並べられる

(e i (e i (...(e i e)...)))

これから、infix優先度マップを元に優先順に評価したい

(1 * (2 + (3 * (4)))) => (1*2)+(3*4)

実装するのは難しそう。

追記

Haskellはそうだったと思いますけど（詳しくない）、Cleanは、syntax的には関数と演算子の区別がつかないのですよ。

Concurrent Clean : 中置演算子とsyntax - lethevert is a programmer

Haskellでは演算子と変数、リテラルはトークンレベルで区別できます。Cleanはwhere句もあるのにinfixは識別子＋αの文字が使えるんですね。

それを踏まえて考えたら、評価時に前方の式部分をパーザー風に処理しいていくのであれば、最初の構文解析時にパーズさえできれば、二項演算子で構造化してなくても、結局はあまり変わらないのかな、とも思いました。

exp = semiexp
semiexp = uniexp semiexp 
         | uniexp
uniexp = "(" exp ")"
       | symbol
       | num
symbol = <identifier pattern>
num = <num pattern>

スクリプト言語のような、式と定義が混ざった言語に応用するばあいどんな風にできるだろうか。