著者

木山 真人

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.42, no.3, pp.40-48, 2001-03-15

被引用文献数

1

---

迅速なソフトウェア開発の要求が高まるにつれて,オブジェクト指向スクリプト言語は,より多くの場面で使用されている.これまでのスクリプト言語は,主に小規模なプログラムに使用されていたが,オブジェクト指向スクリプト言語はその保守性の高さから大規模なプログラムにも使用されている.一般に,オブジェクト指向言語ではプログラマの負担を軽くするため,メモリ管理を処理系側で行う実装となっている.そのため,処理系はメモリを有効に利用するために,不要になったメモリを回収し再利用可能にするためのごみ集め処理(GC)が必要になる.多くのオブジェクト指向スクリプト言語はGCを有しているが,実装の容易さから,マークスイープ法,リファレンスカウント法が用いられている.しかし,これらの方法ではプログラムの規模が大きくなるにつれて,GC処理時間の全実行時間に占める割合が大きくなる.そこで,プログラムの実行時間を短縮するため, GCの高速化に着目し,世代別GCの導入を検討する.本論文では,オブジェクト指向スクリプト言語Rubyに世代別GCを実装する場合の方法および結果を示す.世代別GCにすることで,従来のGCにくらべGC処理時間が最大92%,プログラムの実行時間が最大50エ%短縮することが分かった.Object-oriented scripting languages are becoming more and more important as a tool for software development, as it provides great flexibility for rapid application development.Scripting languages have been used for developing small-scale programs, object-oriented scripting languages are also used for developing large-scale programs. n general, memory management is implemented in object-oriented language in order to reduce programmers burden. Garbage Collection is necessary to collect and reuse the unnecessary memory to utilize the memory effectively. Mark-sweep and reference counting are general use among most object-oriented scripting languages. But these method, the ratio of whole execution time to GC execution time will increase as program size increase. In order to reduce program execution time, we introduce generational garbage collection in Ruby. In this paper, we show the method of implementation of generational garbage collection in Ruby, and how efficient that. It can reduce 50エ% of total execution time and 92エ of the cost of garbage collecting for our benchmark.

著者

後藤 勇太 木山 真人 芦原 評

雑誌

夏のプログラミング・シンポジウム2011報告集

巻号頁・発行日

pp.49-55, 2012-01-06

---

構文解析法でPackrat Parsingという手法がある.Packrat Parsingは,再帰下降構文解析にメモ化を組み合わせた手法であり,バックトラックや無限先読みを用いた解析において,線形時間で解析可能である.しかし,左再帰を含む文法は解析不可能である.そこで,従来は左再帰を含む文法を解析する際,左再帰部分を等価な右再帰に変換し,解析を行っていた.だが文法の変換を行うと構文木の構造が変化してしまう.また,特定の左再帰は変換できない.たとえば,閉路が存在する文法である.よって,この手法では解析できない文法がある.Alessandro Warthらは,左再帰を含む文法を,右再帰への変換無しに解析を可能にした.しかし,Alessandroらの手法では,同一の入力位置で左再帰が複数発生する文法において,特定の入力の解析に失敗する.そこで本研究では,左再帰を含む文法を右再帰への変換無しに解析でき,かつ従来手法の問題点に対応するPackrat Parserを提案・実装し,評価を行った.

著者

後藤 勇太 白田 佳章 木山 真人 芦原 評

出版者

情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.4, no.3, pp.84-93, 2011-06-29

---

構文解析法で Packrat Parsing という手法がある.Packrat Parsing は,再帰下降構文解析にメモ化を組み合わせた手法であり,バックトラックや無限先読みを用いた解析において,線形時間で解析可能である.しかし,左再帰を含む文法は解析不可能である.そこで,従来は左再帰を含む文法を解析する際,左再帰部分を等価な右再帰に変換し,解析を行っていた.だが文法の変換を行うと構文木の構造が変化してしまう.また,特定の左再帰は変換できない.たとえば,閉路が存在する文法である.よって,この手法では解析できない文法がある.Warth らは,左再帰を含む文法を,右再帰への変換なしに解析を可能にした.しかし,Warth らの手法では,同一の入力位置で左再帰が複数発生する文法において,特定の入力の解析に失敗する.また,構文木の構造が意図したものとは異なるという問題がある.そこで本研究では,更新検知を用いて,左再帰を含む文法を右再帰への変換なしに解析でき,かつ従来手法の 2 つの問題点に対応する Packrat Parser を提案・実装し,評価を行った.Packrat Parsing is a kind of parsing method. Packrat Parsing is a combination of Recursive Descent Parsing and memoization that can parse backtracking and unlimited look-ahead in linear parse time. However, Packrat Parsing cannot parse left recursive grammars. Thus, traditional method transforms left recursive grammars into right recursive grammars. Unfortunately, syntax tree is changed by the transforming. Moreover, particular left recursive grammars cannot be transformed. Traditional method cannot parse particular grammars. Warth, et al. made possible to support left recursive grammars without transforming in Packrat Parsing. However, the method cannot parse some grammars that have multiple left recursions at an input position. Furthermore, syntax tree is be unintended consequence when the method parses particular grammars. This paper presents imprementation and evaluation of Packrat Parser with Update Detection that possible to support left recursive grammars without transforming, and grammars that have multiple left recursions at an input position.