Zenn
🐡

C言語の型宣言をPEG.jsパーサで構文解析する

2022/12/25に公開
C言語
#
peg
tech

C言語の型宣言の構文はわかりにくい

C言語の型宣言の構文はわかりにくいと言われます。
この理由は、C言語では型の修飾が前後に連なっていくからです。
int* a;
この場合、aを修飾する型のタイプである*やintは、aの前に前置されます。
int a[];
この場合、配列であるという意味の修飾である[]は、それを修飾する対象であるaの後に後置されます。
[]の後置としての結合優先度は前置の*よりも高いので、
int* a[];
は
int* (a[]);
と解釈されます。「int型へのポインタの配列」です。これに対して、
int(* a)[];
のように括弧をつけて結合を変えてやると、これは「int配列へのポインタ」になります。

このような「前置か」「後置か」が優先度前提で、括弧で優先度を制御しながら次々とあられてくるので、解釈順序は右往左往することになります。また、上でわかるようにCの宣言は「左から右」でもなく、もちろん右から左でもなく、「内側から外側に」解釈しなければなりません。この特性が人間にとっての「難しさ」に繋がっています。「内側から外側に」というのは、具体的には最初になんとかして起点を探し「括弧がない限り後置修飾(関数引数の丸括弧や配列宣言の大括弧)右へ」を、後置修飾がなくなるまで探し、解釈できなくなったら左へ、と探していきます。慣れないとやっかいなものです。

ならば練習だ

Cの厄介なルールを体感で理解するために、PEG.jsでパーサを書いてみました。簡単に実行するには、以下をPEG.jsのブラウザオンラインバージョンの左に貼り付けてください。

START
  = _ typeDecl:TypeDecl _ ';' _ {
    return typeDecl()
  }

TypeDecl
  = preModifier:PreModifier _ typeDecl:TypeDecl {
    return (leaf) => typeDecl(preModifier(leaf))
  }
  / preModifier:PreModifier {
    return preModifier
  }
  / typeTerm:TypeTerm {
    return typeTerm
  }

TypeTerm
  = typeFactor:TypeFactor _ postModifiers:PostModifiers {
    return (leaf) => typeFactor(postModifiers(leaf))
  }
  / postModifiers:PostModifiers {
    return postModifiers;
  }
  / typeFactor:TypeFactor {
	return typeFactor
  }

TypeFactor
  = variable:Variable {
    return (leaf) => ({
      "name": variable,
      "type": leaf,
    })
  }
  / '(' _ typeDecl:TypeDecl _ ')' {
    return typeDecl
  }

PostModifiers
  = postModifier:PostModifier _ postModifiers:PostModifiers {
    return (leaf) => postModifier(postModifiers(leaf))
  }
  / postModifier:PostModifier {
    return (leaf) => postModifier(leaf)
  }

PreModifier
  = primType:PremitiveType {
    return () => primType
  }
  / '*' {
    return (leaf) => ({
      "name": "pointer",
      "to": leaf,
    })
  }

PostModifier
  = '[' _ ']' {
    return (leaf) => ({
      "name": "array",
      "element": leaf
    })
  }
  / '(' _ params:Params _ ')' {
    return (leaf) => ({
      "name": "function",
      "params": params,
      "returns": leaf
    })
  }

Params
  = typeDecl:TypeDecl _ ',' _ params:Params { return [typeDecl(), ...params] }
  / typeDecl:TypeDecl { return [typeDecl()] }
  / 'void' { [] }
  / '' { [] }

Variable
  = Identifier

PremitiveType
  = "int" { return {"primtype": text() } }
  / "char" { return {"primtype": text() } }
  / "double" { return {"primtype": text() } }
  / "float" { return {"primtype": text() } }
  / "void" { return {"primtype": text() } }

Identifier
  = [a-zA-Z_][a-zA-Z_0-9]* { return text() }

_ "whitespace"
  = [ \t\n\r]*

するとPEGパーサが生成されますので、

のように右側にC言語の宣言ぽいものを入れてください。

実行例

void (*signal(int sig, void (*func)(int)))(int); 

を入力すると以下のように解釈されます。

    { 
       "name": "signal", 
       "type": { 
          "name": "function", 
          "params": [ 
             { 
                "name": "sig", 
                "type": { 
                   "primtype": "int" 
                } 
             }, 
             { 
                "name": "func", 
                "type": { 
                   "name": "pointer", 
                   "to": { 
                      "name": "function", 
                      "params": [ 
                         { 
                            "primtype": "int" 
                         } 
                      ], 
                      "returns": { 
                         "primtype": "void" 
                      } 
                   } 
                } 
             } 
          ], 
          "returns": { 
             "name": "pointer", 
             "to": { 
                "name": "function", 
                "params": [ 
                   { 
                      "primtype": "int" 
                   } 
                ], 
                "returns": { 
                   "primtype": "void" 
                } 
             } 
          } 
       } 
    }

制限

フルセットではもちろんないので以下に気をつけて。

  • 基本型はint,char,double,float,voidのみ
  • 修飾はポインタ型と配列型と関数型がある
  • typedefはない
  • constやregisterやstaticやshotやlongなどの修飾はない
  • structやunionはない。bit fieldもない。
    他、多くがない。

PEG.jsで気づいたこと

左再帰ができない

TypeDecl
  = _ PreModifier _ TypeDecl        // これは書ける
  / _ TypeDecl _ PostModifier        // これは左再帰になるので書けないん

これは原理的にしょうがありません。再帰下降構文解析でも同じことがおきます。上記のパーサではPostModifiersを導入して再帰による繰り返しをつかって文法上は回避し、その上で構文木を無名関数で遅延評価させながら構築していきます。
PEG実装でもいろいろあって、工夫して左再帰もできる処理系もあるそうですが、PEG.jsではできません。

型がつかない

TypeScript対応ってあるのかしら。

lexerが無いのが良い

(PEG.jsに限らずPEGパーサ一般に)パーサコンビネータもそうだけどトークナイザーが不要。これはいいね。

Discussion