【C】プリプロセッサのマクロ展開アルゴリズム

2022-09-18
#compiler #c

C言語のプリプロセッサを自作して簡単なマクロは扱えていたが、 いろいろなソースを食わせてみたところうまく展開できないケースがあったので修正した。

前置き

マクロ定義で自分を含む再帰的な定義をしてしまうと、展開が無限に続いてしまう可能性がある：

#define RECUR(x)  RECUR(x-1)

マクロ展開は単純な文字列置換で行われるので、終了条件で回避することができない。 なのでそういうことが起こらないように、一段階しか展開されないようになっている：

RECUR(123)  // => RECUR(123-1)

という程度の理解だったので、「ふむふむ展開中はそのマクロ名は無効にしてやればよいのね」という具合で実装していた。

うまく展開できなかったケース

なんかのソースでうまく展開できないのを掘っていったところ、次のようなケースに問題があった：

#define F(x) CHECK(G(x))
#define G(x) CHECK(H(x))
#define CHECK(x) x
F(987)

関数風マクロで実装されたAPIがチェックをかましつつ他の関数風マクロAPIを呼び出してて、そちらでもチェックが入る、というような構成。

マクロ展開を関数呼び出しと同じように考えると、 Fの展開でCHECKの展開が呼び出され、さらにGの展開が呼び出されCHECK(H(x))となるが、CHECKは展開中だからここでストップ、 で結果はCHECK(H(987))となっていた。

が実際にはどちらも展開されてH(987)となるのが期待される動作のようだった。

アルゴリズム

うまく展開するアルゴリズムは自分で考えてもわからなかったのでググったところ、 C++でCプリプロセッサを作ったり速くしたりしたお話 のスライドに示されていたサイト、 blog dds: 2006-06-26 — Dave Prosser’s C Preprocessing Algorithm から辿れるpdfに書かれていた。

主に expand と subst の２関数：

expand(TS) /* recur, substitute, pushback, rescan */
{
    if TS is {} then
        return {};
    else if TS is T^HS • TS’ and T is in HS then
        return T^HS • expand(TS’);
    else if TS is T^HS • TS’ and T is a "()-less macro" then
        return expand(subst(ts(T), {}, {}, HS ∪ {T}, {}) • TS’);
    else if TS is T^HS • ( • TS’ and T is a "()’d macro" then
        check TS’ is actuals • )^HS’ • TS’’ and actuals are "correct for T"
          return expand(subst(ts(T), fp(T), actuals, (HS∩HS’)∪{T}, {})•TS’’);

    note TS must be T^HS • TS’
    return THS • expand(TS’ );
}

subst(IS,FP,AP,HS,OS) /* substitute args, handle stringize and paste */
{
    if IS is {} then
        return hsadd(HS, OS);
    else if IS is # • T • IS’ and T is FP[i] then
        return subst(IS’, FP, AP, HS, OS • stringize(select(i, AP)));
    else if IS is ## • T • IS’ and T is FP[i] then
    {
        if select(i, AP) is {} then /* only if actuals can be empty */
            return subst(IS’, FP, AP, HS, OS);
        else
            return subst(IS’, FP, AP, HS, glue(OS, select(i, AP)));
    }
    else if IS is ## • T^HS’ • IS’ then
        return subst(IS’, FP, AP, HS, glue(OS, T^HS’));
    else if IS is T • ##^HS’ • IS’ and T is FP[i] then
    {
        if select(i, AP) is {} then /* only if actuals can be empty */
        {
            if IS’ is T’ • IS’’ and T’ is FP[j] then
                return subst(IS’’, FP, AP, HS, OS • select(j, AP));
            else
                return subst(IS’, FP, AP, HS, OS);
        } else
            return subst(##^HS’ • IS’, FP, AP, HS, OS • select(i, AP));
    }
    else if IS is T • IS’ and T is FP[i] then
        return subst(IS’, FP, AP, HS, OS • expand(select(i, AP)));

    note IS must be T^HS’ • IS’
    return subst(IS’, FP, AP, HS, OS • T^HS’);
}
  • TSがトークン列、Tがトークンを表し、マクロ展開はトークン単位で行われる
  • HSがhidesetを表し、展開しない語彙セットをトークンごとに持つ
  • subst はマクロ引数の置換を行う
    • IS: 入力列
    • FP: マクロのパラメータ (Formal Parameter)
    • AP: マクロに与えられた実引数 (Actual Parameter)
    • HS: HideSet
    • OS: 出力列
  • hsadd で出力列の各トークンにhidesetを追加する

再帰による実装なので追いづらいんだけど、expand でトークン列を順に見ていき、 マッチしたマクロ名に対しての subst 呼び出しで IS をマクロボディ、 OS を空で与えるので、 マクロで一段展開されたトークン列にそのマクロ名自体がhidesetとして追加されるという動作っぽい。

subst 内での引数置き換え時に、hidesetを指定しない状態で引数だけを先に expand で展開するので、 引数自体はそのマクロを含んでいても展開される、ということっぽい。

引数付きマクロの場合に、閉じ括弧のhidesetと積をとっているのはなんだろう…よく理解してない、 これがないと無限ループが発生してしまうのかもしれない。

資料では他に ## の連結や # の文字列化などについても書かれている。

実装、ループ化

上記のアルゴリズムは再帰呼び出しで副作用なしなので簡潔ではあるけど、そのまま実装すると再起呼び出しとシーケンス連結のコストがかかってしまう。 ループ・副作用あり（配列要素書き換え）にできるにこしたことはない、と思っていじくったところ問題なく動くっぽい。

  • hidesetはすべてのトークンには必要なく、マクロ名である可能性がある識別子と、閉じ括弧のみでよい
  • マクロボディや引数のトークンは、展開や置換で複数回使用されることになるので、それぞれでhidesetが別になるよう複製する必要がある？

JavaScriptで実装してみた： https://github.com/tyfkda/xcc/blob/main/tool/pp.js

参考

関連記事

新着記事