Loading article…
コンピュータサイエンスにおいて、再帰上昇構文解析は、テーブルではなく相互再帰関数を使用するLRパーサーを実装するための手法です。そのため、パーサーは再帰下降と同様にホスト言語で直接エンコードされます。コンパイルが解釈よりも高速であるのと同じ理由で、直接エンコードされたパーサーは通常、テーブル駆動型のパーサーよりも高速になります[ 1 ]。また、再帰上昇構文解析は（名目上）手動で編集することが可能ですが、テーブル形式の実装は一般の人間にはほとんど読みにくいものです。
再帰的上昇は、トーマス・ペネロが論文「 Pennello, Thomas J. (1986). "Very fast LR parsing" . Proceedings of the 1986 SIGPLAN symposium on Compiler construction - SIGPLAN '86 . pp. 145–151 . doi : 10.1145/12276.13326 . ISBN 」で初めて記述した。 0897911970. S2CID 17214407 . 1986年に、彼はLRパーサーの手動編集可能な実装を作成するつもりはなく、アセンブリ言語で実装された保守可能で効率的なパーサーを作成するつもりだった。この技術は後に、1988年にGH Roberts [ 2 ]によって、また1992年にTheoretical Computer Science誌に掲載されたLeermakers、Augustejn、Kruseman Aretz [ 3 ]による記事で詳しく説明された。この技術の非常に読みやすい説明は、2003年にMorellとMiddleton [ 4 ]によって書かれた。SperberとThiemannによるTOPLASの記事にも良い説明がある。[ 5 ]
再帰上昇法は再帰下降法と統合され、再帰上昇/下降法と呼ばれる手法が生まれました。この実装手法は、状態の数が減り、これらの状態の一部がボトムアップよりもトップダウンの方が直感的であるため、手動で編集しやすいと言えます。また、従来の再帰上昇法に比べて、わずかながらパフォーマンスの向上も期待できます。[ 6 ]
直感的に言えば、再帰的上昇はLR構文解析の概念を文字通り実装したものです。パーサー内の各関数は、単一のLRオートマトン状態を表します。各関数内では、入力ストリームから読み取られた現在のトークンに基づいて適切なアクションを選択するために、多分岐ステートメントが使用されます。トークンが識別されると、エンコードされている状態に基づいてアクションが実行されます。問題のトークンに基づいて実行される可能性のある基本的なアクションは、次の2つです。
LRオートマトンには、特定の状態において実行可能な3つ目のアクションも存在します。ただし、これはシフトカウンタがゼロにデクリメントされた（つまり、現在の状態が結果を処理すべきであることを示す）リデュース処理の後に限られます。これはgotoアクションと呼ばれ、本質的にはプロダクション内の非終端記号を処理するために設計されたシフトの特殊なケースです。このアクションは、マルチブランチステートメントの後に処理する必要があります。なぜなら、リデュース処理の結果は、コールスタックのさらに下からこの場所で「再び現れる」からです。
Bison構文における以下の文法を考えてみましょう。
expr : expr '+' term { $$ = $1 + $3; } | expr '-' term { $$ = $1 - $3; } | 用語 { $$ = $1; } ; 項 : '(' 式 ')' { $$ = $2; } | num { $$ = $1; } ; num : '0' { $$ = 0; } | '1' { $$ = 1; } ;この文法は、式非終端記号において左再帰的であるものの、先読みを必要としないため、 LR(0)です。再帰的上昇法は、テーブル駆動型パーサーがそのようなケースを処理するのとほぼ同じ方法（可能な先読みに基づいて競合解決を事前に計算する）で、LALR(1) の文法も処理できます。
以下は、上記の文法に基づいた再帰的上昇構文解析器のScalaによる実装です。
object ExprParser { private type Result = ( NonTerminal , Int ) private sealed trait NonTerminal { val v : Int } private case class NTexpr ( v : Int , in : Stream [ Char ]) extends NonTerminal private case class NTterm ( v : Int , in : Stream [ Char ]) extends NonTerminal private case class NTnum ( v : Int , in : Stream [ Char ]) extends NonTerminal class ParseException ( msg : String ) extends RuntimeException ( msg ) { def this () = this ( "" ) def this ( c : Char ) = this ( c . toString ) } def parse ( in : Stream [ Char ]) = state0 ( in ). _1 . v /* * 0 $accept: . expr $end * * '(' シフトして状態 1 へ * '0' シフトして状態 2 へ * '1' シフトして状態 3 へ * * expr で状態 4 へ * term で状態 5 へ * num で状態 6 へ */ private def state0 ( in : Stream [ Char ]) = in match { case cur #:: tail => { def loop ( tuple : Result ): Result = { val ( res , goto )= tuple if ( goto == 0 ) { loop ( res match { case NTexpr ( v , in ) => state4 ( in , v ) case NTterm ( v , in ) => state5 ( in , v ) case NTnum ( v , in ) => state6 ( in , v ) }) } else ( res , goto - 1 ) } loop ( cur match { case '(' => state1 ( tail ) case '0' => state2 ( tail ) case '1' => state3 ( tail ) case c => throw new ParseException ( c ) }) } case Stream () => throw new ParseException } /* * 4 項: '(' . expr ')' * * '(' シフトして状態 1 へ移動 * '0' シフトして状態 2 へ移動 * '1' シフトして状態 3 へ移動 * * expr は状態 7 へ * term は状態 5 へ * num は状態 6 へ */ private def state1 ( in : Stream [ Char ]): Result = in match { case cur #:: tail => { def loop ( tuple : Result ): Result = { val ( res , goto ) = tuple if ( goto == 0 ) { loop ( res match { case NTexpr ( v ,in ) => state7 ( in , v ) case NTterm ( v , in ) => state5 ( in , v ) case NTnum ( v , in ) => state6 ( in , v ) }) } else ( res , goto - 1 ) } loop ( cur match { case '(' => state1 ( tail ) case '0' => state2 ( tail ) case '1' => state3 ( tail ) case c => throw new ParseException ( c ) }) } case Stream () => throw new ParseException } /* * 6 num: '0' . * * $default reduce using rule 6 (num) */ private def state2 ( in : Stream [ Char ]) = ( NTnum ( 0 , in ), 0 ) /* * 7 num: '1' . * * $default reduce using rule 7 (num) */ private def state3 ( in : Stream [ Char ]) = ( NTnum ( 1 , in ), 0 ) /* * 0 $accept: expr . $end * 1 expr: expr . '+' term * 2 | expr . '-' term * * $end シフトして状態 8 へ * '+' シフトして状態 9 へ * '-' シフトして状態 10 へ */ private def state4 ( in : Stream [ Char ], arg1 : Int ): Result = in match { case cur#:: tail => { decrement ( cur match { case '+' => state9 ( tail , arg1 ) case '-' => state10 ( tail , arg1 ) case c => throw new ParseException ( c ) }) } case Stream () => state8 ( arg1 ) } /* * 3 expr: term . * * $default reduce using rule 3 (expr) */ private def state5 ( in : Stream [ Char ], arg1 : Int ) = ( NTexpr ( arg1 , in ), 0 ) /* * 5 term: num . * * $default reduce using rule 5 (term) */ private def state6 ( in : Stream [ Char ], arg1 : Int ) = ( NTterm ( arg1 , in ), 0 ) /* * 1 expr: expr . '+' 項 * 2 | expr . '-' 項 * 4 項: '(' expr . ')' * * '+' シフトして状態 9 へ * '-' シフトして状態 10 へ * ')' シフトして状態 11 へ */ private def state7 ( in : Stream [ Char ], arg1 : Int ): Result = in match { case cur #:: tail => { decrement ( cur match { case '+' => state9 ( tail , arg1 ) case '-' => state10 ( tail , arg1 ) case ')' => state11 ( tail ,arg1) case c => throw new ParseException ( c ) }) } case Stream () => throw new ParseException } /* * 0 $accept: expr $end . * * $default accept */ private def state8 ( arg1 : Int ) = ( NTexpr ( arg1 , Stream ()), 1 ) /* * 1 expr: expr '+' . term * * '(' シフトして状態 1 へ * '0' シフトして状態 2 へ * '1' シフトして状態 3 へ * * term は状態 12 へ * num は状態 6 へ */ private def state9 ( in : Stream [ Char ], arg1 : Int ) = in match { case cur #:: tail => { def loop ( tuple : Result ): Result = { val ( res , goto ) = tuple if ( goto == 0 ) { loop ( res match { case NTterm ( v , in ) => state12 ( in , arg1 , v ) case NTnum ( v , in ) => state6 ( in , v ) case _ => throw new AssertionError }) } else ( res , goto - 1 ) } loop ( cur match { case '(' => state1 ( tail ) case '0' => state2 ( tail ) case '1' =>state3 ( tail ) case c => throw new ParseException ( c ) }) } case Stream () => throw new ParseException } /* * 2 expr: expr '-' . term * * '(' シフトして状態 1 へ * '0' シフトして状態 2 へ * '1' シフトして状態 3 へ * * term は状態 13 へ * num は状態 6 へ */ private def state10 ( in : Stream [ Char ], arg1 : Int ) = in match { case cur #:: tail => { def loop ( tuple : Result ): Result = { val ( res , goto ) = tuple if ( goto == 0 ) { loop ( res match { case NTterm ( v , in ) => state13 ( in , arg1 , v ) case NTnum ( v , in ) => state6 ( in , v ) case _ => throw new AssertionError }) } else ( res , goto - 1 ) } loop ( cur match { case '(' => state1 ( tail ) case '0' => state2 ( tail ) case '1' => state3 ( tail ) case c => throw new ParseException ( c ) }) } case Stream () => throw new ParseException} /* * 4 項: '(' 式 ')' 。 * * $default ルール 4 (項) を使用して削減します */ private def state11 ( in : Stream [ Char ], arg1 : Int ) = ( NTterm ( arg1 , in ), 2 ) /* * 1 式: 式 '+' 項 。 * * $default ルール 1 (式) を使用して削減します */ private def state12 ( in : Stream [ Char ], arg1 : Int , arg2 : Int ) = ( NTexpr ( arg1 + arg2 , in ), 2 ) /* * 2 式: 式 '-' 項 。 / ** * $default reduce using rule 2 (expr) */ private def state13 ( in : Stream [ Char ], arg1 : Int , arg2 : Int ) = ( NTexpr ( arg1 - arg2 , in ), 2 ) private def decrement ( tuple : Result ) = { val ( res , goto ) = tuple assert ( goto != 0 ) ( res , goto - 1 ) } }以下は、上記の文法に基づいた再帰的上昇構文解析器のPrologによる実装です。
state ( S ), [ S ] --> [ S ]. state ( S0 , S ), [ S ] --> [ S0 ]./* 0. S --> E$ 1. E --> E + T 2. E --> E - T 3. E --> T 4. T --> (E) 5. T --> N 6. N --> 0 7. N --> 1 */ accept --> state ( s ([], [ e ( _ )])). r ( 1 ) --> state ( s ( Ts , [ t ( A1 ), '+' , e ( A0 )| Ss ]), s ( Ts , [ e ( A0 + A1 )| Ss ])). r ( 2 ) --> state ( s ( Ts , [ t ( A1 ), '-' , e ( A0 )| Ss ]), s ( Ts , [ e ( A0 - A1 )| Ss ])). r ( 3 ) --> state ( s ( Ts , [ t ( A )| Ss ]), s ( Ts , [ e ( A )| Ss ])). r ( 4 ) --> state ( s ( Ts , [ ')' , e ( A ), '(' | Ss ]), s ( Ts , [ t ( A )| Ss ])). r ( 5 ) --> state ( s ( Ts , [ n ( A )| Ss ]), s ( Ts , [ t ( A )| Ss ])). r ( 6 ) --> state ( s ( Ts, [ '0' | Ss ]), s ( Ts , [ n ( 0 )| Ss ])). r ( 7 ) --> state ( s ( Ts , [ '1' | Ss ]), s ( Ts , [ n ( 1 )| Ss ])). t ( T ) --> state ( s ([ T | Ts ], Ss ), s ( Ts , [ T | Ss ]))./* S --> .E$ E --> .E + T E --> .E - T E --> .T T --> .(E) T --> .N N --> .0 N --> .1 */ s0 --> t ( '(' ), s3 , s2 , s1 . s0 --> t ( '0' ), s11 , s10 , s2 , s1 . s0 --> t ( '1' ), s12 , s10 , s2 , s1 ./* S --> E.$ E --> E. + T E --> E. - T */ s1 --> accept . s1 --> t ( '+' ), s7 , s1 . s1 --> t ( '-' ), s8 , s1 ./* E --> T. */ s2 --> r ( 3 )./* T --> (.E) E --> .E + T E --> .E - T E --> .T T --> .(E) T --> .N N --> .0 N --> .1 */ s3 --> t ( '(' ), s3 , s2 , s4 . s3 --> t ( '0' ), s11 , s10 , s2 、s4 . s3 --> t ( '1' )、s12 、s10 、s2 、s4 。/* T --> (E.) E --> E .+ T E --> E .- T */ s4 --> t ( ')' ), s9 . s4 --> t ( '+' )、s7 、s4 。s4 --> t ( '-' )、s8 、s4 。/* E --> E + T. */ s5 --> r ( 1 )./* E --> E - T. */ s6 --> r ( 2 )./* E --> E + .T T --> .(E) T --> .N N --> .0 N --> .1 */ s7 --> t ( '(' ), s3 , s5 . s7 --> t ( '0' ), s11 , s10 , s5 . s7 --> t ( '1' ), s12 , s10 , s5 ./* E --> E - .T T --> .(E) T --> .N N --> .0 N --> .1 */ s8 --> t ( '(' ), s3 , s6 . s8 --> t ( '0' ), s11 , s10 , s6 . s8 --> t ( '1' ), s12 , s10 , s6 ./* T --> (E). */ s9 --> r ( 4 )。/* T --> N. */ s10 --> r ( 5 )./* N --> '0'。*/ s11 --> r ( 6 )。/* N --> '1'. */ s12 --> r ( 7 ).パーサー( Cs 、T ) :-長さ( Cs 、_ ) 、フレーズ( s0 、[ s ( Cs 、[])]、[ s ([]、[ e ( T )])])。% state(S0, S), [S] --> [S0, S]. %?- S0 = [s("(1+1)", [])|_], phrase(s0, S0, [S]), maplist(portray_clause, S0).{{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)