再帰下降構文解析器

コンピュータサイエンスにおいて、再帰下降パーサーは、相互に再帰的な手続き（または非再帰的な同等のもの）のセットから構築された一種のトップダウンパーサーであり、各手続きは文法の非終端記号の1つを実装します。したがって、結果として得られるプログラムの構造は、それが認識する文法の構造を忠実に反映します。^[¹^]^[²^]

予測構文解析器は、バックトラッキングを必要としない再帰下降構文解析器です。^{[ 3 ]}予測構文解析は、 LL( k )文法のクラスでのみ可能です。LL(k)文法とは、再帰下降構文解析器が入力の次のk個のトークンのみを調べて使用する生成規則を決定できるような正の整数kが存在する文脈自由文法です。したがって、LL( k )文法は、すべての曖昧な文法と、左再帰を含むすべての文法を除外します。任意の文脈自由文法は、左再帰のない同等の文法に変換できますが、左再帰の除去によって必ずしも LL( k )文法が得られるとは限りません。予測構文解析器は線形時間で実行されます。

バックトラッキング付き再帰下降は、各生成規則を順番に試すことでどの生成規則を使用するかを決定する手法です。バックトラッキング付き再帰下降はLL( k )文法に限定されませんが、文法がLL( k )でない限り終了が保証されません。終了した場合でも、バックトラッキング付き再帰下降を使用するパーサーは指数時間を要する場合があります。

予測構文解析器は広く利用されており、手動で構文解析器を作成する場合によく選ばれますが、プログラマーはLL( k )言語用、またはLALRやLRなどの代替構文解析器を使用した構文解析器生成ツールによって生成されたテーブルベースの構文解析器を使用することを好む場合が多いです。これは、文法が LL( k )形式でない場合に特に当てはまります。予測構文解析に適したLL形式に変換する作業が必要となるためです。予測構文解析器は、 ANTLRなどのツールを使用して自動的に生成することもできます。

予測構文解析器は、各非終端記号の遷移図を使用して表現することができ、初期状態と最終状態の間のエッジは、生成規則の右側の記号（終端記号と非終端記号）によってラベル付けされます。^{[ 4 ]}

パーサーの例

以下のEBNFライクな文法（ニクラウス・ヴィルトのPL/0プログラミング言語用、『アルゴリズム＋データ構造＝プログラム』より）はLL(1)形式です。

プログラム=ブロック"." 。block = [ "const" ident "=" number { "," ident "=" number } ";" ] [ "var" ident { "," ident } ";" ] { "procedure" ident ";" block ";" } statement .ステートメント= ident ":="式| "call" ident | "begin"ステートメント{ ";"ステートメント} "end" | "if"条件"then"ステートメント| "while"条件"do"ステートメント.条件= "odd"式|式( "=" | "#" | "<" | "<=" | ">" | ">=" )式。式= [ "+" | "-" ]項{( "+" | "-" )項} 。項=因子{( "*" | "/" )因子} 。因子=識別子|数値| "("式")" 。

終端記号は引用符で囲んで表記します。非終端記号はそれぞれ文法規則によって定義されますが、識別子と数値は暗黙的に定義されているものとみなされます。

C言語による実装

以下は、上記の言語に対する再帰下降構文解析器のC言語による実装です。この構文解析器はソースコードを読み込み、コードの解析に失敗した場合はエラーメッセージを表示して終了し、正しく解析できた場合は何も表示せずに終了します。

下の予測構文解析器が上の文法とどれほどよく似ているかに注目してください。文法内の各非終端記号に対応する処理手順があります。構文解析は、最後の非終端記号が処理されるまで、上から下へと順に行われます。

peeksymこのプログラム断片は、現在のシンボルを覗き見る関数consumesym、シンボルを消費して次のシンボルへ移動する関数、およびerrorエラーメッセージを表示する関数に依存しています。これらの関数は、字句解析器によって提供されるものと想定されています。

