スタートC language面白論文紹介&読み会

発表者: kinaba面白い論文が見つからなかったので捏造

Towards
Higher-Order Syntax of
C Programming Language

Cの文法は文脈自由ではないと言われるなぜか。

Cの文法は文脈自由ではないと言われるなぜか。

FILE *fp;

width * height;n = (size_t)*ptr;

f = (m) * a;strdup(*argv)[9];byte (*bufs)[9];puts(str);

clock_t (t);

すごくどうでもいいんですけど、いろいろ面白いですね。

(a)*b*c;a*(b)*c;(a*)(b*)c;(a*)b*c;a*(b*)c;(a*)b(*c);(a*b)*c;a*(b*c);a(*b)(*c);(a*b*c);a*b()*c;a()*b*c;a*b(*c);a(*b)*c;

a*b*(c);a(*b*c);

a*b*c();(a(*)(b))*c;
クイズ：a*b*c; に括弧を入れて宣言文をつくることはできるか？

Cの文法は文脈自由ではないと言われる
根本原因は、型名 と 変数/関数名 が 文脈情報を持ってないと区別できないこと。

cf.
goto のラベル名
struct や enum の名前は文法的に区別できる。

Cの文法は文脈自由ではないと言われる
文脈自由じゃないなら、BNFより強力な文法記述言語で書けばいいじゃない！

Cの文法は文脈自由ではないと言われる
文脈自由じゃないなら、BNFより強力な文法記述言語で書けばいいじゃない！

ISO/IEC 9899:1999 自然言語で書いてある
gcc, clang, ... ： C や C++ で書いてある
CompCert (Coqで証明されたCコンパイラ) ：パーサだけ OCaml で書いてあったElsa/Elkhound C++ Parser： GLR構文解析で頑張るが結局最後はC++。

Cの文法は文脈自由ではないと言われる
文脈自由じゃないなら、BNFより強力な文法記述言語で書けばいいじゃない！

ISO/IEC 9899:1999 自然言語で書いてある
gcc, clang, ... ： C や C++ で書いてある
CompCert (Coqで証明されたCコンパイラ) ：パーサだけ OCaml で書いてあったElsa/Elkhound C++ Parser： GLR構文解析で頑張るが結局最後はC++。
なぜ揃いも揃ってチューリング完全な言語を使うのか。根性が足りない。

チューリング完全脳の恐怖∞: チューリングマシン

2: 文脈自由文法

1: 正規表現∞: チューリングマシン

現実を見よう

再帰文法

停止証明付き計算

文脈依存文法
帰納的木変形文法
高階文法

拡張表0Lシステム

Quoteマクロ文法
添字文法

CbVマクロ文法

多重CFG
木結合文法

範囲結合文法Boolean文法
And文法

2: 文脈自由文法
0Lシステム他色々PEG

1: 正規表現∞: チューリングマシン現実を見よう

再帰文法

停止証明付き計算

文脈依存文法
帰納的木変形文法
高階文法

拡張表0Lシステム

この辺の中間的な表現力を持つ言語を使って添字文法
CbVマクロ文法
C言語の文法を記述してみたい
多重CFG
Boolean文法
Quoteマクロ文法

木結合文法

範囲
結合文法

他色々

And文法

2: 文脈自由文法
0LシステムPEG
1: 正規表現∞: チューリングマシン
再帰文法
文脈依存文法

この辺なら書けるはずだけど人類には難しい

停止証明付き計算この辺では無理そうな気がなんとなくする
添字文法

CbVマクロ文法

多重CFG
木結合文法

範囲結合文法2: 文脈自由文法
0LシステムPEG
1: 正規表現この辺で頑張ってみる
帰納的木変形文法
高階文法
Quoteマクロ文法

Q. その前に、なぜ強力すぎる文法記述言語ではいけないのか
A. ツールで扱えない。
BNFで書いてあればそのままほぼコピペで yacc (など) に持って行ける。
IDE, エディタ, 静的解析器, lint, 構造化diff, 色分けマークアップツール 等のパーサに即座に転用できる。
A. 他言語に自動的に持って行くのが難しい。
Eclipse上の開発環境作りたいのにC++で書いたコンパイラが仕様書しかない等々。
A. 抽象性・非決定性がないことが多い
どこまでが仕様でどこまでが実装の都合なのか境界が曖昧。
A. 安全でない
コードジェネレータの吐くコードが意図した通りにparseされることの証明をどう書けば良いのか？どう検証すればよいのか？
A. 文法の複雑さをなんとなくの感覚でしか議論できない。

