JavaScript実行環境におけるC言語プログラムの実行基盤
スポンサーリンク
概要
- 論文の詳細を見る
現在一般的に使われている構文解析手法では,解析時間を線形時間に保つため,バックトラックを行わない.しかし,バックトラックを行わない解析手法では,先読みできる記号数が限られ,解析できる文法に制限ができてしまう.バックトラックを行い,parsing expression grammarで表現できる広範囲な構文規則を解析する手法としてpackrat parsingという手法がある.この手法では,解析対象文字列のすべての位置において一度解析した結果を保存するメモ化という手法を用いて,同じ解析を繰り返し行わないことで,単純なバックトラックでは最悪の場合に指数時間が必要だった解析時間を線形時間に抑えている.本発表では,この手法の問題点である,解析対象文字列のサイズに比例してメモ化領域が肥大化する点を改善することを目標としている.本発表での提案手法として,効果的にメモからエントリを削除するための手法と,メモ領域のサイズと解析効率のトレードオフを行うための手法の2点がある.まず,前者として直近にメモを行った付近で頻繁にバックトラックが発生することを前提とし,時間的局所性を用いて最近最も用いていないエントリをメモから削除する手法や,バックトラックを行う際に入力対象の細かい部分から広い部分に解析が進むことを考慮し,最も古いエントリをメモから削除する手法を提案する.また,後者の手法として,メモのヒット率が悪くなってきた場合に,動的にメモ領域の大きさを変化させ解析効率を維持する手法を提案する.以上の3つの手法を組み合わせ,解析効率をなるべく維持した状態でメモ領域を削減を行う.
- 2014-01-22
著者
関連論文
- ユビキタス環境のためのスクリプト言語の設計
- 拡張性のある組み込みアプリケーションを実現するスクリプティング言語の開発
- プロセスグループ別LSMのためのLSMフレームワーク拡張
- スクリプティング言語によるカーネル拡張
- B-008 実行コンテクストの変化に伴うアクセスコントロールの変更に関する研究(ソフトウェア,一般論文)
- セキュアコーディングと準形式設計モデル
- 魔法の水晶:音声インタラクションを備えたAmbient Displayの実装
- プログラミングとマッピング
- 最適投資モデルに基づくセキュアシステム設計と事例研究
- 最適投資モデルに基づくセキュアシステム設計と事例研究
- 最適投資モデルに基づくセキュアシステム設計と事例研究
- 大規模主記憶環境におけるGC方式の性能評価
- 分散障害管理のためのアクターベースのスクリプトフレームワーク
- オープンシステムディペンダビリティ : 新しいディペンダビリティへの挑戦
- 障害対応ワークフローに起こる二次リスクの保証事例の報告(システムのディペンダビリティ,2012年並列/分散/協調処理に関する『鳥取』サマー・ワークショップ(SWoPP鳥取2012))
- アシュアランス駆動プログラミングに向けて
- シェル文法の拡張可能な自己文法拡張スクリプト言語
- Mindstorms NXTを対象としたKonoha処理系のコンパクト化
- JavaScript生成言語への難読化処理の適用と性能評価
- エラーコードによるフォルト診断の例外処理機構
- JavaScript実行環境におけるC言語プログラムの実行基盤
- Konoha PlayGround:Web上で動作する多言語ソースコード変換系
- ディペンダブルシェルの分散環境での利用に向けた拡張
- GSNからの実行可能なスクリプト生成の提案
- 例外処理機能を備えたシェル言語
- 実行環境との同期を含めたAssurance Casesの管理ツールの提案(ディペンダビリティ,並列/分散/協調とディペンダブルコンピューティング及び一般)
- 障害対応ワークフローに起こる二次リスクの保証事例の報告