これでわかるC言語の宣言解読法！！（右端導出を用いた方法です）

# はじめに

初めまして、私はくまさんです。ただいま、独学で[Cコンパイラ](https://github.com/wo4mei3/wcc)を作成しています。関数型言語は格好良く感じるという理由で使用言語はOCamlを選んでいます。まだまだ必要な作業は一杯でもうすでに心が折れかけていますが、最後までやり遂げたいと思います。

さて、今回はC言語の宣言の読み方について解説したいと思います。
この記事を読むにあたって、あったら望ましい知識はBNF記法と右端導出の2点だけですが、これらは後々順を追って解説して行くので、まったく知らなくても大丈夫です。

この記事を読めば、よく巷のドキュメントで紹介されているような優先順位なる概念云々を挟むことなしに、右端導出といった統一的で理論的な方法論で、どんな複雑な宣言も、機械的に読み解いていくことができるようになります。

ただし、C言語のdeclaration、とくに、declaratorとdirect-declaratorあたりの構文規則を頭に馴染ませる必要は少なからずあります。

ただ、構文規則自体は単純なのですぐに馴染むことはできると思います。

C言語の構文規則のリファレンスとして、よく引き合いに出されるものに、通称『K&R C』というCプログラマにとってのバイブル的な書物に付録としてついているものがありますが、この記事で扱う構文規則は説明の都合のため、それの一部改変したものを扱います。

# BNF記法と右端導出
（補足:この章は以下の記事を参考にして書いています。こっちの方がわかりやすいと思います。）
https://ja.wikipedia.org/wiki/バッカス・ナウア記法
https://ja.wikipedia.org/wiki/文脈自由文法#導出と構文木

BNF記法とはプログラミング言語などの形式言語の文法を定義するために使われる記法のことで、左辺に非終端記号（<>で囲まれている記号）、右辺に複数の記号（終端記号、非終端記号どちらも含む）でできた構文規則が複数集まったもので構成されます。

例えば二進数のBNF記法は以下のようにして定義されます。
```
(1) <bin_num> ::= <bin_seq>
(2) <bin_seq> ::= <bin_digit>
(3) <bin_seq> ::= <bin_digit> <bin_seq>
(4) <bin_digit> ::= 0
(5) <bin_digit> ::= 1
```

任意の二進数の数字は、(1)~(5)までの各構文規則の左辺の非終端記号を右辺の記号列に置き換えていくことで得ることができます。開始記号\<bin_num>から置き換えをスタートして、最終的に終端記号0,1の記号列になるまで置き換えが完了したらゴールです。

例えば、二進数の101は、以下のようにして得られます。
```
<bin_num> 
-> <bin_seq>  #(1)を適用
-> <bin_digit> <bin_seq>  #(3)を適用
-> 1 <bin_seq>  #(5)を適用
-> 1 <bin_digit> <bin_seq>  #(3)を適用
-> 1 0 <bin_seq>  #(4)を適用
-> 1 0 <bin_digit>  #(2)を適用
-> 1 0 1  #(5)を適用
```
以上のように、開始記号と呼ばれる非終端記号に構文規則を適用していって任意の表現を得ることを導出と言います。

導出には2通りの戦略があります。ひとつは、先ほど行った、左端の非終端記号から順に構文規則を適用して記号を置き換えていく左端導出と、それとは逆に、右端の非終端記号から順に構文規則を適用していく右端導出の2つです。

今度は右端導出で二進数の101を得る方法を見てみましょう。
```
<bin_num>
-> <bin_seq>  #(1)を適用
-> <bin_digit> <binseq>  #(3)を適用
-> <bin_digit> <bin_digit> <bin_seq>  #(3)を適用
-> <bin_digit> <bin_digit> <bin_digit>  #(2)を適用
-> <bin_digit> <bin_digit> 1  #(5)を適用
-> <bin_digit> 0 1  #(4)を適用
-> 1 0 1  #(5)を適用
```
無事得られましたね！！

この記事では、この後者の右端導出を用いてC言語の宣言を導出していきたいと思います。


# C言語の宣言部分の文法
さて、実際のC言語の宣言部分のBNF定義がどうなっているのかみてみましょう。
以下のようになっています。
```
(1) <declaration> ::= <declaration-specifier-list> <declarator>

(2) <declaration-specifier-list> ::= <declaration-specifier>
(3) <declaration-specifier-list> ::= <declaration-specifier-list> <declaration-specifier>
(4) <declaration-specifier> ::= <identifier>


(5) <declarator> ::= * <declarator>
(6) <declarator> ::= * const <declarator>
(7) <declarator> ::= <direct-declarator>

(8) <direct-declarator> ::= <identifier>
(9) <direct-declarator> ::= ( <declarator> )
(10) <direct-declarator> ::=  <direct-declarator> [ <integer> ]
(11) <direct-declarator> ::=  <direct-declarator> ( <parameter-type-list> )

(12) <parameter-type-list> ::=  #empty
(13) <parameter-type-list> ::= <declaration>
(14) <parameter-type-list> ::= <parameter-type-list> , <declaration>

```
う、、長ったらしい。。
複雑そうに見えますが、我々が宣言の型を把握するために意識する規則はわずかです。
ここで重要な構文規則は、(1),(5),(6),(8),(9),(10),(11)です。

構文規則(1)の左辺\<declaration>がここでは開始記号になっています。ここから置き換えを始めます。

構文規則(5),(6)が適用されたら、我々はポインタ型を読んでいます。

構文規則(8)、ここで我々は宣言されている変数名を得ることができます。

構文規則(9)、この規則のおかげで\<declarator>と呼ばれる構文規則がネストすることになります。

構文規則(10)が適用されたら、我々は配列型を読んでいます。

構文規則(11)が適用されたら、我々は関数の型を読んでいます。

これらの中で、特に注目すべき規則は、ポインタ型に対応する(5),配列型に対応する(10),関数の型に対応する(11)のたった3つでしょう。
 
これらの構文規則が適用されたとき、我々はなんの規則が適用されたか記録するために、我々はあるスタックをdeclarationごとに用意することにします。

このスタックには、ポインタ型に対応する規則が読まれた場合、"pointer of"を（constポインタ型だった場合、"const pointer of"を）、配列型に対応する規則が読まれた場合、"array [ " + integer + " ] of"を、関数の型に対応する規則が読まれた場合、"function ( " + parameter-type-list + " ) returning"といった、各種文字列を入れていきます。

構文規則(1)で\<declarator>の部分の置き換えが全て終わったら、今度はここでスタックの中の文字列を上から順番に取り出していきます。
構文規則(8)で得られた変数名を最初にして、左から右へと、
取り出した順に順番につなげていきます。そして最後に\<declaration-specifier-list>で得られた記号を一番右に付け足すと、我々は宣言に対応する英語の読み方が得られたことになります。

さて、次の章で実際にいろいろなC言語の宣言を右端導出して試してみましょう。

# 宣言部分の右端導出
### まずは次の宣言を右端導出してみましょう。

```char *const ptr [4]```

```
<declaration>
-> <declaration-specifier-list> <declarator>  #(1)を適用
-> <declaration-specifier-list> * const <declarator>  #(6)を適用 スタックに"const pointer of"を入れる。
-> <declaration-specifier-list> * const <direct-declarator> [ 4 ]  #(10)を適用 スタックに"array [ 4 ] of"を入れる。
-> <declaration-specifier-list> * const ptr [ 4 ]  #(8)を適用
-> char * const ptr [ 4 ]  #(2),(4)を適用。
```
ここでスタックは上から順に次のようになっています。
```
"array [ 4 ] of"
"const pointer of"
```
これを上から取り出して左から右へと並べます。

"array [ 4 ] of const pointer of"

これを、構文規則(8)で得られた"ptr"の後ろにつなげて、さらにその後ろに、残りの\<declaration-specifier-list>で得られた"char"をつなげます。
すると次のようになります。

"ptr array [ 4 ] of const pointer of char"

これで宣言に対応する簡単な英語表記が得られました。とても単純に機械的にできたとおもいます。

### 次はちょっと変形したバージョンのこの宣言を見ていきましょう。
```char (*const ptr)[4]```

```
<declaration>
-> <declaration-specifier-list> <declarator>  #(1)を適用
-> <declaration-specifier-list> <direct-declarator> [ 4 ]  #(10)を適用 スタックに"array [ 4 ] of"を入れる。
-> <declaration-specifier-list> ( <declarator> ) [ 4 ]  #(9)を適用
-> <declaration-specifier-list> ( * const <declarator> ) [ 4 ]  #(6)を適用 スタックに"const pointer of"を入れる。
-> <declaration-specifier-list> ( * const <direct-declarator> ) [ 4 ]  #(7)を適用
-> <declaration-specifier-list> ( * const ptr ) [ 4 ]  #(8)を適用
-> char * const ptr [ 4 ]  #(2),(4)を適用。
```
ここでスタックは上から順に次のようになっています。
```
"const pointer of"
"array [ 4 ] of"
```
これを上から取り出して左から右へと並べます。

"const pointer of array [ 4 ] of"

これを、構文規則(8)で得られた"ptr"の後ろにつなげて、さらにその後ろに、残りの\<declaration-specifier-list>で得られた"char"をつなげます。
すると次のようになります。

"ptr const pointer of array [ 4 ] of char"

今度も宣言に対応する簡単な英語表記が得られましたね。declaratorがネストしている分、先ほどの宣言とはポインタと配列の読む順序が変わったのがわかると思います。

### 次はもっと複雑な例をみてみましょう。
```bool (*(*p)[10])(int a, int b)```


```
<declaration>
-> <declaration-specifier-list> <declarator>  #(1)を適用
-> <declaration-specifier-list> <direct-declarator>  #(7)を適用
-> <declaration-specifier-list> <direct-declarator> ( <parameter-type-list> )  #(11)を適用
-> <declaration-specifier-list> <direct-declarator> ( <parameter-type-list> , <declaration> )  #ここに現れた<declaration>について別にみてみる。
```
\<parameter-type-list>の末尾に\<declaration>が新たに現れましたので、ここで新たなスタックを用意して```int b```を導出してみましょう。
```
<declaration>
-> <declaration-specifier-list> <declarator>  #(1)を適用
-> <declaration-specifier-list> <direct-declarator>  #(7)を適用
-> <declaration-specifier-list> b #  (8)を適用
-> int b  #(2),(4)を適用
```
スタックには何もないので、これをそのまま読むと、

"b int"

になります。

戻ってみましょう。

```
<declaration>
-> <declaration-specifier-list> <declarator>  #(1)を適用
-> <declaration-specifier-list> <direct-declarator>  #(7)を適用
-> <declaration-specifier-list> <direct-declarator> ( <parameter-type-list> )  #(11)を適用
-> <declaration-specifier-list> <direct-declarator> ( <parameter-type-list> , int b )  #int bを導出できた。
-> <declaration-specifier-list> <direct-declarator> ( <declaration> , int b )  #(13)を適用
-> <declaration-specifier-list> <direct-declarator> ( int a , int b )  #前回の<declaration>の場合と同じ　スタックに"function ( a int , b int ) returning"を入れる。
-> <declaration-specifier-list> ( <declarator> ) ( int a , int b )  #(9)を適用
-> <declaration-specifier-list> ( * <declarator> ) ( int a , int b )  #(5)を適用 スタックに"pointer of"を入れる。
-> <declaration-specifier-list> ( * <direct-declarator> ) ( int a , int b )  #(7)を適用
-> <declaration-specifier-list> ( * <direct-declarator> [10] ) ( int a , int b )  #(10)を適用  スタックに"array [ 10 ] of"を入れる。
-> <declaration-specifier-list> ( * ( <declarator> ) [10] ) ( int a , int b )  #(9)を適用
-> <declaration-specifier-list> ( * ( * <declarator> ) [10] ) ( int a , int b )  #(5)を適用  スタックに"pointer of"を入れる。
-> <declaration-specifier-list> ( * ( * <direct-declarator> ) [10] ) ( int a , int b )  #(7)を適用
-> <declaration-specifier-list> ( * ( * p ) [10] ) ( int a , int b )  #(8)を適用
-> bool ( * ( * p ) [10] ) ( int a , int b )  #(2),(4)を適用
```
ここでスタックは上から順に次のようになっています。
```
"pointer of"
"array [ 10 ] of"
"pointer of"
"function ( a int , b int ) returning"
```
これを上から取り出して左から右へと並べます。

"pointer of array [ 10 ] of pointer of function ( a int , b int ) returning"


これを、構文規則(8)で得られた"p"の後ろにつなげて、さらにその後ろに、残りの\<declaration-specifier-list>で得られた"bool"をつなげます。
すると次のようになります。

"p pointer of array [ 10 ] of pointer of function ( a int , b int ) returning bool"

これで宣言に対応する簡単な英語表記が得られました。これからは、もう複雑な宣言に臆することもありませんね。

### 最後は標準Cライブラリの悪名高い関数宣言を見てみましょう。
```void (*signal(int sig, void(*func)(int a)))(int b)```

```
<declaration>
-> <declaration-specifier-list> <declarator>  #(1)を適用
-> <declaration-specifier-list> <direct-declarator>  #(7)を適用
-> <declaration-specifier-list> <direct-declarator> ( <parameter-type-list> )  #(11)を適用
-> <declaration-specifier-list> <direct-declarator> ( <declaration> )  #(13)を適用
-> <declaration-specifier-list> <direct-declarator> ( int b )  #int bを導出できた。 スタックに"function ( b int ) returning"を入れる。
-> <declaration-specifier-list> ( <declarator> ) ( int b )  #(9)を適用
-> <declaration-specifier-list> ( * <declarator> ) ( int b )  #(5)を適用  スタックに"pointer of"を入れる。
-> <declaration-specifier-list> ( * <direct-declarator> ) ( int b )  #(7)を適用
-> <declaration-specifier-list> ( * <direct-declarator> ( <parameter-type-list> ) ) ( int b )  #(11)を適用
-> <declaration-specifier-list> ( * <direct-declarator> ( <parameter-type-list> , <declaration> ) ) ( int b )  #(14)を適用
```
ここで現れた\<declaration>から```void(*func)(int a)```の部分を導出してみましょう。スタックも新たに用意します。
```
<declaration>
-> <declaration-specifier-list> <declarator>  #(1)を適用
-> <declaration-specifier-list> <direct-declarator>  #(7)を適用
-> <declaration-specifier-list> <direct-declarator> ( <parameter-type-list> )  #(11)を適用
-> <declaration-specifier-list> <direct-declarator> ( <declaration> )  #(13)を適用
-> <declaration-specifier-list> <direct-declarator> ( int a )  #int bを導出できた。 スタックに"function ( a int ) returning"を入れる。
-> <declaration-specifier-list> ( <declarator> ) ( int a )  #(9)を適用
-> <declaration-specifier-list> ( * <declarator> ) ( int a )  #(5)を適用  スタックに"pointer of"を入れる。
-> <declaration-specifier-list> ( * <direct-declarator> ) ( int a )  #(7)を適用
-> <declaration-specifier-list> ( *func ) ( int a )  #(8)を適用
-> void ( *func ) ( int a )  #(2),(4)を適用
```
ここでスタックは上から順に次のようになっています。
```
"pointer of"
"function ( a int ) returning"
```
これを上から取り出して左から右へと並べます。

"pointer of function ( a int ) returning"


これを、構文規則(8)で得られた"func"の後ろにつなげて、さらにその後ろに、残りの\<declaration-specifier-list>で得られた"void"をつなげます。
すると次のようになります。

"func pointer of function ( a int  ) returning void"

```void(*func)(int a)```の部分に対応する英語表記が得られましたので、使ったスタックは破棄して、もとの部分に戻ってみましょう。

```
<declaration>
-> <declaration-specifier-list> <declarator>  #(1)を適用
-> <declaration-specifier-list> <direct-declarator>  #(7)を適用
-> <declaration-specifier-list> <direct-declarator> ( <parameter-type-list> )  #(11)を適用
-> <declaration-specifier-list> <direct-declarator> ( <declaration> )  #(13)を適用
-> <declaration-specifier-list> <direct-declarator> ( int b )  #int bを導出できた。 スタックに"function ( b int ) returning"を入れる。
-> <declaration-specifier-list> ( <declarator> ) ( int b )  #(9)を適用
-> <declaration-specifier-list> ( * <declarator> ) ( int b )  #(5)を適用  スタックに"pointer of"を入れる。
-> <declaration-specifier-list> ( * <direct-declarator> ) ( int b )  #(7)を適用
-> <declaration-specifier-list> ( * <direct-declarator> ( <parameter-type-list> ) ) ( int b )  #(11)を適用
-> <declaration-specifier-list> ( * <direct-declarator> ( <parameter-type-list> , <declaration> ) ) ( int b )  #(14)を適用
-> <declaration-specifier-list> ( * <direct-declarator> ( <parameter-type-list> ,  void(*func)(int a)) ) ( int b )  #void(*func)(int a)を導出できた。
-> <declaration-specifier-list> ( * <direct-declarator> ( <declaration>,  void(*func)(int a)) ) ( int b )  #(13)を適用
-> <declaration-specifier-list> ( * <direct-declarator> ( int sig,  void(*func)(int a)) ) ( int b )  #int sigを導出できた。 スタックに"function ( sig int , func pointer of function ( a int ) returning void ) returning"を入れる。
-> <declaration-specifier-list> ( * signal ( int sig,  void(*func)(int a)) ) ( int b )  #(8)を適用
-> void ( * signal ( int sig,  void(*func)(int a)) ) ( int b )  #(2),(4)を適用
```
ここでスタックは上から順に次のようになっています。
```
"function ( sig int , func pointer of function ( a int ) returning void ) returning"
"pointer of"
"function ( b int ) returning"
```
これを上から取り出して左から右へと並べます。

"function ( sig int , func pointer of function ( a int ) returning void ) returning pointer of function ( b int ) returning"


これを、構文規則(8)で得られた"signal"の後ろにつなげて、さらにその後ろに、残りの\<declaration-specifier-list>で得られた"void"をつなげます。
すると次のようになります。

"signal function ( sig int , func pointer of function ( a int ) returning void ) returning pointer of function ( b int ) returning void"

きちんと正しく読むことが出来ましたね。

# 終わりに
今回の記事をもとに、C言語の宣言を簡単な英語の表記に変換するプログラムをPythonで書いてみました。ソースは[こちら](https://github.com/wo4mei3/decl_reader)です。

使い方は以下の通りです。

main.pyを実行すると、以下のようにプロンプトが表示されます。
```
 decl_reader $ python3 main.py
> 
```
セミコロンをつけて、任意の宣言を入力すると、それの簡単な英語での読み方が返ってきます。
ただし、structやunion、enumなどには対応していません。エラーを吐きます。
```
> char *const ptr [4] ;

ptr array [ 4 ] of const pointer of char

> char (*const ptr)[4];

ptr const pointer of array [ 4 ] of char

> bool (*(*p)[10])(int a, int b);

p pointer of array [ 10 ] of pointer of function ( a int , b int ) returning bool

> void (*signal(int sig, void(*func)(int a)))(int b);

signal function ( sig int , func pointer of function ( a int ) returning void ) returning pointer of function ( b int ) returning void
```

それではこの記事はこれで以上になります。長々と読んでいただきありがとうございました。
くまさんがこの記事で紹介した方法があなたのC言語の宣言解読法に採用される日を心待ちにしております。わくわく。

# 参考文献

B.W. カーニハン (著), D.M. リッチー (著), 石田 晴久 (翻訳)　(1989)『プログラミング言語C 第2版 ANSI規格準拠』 共立出版
前橋　和弥 (2017)『新・標準プログラマーズライブラリ C言語 ポインタ完全制覇』 技術評論社