再帰上昇パーサー

コンピュータサイエンスにおいて、再帰上昇構文解析は、テーブルではなく相互再帰関数を用いるLRパーサを実装する手法です。したがって、パーサは再帰下降構文解析と同様に、ホスト言語に直接エンコードされます。直接エンコードされたパーサは通常、テーブル駆動型パーサ[1]よりも高速です。これは、コンパイルが解釈よりも高速であるのと同じ理由です。また、再帰上昇構文解析は（名目上は）手作業で編集することも可能ですが、表形式の実装は平均的な人間にとってほぼ読みにくいものになります。

再帰上昇は、トーマス・ペンネロによる論文「Pennello, Thomas J. (1986). 「超高速LR構文解析」で初めて記述されました。1986年SIGPLANコンパイラ構築シンポジウム議事録 - SIGPLAN '86 . pp.  145– 151. doi :10.1145/12276.13326. ISBN 0897911970. S2CID  17214407。1986年に彼はLRパーサーの手作業で編集可能な実装を作るつもりはなく、アセンブリ言語で実装された保守性と効率性に優れたパーサーを作るつもりでした。この手法は後にGH Roberts [2]によって1988年に、またLeermakers、Augusteijn、Kruseman Aretz [3]によって1992年にTheoretical Computer Science誌に発表された論文で詳しく説明されました。この手法の非常に読みやすい解説はMorellとMiddleton [4]によって2003年に執筆されました。また、SperberとThiemannによるTOPLAS論文[5]にも優れた解説があります。

再帰上昇は再帰下降と統合され、再帰上昇/下降と呼ばれる手法が生まれました。この実装手法は、状態数が削減され、一部の状態がボトムアップではなくトップダウンでより直感的に記述できるため、手作業での編集が容易であるといえます。また、従来の再帰上昇に比べて、パフォーマンスがわずかに向上することもあります。[6]

まとめ

直感的に言えば、再帰上昇はLR構文解析の概念を文字通りに実装したものです。パーサー内の各関数は、単一のLRオートマトン状態を表します。各関数内では、入力ストリームから読み取られた現在のトークンに基づいて適切なアクションを選択するために、多分岐文が使用されます。トークンが識別されると、エンコードされている状態に基づいてアクションが実行されます。対象となるトークンに基づいて実行される可能性のある基本的なアクションは2つあります。

LRオートマトンには、特定の状態において実行可能な3つ目のアクションがあります。ただし、これはシフトカウンタがゼロに減算された（つまり、現在の状態が結果を処理すべきであることを示す）reduceの後にのみ実行されます。これはgotoアクションであり、本質的にはプロダクション内の非終端記号を処理するために設計されたshiftの特殊なケースです。このアクションは、マルチブランチステートメントの後に処理する必要があります。なぜなら、このアクションは、コールスタックのさらに下からreduction結果が「再出現」する場所だからです。

例

bison構文の次の文法を考えてみましょう。

式: 式 '+' 項 { $$ = $1 + $3; } | 式 '-' 項 { $$ = $1 - $3; } | 用語 { $$ = $1; }  ;用語: '(' 式 ')' { $$ = $2; } | 数値 { $$ = $1; }  ;数値: '0' { $$ = 0; } | '1' { $$ = 1; }  ;

この文法は、左再帰（非終端記号 exprにおいて）であるものの、先読みを必要としないという点でLR(0)です。また、再帰上昇法は、テーブル駆動型パーサがそのようなケースを処理するのとほぼ同様の方法で、LALR(1)の文法も処理できます（可能な先読みに基づいて衝突解決を事前に計算することによって）。

以下は、上記の文法に基づいた再帰上昇パーサーのScala実装です。

