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

自扩展语法系统与编译时反射研究

• 批准号: 14780222
• 负责人: 加藤 大志朗
• 金额: $ 1.47万
• 依托单位: Kagawa University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2003
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14780222/
• 关键词: 文脈自由文法; LALR構文解析系; 差分的構成法; 自己反映計算; コンパイラ・コンパイラ; 構文解析

自己拡張可能な文法を持つプログラミング言語開発ツールとして、これまで種々のプログラミング言語の構文解析系記述/生成の為に用いられている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）解析系统的差异构建方法，但是现有的差分构造方法是基于LR（0）状态过渡图的差异构造方法，这是创建LALR（1）解析表的基础。在计算预读符号时，它们不会超出YACC等中使用的传统方法，并且很难说它们是差异化的构造方法。相比之下，本研究提出的方法提出了各种概念和框架，包括ε衍生性条件的表达以及包括ε衍生性条件在内的终端符号的衍生性，用于计算初步符号的计算。这还审查了LR（0）状态过渡图的状态识别方法，以使其成为LALR（1）句法分析表的“真实”差分结构。特别是，今年的研究提出了两种方法，以节省差分计算所需的存储空间，以便它们可以承受实际用作自我育儿编程语言的解析系统。一个事实的重点是，即使具有动态扩展语法的编程语言也具有可扩展的语法元素和不可扩展的，固定的语法元素，并且在开头，在分析表的结构上以对不延伸的分析表的结构进行了分析，我们已经成功地删除了有关范围的大量记忆空间。此外，关于动态扩展的语法元素，不仅可以通过添加单个生产规则来完成扩展，而且通常可以通过添加多个生产规则来完成扩展。提出了一种基于语法元素依赖性的拓扑排序方法，并创建了原型以确认其有效性。

项目成果

Daijiro Kato: "Reflective Context-Free Grammar"情報処理学会論文誌. 44巻7号(論文編集委員会より4月7日付けで採録通知あり)(未定). (2003)

Daijiro Kato：“Reflective Context-Free Grammar”，日本信息处理学会汇刊，第 44 卷，第 7 期（4 月 7 日论文编辑委员会的接受通知）（待定）。

Daijiro KATO: "Alternatives of First : a Basis of Incremental calculation of Look Ahead Sets"情報処理学会論文誌. (査読中).

加藤大二郎：“第一的替代方案：前瞻集增量计算的基础”日本信息处理学会杂志（正在审查中）。