ログイン 新規登録
言語:

WEKO3

  • トップ
  • ランキング


インデックスリンク

インデックスツリー

  • RootNode

メールアドレスを入力してください。

WEKO

One fine body…

WEKO

One fine body…

アイテム

  1. 論文誌(トランザクション)
  2. プログラミング(PRO)
  3. Vol.7
  4. No.1

JavaScript実行環境におけるC言語プログラムの実行基盤

https://ipsj.ixsq.nii.ac.jp/records/98103
https://ipsj.ixsq.nii.ac.jp/records/98103
756f834d-b749-4cc8-a4b4-79ec0a82d20c
名前 / ファイル ライセンス アクション
IPSJ-TPRO0701007.pdf IPSJ-TPRO0701007.pdf (110.7 kB)
Copyright (c) 2014 by the Information Processing Society of Japan
オープンアクセス
Item type Trans(1)
公開日 2014-01-22
タイトル
タイトル JavaScript実行環境におけるC言語プログラムの実行基盤
タイトル
言語 en
タイトル C Language Platform on JavaScript Runtime
言語
言語 jpn
キーワード
主題Scheme Other
主題 [発表概要]
資源タイプ
資源タイプ識別子 http://purl.org/coar/resource_type/c_6501
資源タイプ journal article
著者所属
横浜国立大学大学院工学府
著者所属
横浜国立大学大学院工学府
著者所属
横浜国立大学大学院工学府/科学技術振興機構/CREST
著者所属(英)
en
Graduate School of Engineering, Yokohama National University
著者所属(英)
en
Graduate School of Engineering, Yokohama National University
著者所属(英)
en
Graduate School of Engineering, Yokohama National University / Japan Science and Technology Agency/CREST
著者名 松村, 哲郎 井出, 真広 倉光, 君郎

× 松村, 哲郎 井出, 真広 倉光, 君郎

松村, 哲郎
井出, 真広
倉光, 君郎

Search repository
著者名(英) Tetsuro, Matsumura Masahiro, Ide Kimio, Kuramitsu

× Tetsuro, Matsumura Masahiro, Ide Kimio, Kuramitsu

en Tetsuro, Matsumura
Masahiro, Ide
Kimio, Kuramitsu

Search repository
論文抄録
内容記述タイプ Other
内容記述 現在一般的に使われている構文解析手法では,解析時間を線形時間に保つため,バックトラックを行わない.しかし,バックトラックを行わない解析手法では,先読みできる記号数が限られ,解析できる文法に制限ができてしまう.バックトラックを行い,parsing expression grammarで表現できる広範囲な構文規則を解析する手法としてpackrat parsingという手法がある.この手法では,解析対象文字列のすべての位置において一度解析した結果を保存するメモ化という手法を用いて,同じ解析を繰り返し行わないことで,単純なバックトラックでは最悪の場合に指数時間が必要だった解析時間を線形時間に抑えている.本発表では,この手法の問題点である,解析対象文字列のサイズに比例してメモ化領域が肥大化する点を改善することを目標としている.本発表での提案手法として,効果的にメモからエントリを削除するための手法と,メモ領域のサイズと解析効率のトレードオフを行うための手法の2点がある.まず,前者として直近にメモを行った付近で頻繁にバックトラックが発生することを前提とし,時間的局所性を用いて最近最も用いていないエントリをメモから削除する手法や,バックトラックを行う際に入力対象の細かい部分から広い部分に解析が進むことを考慮し,最も古いエントリをメモから削除する手法を提案する.また,後者の手法として,メモのヒット率が悪くなってきた場合に,動的にメモ領域の大きさを変化させ解析効率を維持する手法を提案する.以上の3つの手法を組み合わせ,解析効率をなるべく維持した状態でメモ領域を削減を行う.
論文抄録(英)
内容記述タイプ Other
内容記述 Many of widely used parsing techniques avoid backtracking to keep time complexity linear. However, these techniques can lookup only limited number of symbols, thus placing some restriction on grammars. Packrat parsing is a parsing algorithm which use backtracking to handle wide range of grammars defined in parsing expession grammar. With this algorithm, a technique called memoization is used to store results of parsing performed in a position to eliminate duplicated analisys in backtrack to keep parsing time linear. In this presentation, we propose methods to eliminate entries from memo effectively, and a method to set trade-off between memo size and parsing efficiency. For entry elimination, we propose two methods; the first one assumes backtrack occurs mainly near the last position memoized and eliminate least-recently used entry, while the second one considers parsing order and eliminates oldest entry from the memo. For trade-off control method, we propose an algorithm to modify memo size dynamically when hit-rate degrades to keep parsing efficiency. Combining these methods, our system effectively reduce memo size while keeping parsing as efficient as possible.
書誌レコードID
収録物識別子タイプ NCID
収録物識別子 AA11464814
書誌情報 情報処理学会論文誌プログラミング(PRO)

巻 7, 号 1, p. 30-30, 発行日 2014-01-22
ISSN
収録物識別子タイプ ISSN
収録物識別子 1882-7802
出版者
言語 ja
出版者 情報処理学会
戻る
0
views
See details
Views

Versions

Ver.1 2025-01-21 12:37:52.796646
Show All versions

Share

Mendeley Twitter Facebook Print Addthis

Cite as

倉光, 君郎, 2014: 情報処理学会, 30–30 p.

Loading...

エクスポート

OAI-PMH
  • OAI-PMH JPCOAR
  • OAI-PMH DublinCore
  • OAI-PMH DDI
Other Formats
  • JSON
  • BIBTEX

Confirm


Powered by WEKO3


Powered by WEKO3