object ExprParser { private type Result = ( NonTerminal , Int ) private seal 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 term: '(' . expr ')'  *  * '(' シフトして状態 1 へ * '0' シフトして状態 2 へ * '1' シフトして状態へ3  *  * expr 状態7へ進む * t​​erm 状態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 ルール 6 (num) を使用して reduce  */ private def state2 ( in : Stream [ Char ]) = ( NTnum ( 0 , in ), 0 ) /*  * 7 num: '1' .  * * $default ルール 7 (num) を使用して reduce  */ 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 ルール 5 (term) を使用して reduce します */ private def state6 ( in : Stream [ Char ], arg1 : Int ) = ( NTterm ( arg1 , in ), 0 ) /*  * 1 expr: expr . '+' term  * 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 ,引数1                                                                                           ) 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 '(' =>状態1 (末尾)の場合'0' =>状態2 (末尾)の場合'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 (末尾) case '0' => state2 (末尾) case '1' => state3 (末尾) case c =>新しいParseException ( c )をスローします}) } case Stream () =>新しいParseExceptionをスローします                                                                                                                 } /*  * 4 term: '(' expr ')' .  *  * $default ルール 4 (term) を使用して reduce します */ private def state11 ( in : Stream [ Char ], arg1 : Int ) = ( NTterm ( arg1 , in ), 2 ) /*  * 1 expr: expr '+' term .  *  * $default ルール 1 (expr) を使用して reduce します */ private def state12 ( in : Stream [ Char ], arg1 : Int , arg2 : Int ) = ( NTexpr ( arg1 + arg2 , in ), 2 ) /*  * 2 expr: expr '-' term .  *  * $default ルール 2 (expr) を使用して reduce を実行します */ 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実装です。

状態( S )、 [ S ]  -->  [ S ]。状態( 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 )  --> 状態( s ( Ts ,  [ t ( A )| Ss ]),  s ( Ts ,  [ e ( A )| Ss ])). r ( 4 )  --> 状態( s ( Ts ,  [ ')' ,  e ( A ),  '(' | Ss ]),  s ( Ts ,  [ t ( A )| Ss ])). r ( 5 )  --> 状態( s ( Ts ,  [ n ( A )| Ss ]),  s ( Ts ,  [ t ( A )| Ss ])). r ( 6 )  --> 状態( s ( Ts,  [ '0' | Ss ]),  s ( Ts ,  [ n ( 0 )| Ss ])). r ( 7 )  --> 状態( s ( Ts ,  [ '1' | Ss ]),  s ( Ts ,  [ n ( 1 )| Ss ])). t ( T )  --> 状態( 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 ).parser ( Cs ,  T )  :-  length ( Cs ,  _ )、 phrase ( s0 、 [ s ( Cs 、 [])]、 [ s ([]、 [ e ( T )])])。% state(S0, S)、[S] --> [S0, S]。%?- S0 = [s("(1+1)", [])|_]、phrase(s0, S0, [S])、maplist(portray_clause, S0)。

参照

参考文献

  1. ^ Thomas J Penello (1986). 「非常に高速なLR構文解析」. ACM SIGPLAN Notices . 21 (7): 145– 151. doi : 10.1145/13310.13326 .
  2. ^ GH Roberts (1988). 「再帰的上昇：再帰的下降のLRアナログ」. ACM SIGPLAN Notices . 23 (8): 23– 29. doi : 10.1145/47907.47909 . S2CID  12740771.
  3. ^ リアメーカー、アウグステイン、クルーゼマン・アレッツ (1992)。 「機能的な LR パーサー」。理論的なコンピューターサイエンス。104 (2): 313–323。土井: 10.1016/0304-3975(92)90128-3。{{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)
  4. ^ Larry Morell & David Middleton (2003). 「再帰上昇構文解析」. Journal of Computing Sciences in Colleges . 第18巻、第6号、pp.  186– 201.
  5. ^ Sperber and Thiemann (2000). 「部分評価によるLRパーサの生成」. ACM Transactions on Programming Languages and Systems . 22 (2): 224– 264. doi : 10.1145/349214.349219 . S2CID  14955687.
  6. ^ John Boyland & Daniel Spiewak (2009). 「ScalaBison 再帰的上昇降下パーサージェネレーター」(PDF) . 2009年7月18日時点のオリジナル(PDF)からのアーカイブ。
「https://en.wikipedia.org/w/index.php?title=Recursive_ascent_parser&oldid=1264674624」から取得