WEKO3
アイテム
計算モデルとしての属性文法の制限とその対処法
https://ipsj.ixsq.nii.ac.jp/records/17026
https://ipsj.ixsq.nii.ac.jp/records/170266d12d650-595d-4101-8d84-4a9d3e6ed805
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-TPRO4001009.pdf (89.4 kB)
|
Copyright (c) 1999 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Trans(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1999-02-15 | |||||||
| タイトル | ||||||||
| タイトル | 計算モデルとしての属性文法の制限とその対処法 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Attribute Grammar's Limitations as a Computational Model, and Method to Deal with the Limitation | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | 発表概要 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| 東京工業大学 | ||||||||
| 著者所属 | ||||||||
| 東京工業大学 | ||||||||
| 著者所属 | ||||||||
| 北陸先端科学技術大学院大学 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Tokyo Institute of Technology | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Tokyo Institute of Technology | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Japan Advanced Institute of Science and Technology | ||||||||
| 著者名 |
長谷川, 勇
× 長谷川, 勇
|
|||||||
| 著者名(英) |
Isamu, Hasegawa
× Isamu, Hasegawa
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 属性文法は プログラミング言語などの文脈自由言語の意味を記述するために提案された計算モデルである. これまで コンパイラの記述や その自動生成など プログラムの静的な意味の記述に利用され 研究が進められてきた. しかしその一方で 属性文法は インタプリタやデバッガなど プログラムの動的な意味の記述には適さないとされてきた. 本研究の目的は 属性文法がプログラムの動的な意味の記述に適さないことを確認し その理由や対処方法を明らかにすることである. 本研究では まず 属性文法の記述力について 計算論の立場から考察を行った. 具体的には 意味規則が算術式で 属性の依存関係が非循環の場合について考えた. この場合 属性文法に入力が与えられた時に行われる計算を 判定命令を使用しないNプログラムとして表現できることを示した. この結果から 属性文法がチューリングマシンと等価な記述力を持つのは その意味規則に部分帰納的関数が許されているためであり 属性伝播という仕組みは なんら貢献していないことを示した. 我々は この属性伝播という仕組みに計算力が欠如している点が 属性文法がプログラムの動的な意味の記述に適さない理由であると考えた. そして その対処法として 高階属性文法を用いることで 属性文法の制限を補い 動的な意味の記述を容易に行う方法を示した. | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Attribute grammar is a computational model for describing semantics of formal languages, and has been used mainly for designing compilers and compiler generators. But it is not suitable for describing dynamic semantics. In this research, we confirm that attribute grammar is not fit to describe dynamic semantics of program, and to clear up the cause and the method to deal with the cause. We considered attribute grammar's description ability from a point of Computability. Concretely, we treat restricted attribute grammar that has arithmetic semantic rules, and there is no circularity in attribute dependencies. In this case, there is a corresponding N program that has no branches. As a result, we found that attribute grammar has ability equivalent to Turing Machine. But it highly depends on recursive functions in semantic rules. We consider that why attribute grammar is not suitable for describing dynamic semantics, is that attribute propagation mechanism lacks the calculation ability. And we show the method by which we easily describe the dynamic semantics or program by using Higher Order Attribute Grammar to make up attribute grammar's limitation. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA11464814 | |||||||
| 書誌情報 |
情報処理学会論文誌プログラミング（PRO） 巻 40, 号 SIG01(PRO2), p. 59-59, 発行日 1999-02-15 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7802 | |||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
