自己拡張可能な文法体系とコンパイルタイム・リフレクションに関する研究

自己拡張可能な文法を持つプログラミング言語開発ツールとして、これまで種々のプログラミング言語の構文解析系記述/生成の為に用いられているYACC/Bisonの拡張を試みている。その前段階として、YACC/Bisonで用いられているLALR(1)構文解析系の差分的構成法を提案した。これまで、LALR(1)構文解析系の差分的構成法は、プログラミング言語開発環境における文法デバッグ等の為のものとして提案されたものがあるが、既存の差分的構成法では、LALR(1)構文解析表作成の基礎となるLR(0)状態遷移グラフのみの差分的構成法となっており、先読み記号の計算に関しては、YACC等で用いられている伝統的な方法の枠を超えるものではなく、差分的構成法とは言い難いものである。これに対し、本研究で提案した方法は、先読み記号の計算も差分的に計算する為の、ε導出可能性条件の表現方法、ε導出可能性条件を含む終端記号列の導出可能性を含む、各種の概念、枠組みを提案した。この中には、LALR(1)構文解析表の「真の」差分的構成法となるよう、LR(0)状態遷移グラフの状態識別法の見直しも行った。本年度の研究では特に、自己拡張可能なプログラミング言語の構文解析系記述体系として実用に耐え得るよう、差分的計算に必要な記憶領域を節約する為の方法として2つの方法を提案した。1つは、動的拡張可能な文法を持つプログラミング言語でも、拡張可能な構文要素と拡張不可能で固定された構文要素があると言う点に着目し、はじめに与えられた文法の上でそれを区別し、拡張不可能な部分の構文解析表の構成が完了した後、それに関わる部分のε導出可能性に関する情報を破棄/固定することにより、大幅な使用メモリ領域の節約に成功した。また、動的に拡張可能な構文要素に関しても、単一の生成規則の付加で拡張が完了する場合だけでなく、複数の生成規則を付加することにより、構文の拡張が完了する場合も多い。そのような場合に効果を発揮する、構文要素の依存関係に基づくトポロジカルソート法を提案、プロトタイプを作成し、その実効性を確認した。

自己拡張可能な文法を持つプログラミング言語開発ツールとして、これまで種々のプログラミング言語の構文解析系記述/生成の為に用いられているYACC/Bisonの拡張を試みている。その前段階として、YACC/Bisonで用いられているLALR(1)構文解析系の差分的構成法を提案した。これまで、LALR(1)構文解析系の差分的構成法は、プログラミング言語開発環境における文法デバッグ等の為のものとして提案されたものがあるが、既存の差分的構成法では、LALR(1)構文解析表作成の基礎となるLR(0)状態遷移グラフのみの差分的構成法となっており、先読み記号の計算に関しては、YACC等で用いられている伝統的な方法の枠を超えるものではなく、差分的構成法とは言い難いものである。これに対し、本研究で提案した方法は、先読み記号の計算も差分的に計算する為の、ε導出可能性条件の表現方法、ε導出可能性条件を含む終端記号列の導出可能性を含む、各種の概念、枠組みを提案した。この中には、LALR(1)構文解析表の「真の」差分的構成法となるよう、LR(0)状態遷移グラフの状態識別法の見直しも行った。本年度の研究では特に、自己拡張可能なプログラミング言語の構文解析系記述体系として実用に耐え得るよう、差分的計算に必要な記憶領域を節約する為の方法として2つの方法を提案した。1つは、動的拡張可能な文法を持つプログラミング言語でも、拡張可能な構文要素と拡張不可能で固定された構文要素があると言う点に着目し、はじめに与えられた文法の上でそれを区別し、拡張不可能な部分の構文解析表の構成が完了した後、それに関わる部分のε導出可能性に関する情報を破棄/固定することにより、大幅な使用メモリ領域の節約に成功した。また、動的に拡張可能な構文要素に関しても、単一の生成規則の付加で拡張が完了する場合だけでなく、複数の生成規則を付加することにより、構文の拡張が完了する場合も多い。そのような場合に効果を発揮する、構文要素の依存関係に基づくトポロジカルソート法を提案、プロトタイプを作成し、その実効性を確認した。