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

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

• 批准号: 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つは、動的拡張可能な文法を持つプログラミング言語でも、拡張可能な構文要素と拡張不可能で固定された構文要素があると言う点に着目し、はじめに与えられた文法の上でそれを区別し、拡張不可能な部分の構文解析表の構成が完了した後、それに関わる部分のε導出可能性に関する情報を破棄/固定することにより、大幅な使用メモリ領域の節約に成功した。また、動的に拡張可能な構文要素に関しても、単一の生成規則の付加で拡張が完了する場合だけでなく、複数の生成規則を付加することにより、構文の拡張が完了する場合も多い。そのような場合に効果を発揮する、構文要素の依存関係に基づくトポロジカルソート法を提案、プロトタイプを作成し、その実効性を確認した。

The language structure analysis system describes/generates the YACC/Bison expansion test for the purpose of analyzing the language structure. A method for constructing a differential analysis system of LALR(1) structure is proposed. LALR (1) structure analysis system difference construction method reverse, the first shift in the speech development environment, grammar, etc. for the first shift in the speech development environment, the second shift in the speech development environment, the third shift in the speech development environment, the fourth shift in the speech development environment, YACC, etc., use the method of system, the method of difference, the method of difference, the method of difference In this study, the proposed method includes the calculation of the difference between the first symbol and the second symbol, the expression method of the derivation possibility condition, the derivation possibility condition including the terminal symbol train, various concepts, and the group proposal. The construction method of "true" difference in the structure analysis table of LALR(1), LR(0) state transition and state recognition method are straight forward. This year's research is aimed at proposing a method for saving the necessary memory area by using the description system of speech structure analysis system, differential calculation, and self-expansion possibility. 1. The possible grammar of the opposite movement is supported by the possible grammar of speech, the impossible grammar of speech, the possible grammar of speech, Significant savings in the field of use were achieved. There are many cases where the expansion of a single generation rule is complete and the expansion of a complex generation rule is complete. In the event of a failure, the dependency of the constituent elements is determined by the method of preparation, the method of preparation and the method of execution.

项目成果

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"情報処理学会論文誌. (査読中).

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