Efficient Generation of Recursive Descent Parsers for Regular Right Part Grammars

IPSJ

Bibliographic Information

Other Title
  • 正規右辺文法の再帰降下パーサの効率のよい生成法
  • ソフトウェア基礎理論・言語処理系

Search this article

Description

正規右辺文法は構文規則の右辺の記述に文法記号の正規表現を許した文脈自由文法である.正規表現を使用することにより 構文規則の記述がコンパクトになり 文法の再帰的な構造を繰り返し構造に書き換えることができる.それにより 記述の便利さと読解性がよくなるだけでなく 効率のよい再帰降下パーサを作ることができる.本論文は正規右辺文法に対する再帰降下パーサの効率のよい生成法を示す.この方法では 入力文法の構造に対応する文法木を作り その文法木から直接に再帰降下パーサを生成する.パーサ生成の過程中 必要な時だけ 必要となるFIRST集合やFOLLOW集合しか計算しない.それを実現するために 文法木のノード間のFIRST/FOLLOW集合の計算上の依存関係を動的に解析する.また 同じ値を持つ集合は共通集合とされ 空間的 時間的な効率が上げられる.本方法で実現した再帰降下パーサ生成系は 入力される文法がELL(1)文法であるとき 確かに効率的である.本方法をPascalの文法に適用した結果 FIRST/FOLLOW集合計算にかかった時間が従来の方法と比べて4?9倍ぐらい短くなった.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top