自作コンパイラで演算子の優先順位をつけた

自作コンパイラでC言語の演算子に優先順位をつけました。

これの続き

natsutan.hatenablog.com

低レイヤを知りたい人のためのCコンパイラ作成入門には詳しい説明がなく、テキストの範囲ではバイナリオペレータに優先順位はほとんどついてないと思います。足し算よりかけ算優先くらい。 手持ちの教科書にあんまり詳しく載っていないのは、足し算とかけ算の優先順位付けられるなら後は分かるでしょって事だと思う。

2023/03/18追記 すいません。理解してから低レイヤを知りたい人のためのCコンパイラ作成入門を見たら、ちゃんと優先順位ついてました。論理AND等が無いこととごっちゃになってました。

自作コンパイラで優先順位がつくようになったでまとめました。

そもそも優先順位をどうつけているか

かけ算と足し算の優先順位付けは、この文法から来ています。

expr : term { + term }
term : factor { * factor }
factor : ID | '(' expr ')'

一般的にk個の優先順位をつけるためには、非終端のルールがk+1個必要になります。かけ算と足し算で2つの優先順位があるので、非終端の文法が3つ必要になります。

C言語の演算子

Retargetable C Compilerに実装方法が載ってました。

www.amazon.com

C言語の演算子の優先順位は15段階になっています。 パース関数については後述。優先順位は値が大きい方（表の下）が優先順位が高い。

優先順位	結合	演算子	パース関数
1	左	,	expr
2	右	= += -= *= /= %= &= ^= |= <<= >>=	expr1
3	右	?:	expr2
4	左	||	expr3
5	左	&&	expr3
6	左	|	expr3
7	左	^	expr3
8	左	&	expr3
9	左	== !=	expr3
10	左	< > <= >=	expr3
11	左	<< >>	expr3
12	左	+ -	expr3
13	左	* / %	expr3
14		* & - + ! ~ ++ -- sizeof (type-cast)	unary
15		++ --	postfix

今、バイナリオペレータの優先順位をつけたいので、優先順位4から13までを処理したい。 ざっくりというと、優先順位が15レベルあれば文法を16個作れば優先順位をつけてパースできる理屈になります。

優先順位の数だけ関数を作っても良いけど、ほとんど同じ内容の関数がたくさん出てきて面倒だよねということで、Retargetable C Compilerにでてくるパーサは優先順位4から13までを、expr3という一つの関数で捌いています。

LCCの実装

Retargetable C Compilerに出てくるLCCの実装はこうなっています。 exprで再帰するときに優先順位を渡して、その優先順位を使って一つの関数でパースしています。

void expr(int k) {
 if (k > 13) 
     factor();
  else {
    expr(k+1);
    while(prec[t] == k) {
      t - gettok();
      expr(k + 1);
  }
}

precが優先順位のテーブルになっていて、prec['+']だと12を返します。

なるほど、わからない。

実装してみた

F#でwhileを使うのが苦手なので、愚直に文法増やして対応しました。 こんな感じです。

 expr = logicaland { || logicaland　}
 logicaland = bitwiseor { && bitwiseor　}
 bitwiseor = bitwisexor { | bitwisexor　}
 bitwisexor = bitwiseand { ^ bitwiseand　}
 bitwiseand = equality { & equality　}
 equality = relational { == relational　}
            relational { != relational }
 relational = shifting { < shifting　}
              shifting { > shifting }
              shifting { >= shifting }
              shifting { <= shifting }
 shifting = additive { << additive　}
            additive { >> additive }
 （省略）
 factor = num
        | ( expr )

ソースのコピペ連発でしたが、低レイヤを知りたい人のためのCコンパイラ作成入門の経験から、ここは一度作ればあとから直したくなることがないと判断しました。まずは動く物を作ろう。

こうやって文法を足した結果、こういう計算がgccの結果と一致するようになりました。

int main(void) {
  putd(15 << 2 == 15 >> 2);
  return 0;
}

次は変数とアサインの実装。

ソースはここ

github.com