|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 再 ： [さい] 1. (pref) re- 2. again 3. repeated ・ 再帰 ： [さいき] (n) recursive ・ 下 ： [した, もと] (adv) under (esp. influence or guidance) ・ 構文 ： [こうぶん] 【名詞】 1. syntax 2. sentence structure ・ 文 ： [ぶん] 【名詞】 1. sentence ・ 解析 ： [かいせき] 1. (n,vs) (1) analysis 2. (2) parsing
再帰下降構文解析（さいきかこうこうぶんかいせき、Recursive Descent Parsing）は、相互再帰型の手続き（あるいは再帰的でない同等の手続き）で構成されるLL法のトップダウン構文解析であり、各プロシージャが文法の各生成規則を実装することが多い。従って、生成されるプログラムの構造はほぼ正確にその文法を反映したものとなる。そのような実装の構文解析器を再帰下降パーサ（Recursive Descent Parser）と呼ぶ。 == 概要 == バックトラックのない再帰下降パーサを 予言的パーサ（predictive parser）と呼ぶ。予言的構文解析は文脈自由文法の一種であるLL(k)文法クラスでのみ可能であり、ある正の整数 k が存在し、再帰下降構文解析で次に使用すべき生成規則を選択するのに k 個のトークンを調べることで決定可能である。LL(k)文法には曖昧さがなく、左再帰も含まれない。文脈自由文法は左再帰のない形式に変換可能だが、左再帰を排除しただけでLL(k)文法となるわけではない。予言的パーサは線形時間で動作する。 バックトラックのある再帰下降構文解析では、各生成規則を毎回試すことで適用すべき生成規則を決定する。バックトラックのある再帰下降構文解析はLL(k)文法以外にも適用できるが、LL(k)以外の文法で有限時間以内に構文解析が完了するかどうかは保証されない。また完了したとしても、バックトラックのある再帰下降構文解析は指数関数時間を要する。 予言的パーサはよく使われているものの、文法をLL(k)形式に変換するよりも、LR法やLALR法のパーサを作成することも多い。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「再帰下降構文解析」の詳細全文を読む スポンサード リンク
|