現状「Regular」「LALR」「CF」「その他」の４分類しか無いに等しいが、実際はほとんどが「その他」なので、現実の言語はほとんど何も分類されていない。

そういうわけで、この辺で頑張ってみる
帰納的木変形文法
高階文法
Quoteマクロ文法

Towards
Higher-Order Syntax of
C Programming Language

Macro Grammar [Fischer 68] とはパラメタ付き文脈自由文法（↓はインデントの深さでブロックを表現する文法簡易バージョン）

BLOCK(x)::= STATEMENT(x) | STATEMENT(x) BLOCK(x)STATEMENT(x)::= S_IF(x) | S_WHILE(x) | S_EXPR(x)S_IF(x)::= x if
EXPR ¥n BLOCK(x ¥t)
S_WHILE(x) ::= x while EXPR ¥n BLOCK(x ¥t)
S_EXPR(x) ::= x E
E::= E + E | E * E | …
PROGRAM ::= BLOCK()

Macro Grammar [Fischer 68] とはFischer さんが提案したのは３種類
OI Macro Grammar : パラメタを call-by-name で遅延評価する

IO Macro Grammar : パラメタを call-by-value で正格評価する

AORBPAIR(x)S::= a | b::= < x , x >::= PAIR( AORB )Quoted Macro Grammar : quoteとunquoteでどっちの評価モードか明示できる

Higher-Order Grammar
Context Free Grammar
各規則の型は :: string

Macro Grammar
各規則は、文字列を返す式を引数としてとって、文字列を返す :: stringstring
Higher-Order Grammar((string  string)  string)  string  string みたいな高階規則を考えよう
TYPE1(h, b) ::= h { b }TYPE2(h, b) ::= h begin b end
SS(t) ::= | S(t) SS(t)S(t)::= IF(t) | WHILE(t) | UBE
IF(t)::= t(if E, SS(t))
WHILE(t) ::= t(while E, SS(t))
UBE::= beginend S(TYPE2)
PROGRAM ::= SS(TYPE1)

Towards
Higher-Order Syntax ofC Programming Language

期待
パラメタ渡しを使って、「今宣言された変数の名前」とか「型の名前」とか持ち回っていけば文脈情報が表現できそうな気がする！

それだけで難しくても、なんかハイヤーオーダーパワーでどうにかなりそうな気がする！

やってみる（優先順位とか複雑な型とか無視して簡略化）「今使える型名と変数名」をパラメタに持たせる
EXPR ::= ( TYPE ) EXPR
| * EXPR| EXPR * EXPR
| VAR
| ( EXPR )EXPR(t, v) ::= ( t ) EXPR(t, v)| * EXPR(t, v)| EXPR * EXPR(t, v)| v| ( EXPR(t, v) )

やってみる
わりとよい

EXPR(t, v) ::= ( t ) EXPR(t, v)| * EXPR(t, v)| EXPR * EXPR(t, v)| v| ( EXPR(t, v) )EXPR( size_t, ptr | m | a ) は曖昧性無く以下を区別する。
引数は call-by-name で解釈

n = (size_t)*ptr;
キャスト式

f = (m) * a;
かけ算

宣言の扱い（いろいろ無視して簡略化）
BlockItems ::= (S | D)
| (S | D) BlockItems
D ::= typedef TYPE ID ;| TYPE VAR ;S ::= EXPR ;BlockItems(t, v) ::= (S | D)(t, v, Empty)| (S | D)(t, v, BlockItems)
D(t, v, k) ::= TDecl(ID, t, v, k)| VDecl(ID, t, v, k)S(t, v, k) ::= EXPR(t, v) ; k(t, v)
where Empty(t, v) ::=TDecl(tp, t, v, k) ::= typedef t tp ; k(t|tp, v)
VDecl(x, t, v, k) ::= t x ; k(t, v|x)

宣言の扱い変数宣言は、
VDecl(x, t, v, k)::= t x ; k(t, v|x)

宣言される変数名(cbv)と、今既にある型名(cbn) 、変数名(cbn)を受け取って変数宣言 “t x;” を生成して、更新された名前環境を継続 k に渡す。
型宣言も同様。
TDecl(tp, t, v, k) ::= typedef t tp ; k(t|tp, v)

