大会名称 |
---|
2009年 情報科学技術フォーラム(FIT) |
大会コ-ド |
F |
開催年 |
2009 |
発行日 |
2009/8/20 |
セッション番号 |
2D |
セッション名 |
辞書・インデキシング |
講演日 |
2009/09/02 |
講演場所(会議室等) |
D会場(9号館1F 914教室) |
講演番号 |
D-002 |
タイトル |
ダブル配列による遷移表を用いたLR解析におけるshift・goto操作の高速化 |
著者名 |
蔵満 琢麻, 重越 秀美, 望月 久稔, |
キーワード |
ダブル配列, LR法, LR解析表, 構文解析 |
抄録 |
LR解析表は文脈自由文法の一種であるLR文法の構文解析に用いられる2次元の表で,C言語やPascal等のプログラミング言語のコンパイラに利用されており,時間的,領域的に効率的な実現方法が求められる.構文解析器生成系の一種であるyaccやbisonは,2次元のLR解析表を複数の1次元配列を用いて圧縮し,配列構造の高速性とリスト構造のコンパクト性をあわせもつ解析表を出力する.本論文では,トライ構造を効率的に実現するダブル配列の遷移を拡張することで,記憶領域のコンパクト性を維持しつつ,さらに解析速度を高速化したLR解析表を実現する手法を提案する. |
本文pdf |
PDF download (118.3KB) |