演算子順位を利用した再帰的下向き構文解析器生成系の実現

概要

論文の詳細を見る
コンパイラにおける構文解析法としては、LR構文解析、LL構文解析(再帰的下向き構文解析)、演算子順位構文解析の3つが代表的である。LL構文解析やLR構文解析では生成規則のみによって文法定義を行い、それに基づいて構文解析を行う。そこで、算術式のように演算に優先順位がある場合には優先順位の差を非終端記号の導入によって表現する。従って優先順位のレベルが増えると、再帰的下向き構文解析では再帰呼び出しのネストが深くなり効率が落ちるし、LR構文解析では単純な生成規則還元が多くなり効率が悪い。演算子順位構文解析は他の2つに比べて扱える言語クラスが小さいが、算術式に対しては生成規則とは別に各演算子の優先順位を宣言し、その情報とスタックを用いることにより非常に効率の良い構文解析を行うことが出来る。また、生成規則のみによる定義よりも演算子順位を使った定義の方が一般的に分かり易い。そこで、LR構文解析や再帰的下向き構文解析に演算子順位構文解析の手法を取り入れる方法が研究されている。LR構文解析の中での方法は良く知られており、構文解析器生成系yaccなどによって既に実用化されているが、再帰的下向き構文解析の中での方法はあまり報告されていない。本稿では、中田らによって提案された再帰的下向き構文解析に演算子順位構文解析を取り入れる方法を取り上げ、実用に際しての問題点を考慮し、構文解析器とその生成系の実現・評価について述べる。
1996-03-06

演算子順位を利用した再帰的下向き構文解析器生成系の実現

スポンサーリンク

概要

著者

関連論文

スポンサーリンク