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

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

• 批准号: 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）语法分析系统，但在现有的差分配置方法中，LALR（1）仅是LR（0）状态的差分配置方法。过渡图是创建语法分析表的基础，对于读取符号的计算，超过了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"情報処理学会論文誌. (査読中).

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