extern void error ( const char msg []); extern void consumesym ();typedef enum Symbol { ident , number , lparen , rparen , times , slash , plus , minus , eql , neq , lss , leq , gtr , geq , callsym , beginsym , semicolon , endsym , ifsym , whilesym , becomes , thensym , dosym , constsym , comma , varsym , procsym , period , oddsym } Symbol ; extern Symbol peeksym ();bool accept ( Symbol s ) { if ( peeksym () == s ) { consumesym (); return true ; } return false ; }bool expect ( Symbol s ) { if ( accept ( s )) { return true ; } error ( "expect: 予期しないシンボル" ); return false ; }void factor () { if ( accept ( ident ) || accept ( number )) { return ; } if ( accept ( lparen )) { expression (); expect ( rparen ); } else { error ( "factor: syntax error" ); consumesym (); } }void term () { factor (); while ( peeksym () == times || peeksym () == slash ) { consumesym (); factor (); } }void expression () { if ( peeksym () == plus || peeksym () == minus ) { consumesym (); } term (); while ( peeksym () == plus || peeksym () == minus ) { consumesym (); term (); } }void condition () { if ( accept ( oddsym )) { expression (); return ; } expression (); if ( peeksym () == eql || peeksym () == neq || peeksym () == lss || peeksym ( ) == leq || peeksym () == gtr || peeksym () == geq ) { consumesym (); expression (); } else { error ( "condition: invalid operator" ); consumesym (); } }void statement () { if ( accept ( ident )) { expect ( becomes ); expression (); } else if ( accept ( callsym )) { expect ( ident ); } else if ( accept ( beginsym )) { do { statement (); } while ( accept ( semicolon )); expect ( endsym ); } else if ( accept ( ifsym )) { condition (); expect ( thensym ); statement (); } else if ( accept ( whilesym )) { condition (); expect ( dosym ); statement (); } else { error ( "statement: syntax error" ); consumesym (); } }void block () { if ( accept ( constsym )) { do { expect ( ident ); expect ( eql ); expect ( number ); } while ( accept ( comma )); expect ( semicolon ); } if ( accept ( varsym )) { do { expect ( ident ); } while ( accept ( comma )); expect ( semicolon ); } while ( accept ( procsym )) { expect ( ident ); expect ( semicolon ); block (); expect ( semicolon ); } statement (); }void program () { block (); expect ( period ); }

例

再帰下降構文解析器生成器の例：

TMG – 1960年代から1970年代初頭にかけて使用された初期のコンパイラ
JavaCC
ココ/R
アントラー
Spirit Parser Framework – 事前コンパイル不要のC++再帰下降パーサー生成フレームワーク
parboiled (Java) – Java用の再帰下降PEG解析ライブラリ

ClangコンパイラのC++フロントエンドには、再帰下降構文解析アルゴリズムに基づいた手書きの構文解析器が含まれています。^{[ 5 ]}

参考文献

↑この記事は、2008年11月1日以前にFree On-line Dictionary of ComputingのRecursive+descent+parserから取得した資料に基づいており、 GFDLバージョン1.3以降の「再ライセンス」条項に基づいて組み込まれています。
↑ Burge, WH (1975). Recursive Programming Techniques . Addison-Wesley Publishing Company. ISBN 0-201-14450-6。
↑ワトソン、デス（2017年3月22日）。コンパイラ構築への実践的アプローチ。シュプリンガー。ISBN 978-3-319-52789-5。
↑ Aho, Alfred V. ; Sethi, Ravi; Ullman, Jeffrey (1986). Compilers: Principles, Techniques and Tools (first ed.). Addison Wesley. p. 183 .
↑ Clang が C/C++ の型名/変数名の曖昧さをどのように処理するか https://eli.thegreenplace.net/2012/07/05/how-clang-handles-the-type-variable-name-ambiguity-of-cc/

一般的な参考文献

コンパイラ：原理、技術、ツール、初版、Alfred V Aho、Ravi Sethi、Jeffrey D Ullman、特に第4.4節。
『Javaにおける最新コンパイラ実装第2版』、アンドリュー・アペル著、2002年、ISBN 0-521-82060-X。
再帰プログラミング技法、WH Burge、1975年、ISBN 0-201-14450-6
C言語でコンパイラを作成する、チャールズ・N・フィッシャー、リチャード・J・ルブラン・ジュニア著、1991年、ISBN 0-8053-2166-7。
C#とJavaによるコンパイル、パット・テリー著、2005年、ISBN 0-321-26360-X624
アルゴリズム＋データ構造＝プログラム、ニクラウス・ヴィルト、1975年、ISBN 0-13-022418-9
『コンパイラーの構築』、ニクラウス・ヴィルト、1996 年、ISBN 0-201-40353-6

外部リンク

ジャック・W・クレンショー著『Let's Build A Compiler』（1988年～1995年）、Pascal言語、アセンブリ言語出力、「シンプルに保つ」アプローチを採用。

[1] この記事は、2008年11月1日以前にFree On-line Dictionary of ComputingのRecursive+descent+parserから取得した資料に基づいており、 GFDLバージョン1.3以降の「再ライセンス」条項に基づいて組み込まれています。

[2] Burge, WH (1975). Recursive Programming Techniques . Addison-Wesley Publishing Company. ISBN 0-201-14450-6。

[Watson2017-3] ワトソン、デス（2017年3月22日）。コンパイラ構築への実践的アプローチ。シュプリンガー。ISBN 978-3-319-52789-5。

[4] Aho, Alfred V. ; Sethi, Ravi; Ullman, Jeffrey (1986). Compilers: Principles, Techniques and Tools (first ed.). Addison Wesley. p. 183 .

[5] Clang が C/C++ の型名/変数名の曖昧さをどのように処理するか https://eli.thegreenplace.net/2012/07/05/how-clang-handles-the-type-variable-name-ambiguity-of-cc/

[

[

[ 3 ]

[ 4 ]

[ 5 ]

再帰下降構文解析器

パーサーの例

C言語による実装

例

関連項目

参考文献

一般的な参考文献

外部リンク

関連するトピック

コンピュータサイエンス

相互に再帰的な

トップダウンパーサーであり、各

手続きは