注目ポイント：
cbv と cbn 引数、どっちも必要そう。
継続渡し形式なのは、趣味で高階関数使いたかっただけで、別に要らないと思います。

宣言の扱いBlockItems(t, v) ::= (S | D)(t, v, Empty)| (S | D)(t, v, BlockItems)
D(t, v, k) ::= TDecl(ID, t, v, k)| VDecl(ID, t, v, k)S(t, v, k) ::= EXPR(t, v) ; k(t, v)
where Empty(t, v) ::=TDecl(tp, t, v, k) ::= typedef t tp ; k(t|tp, v)
VDecl(x, t, v, k) ::= t x ; k(t, v|x)
BlockItems(LPCSTR, {}) が以下を一通りにparseすることが確かめられる

typedef LPCSTR x;x y;(x)*y;

Towards
Higher-Order Syntax of
C Programming Language

問題点
これはエラー

これは OK

int main() {typedef int x;int x;}

typedef int x;
int main() {int x;}

問題点
int main() {typedef int x;
int x;}

typedef int x;
int main() {int x;}

・ inner scope での定義と outer scope での定義は区別する必要がある
・ inner scope での衝突はエラーにする必要がある
・ outer scope との衝突は、外の scope を「隠す」必要がある＞ “int x;” より後で x を型名として使うコードは構文エラーにする必要あり高階文法パワーでどうにかなるか？

高階文法パワーでどうにかなるか？
・ inner scope での定義と outer scope での定義は区別する必要がある＞ どうにでもなる・ inner scope での衝突はエラーにする必要がある＞ 無理

・ outer scope との衝突は、外の scope を「隠す」必要がある＞ 無理

Towards
Higher-Order Syntax of
C Programming Language結論・ inner scope での衝突はエラーにする必要がある＞ 無理

・ outer scope との衝突は、外の scope を「隠す」必要がある＞ 無理

高階文法でもまだ無理なことがわかりました。

では、文法へのさらなる拡張として、何が必要か？

提案
nondeterminism
Foo にマッチするものか Bar にマッチするものか、どっちかFoo | Bar

CFG やその上の高階文法は、非決定性の足し算しかできない
anti-nondeterminism
Foo にマッチするもののうち Bar にマッチしないもの 。引き算が必要。

Foo - Bar

提案・ inner scope での衝突はエラーにする必要がある＞引き算あればできる・ outer scope との衝突は、外の scope を「隠す」必要がある＞ 引き算あればできるD(ot, ov, it, iv, k) ::= TDecl(ID-it-iv, ot, ov, it, iv, k)| VDecl(ID-it-iv, ot, ov, it, iv, k)
TDecl(tp, ot, ov, it, iv, k) ::= typedef (ot|it) tp ;k(ot-tp, ov-tp, it|tp, iv)
VDecl(x, ot, ov, it, iv, k) ::= (ot|it) x ;k(ot-x, ov-x, it, iv|x)

提案
高階文法
Quoteマクロ文法

パラメタ渡し的なものができる人たち↑

引き算的なものができる人たち↓
Boolean文法

PEG

最終結論
このようなものを考えるとよいのではないでしょうか！

高階文法

PEG

Quoteマクロ文法Boolean文法

注意：
引き算的なもの入りの文法の意味論を綺麗に定めるのは難しいので、うかつにやるとチューリング完全な言語で書くのと何もかわらなくなってしまいます。注意。

++
次回予告

発表者: kinabaC++の文法は文脈自由ではないと言われるなぜか。

FILE *fp;

width * height;n = (size_t)*ptr;

f = (m) * a;strdup(*argv)[9];byte (*bufs)[9];puts(str);

clock_t (t);

そんなものは大した問題ではない「C++ は、どれだけ文脈情報を持っていても、上から順には parse できない」

class Foo {Foo() {hello * world;}
typedef int hello;
int world;};

class Foo {Foo() {hello * world;}
int hello;
int world;};

曖昧性の問題は C と本質的にはほぼ同じ（優先度付き非決定性で書けそう）
template による複雑化は、まあどうにかなる。
ので、根本問題は上のパターンだと思われる。

次回

Towards C++ Parsing byHigher-Order-Delimited-Continuation PEG

お楽しみに（？）