Analyseur d'ascension récursif

En informatique , l'analyse ascendante récursive est une technique d'implémentation d'un analyseur LR qui utilise des fonctions mutuellement récursives plutôt que des tables. Ainsi, l'analyseur est directement codé dans le langage hôte de manière similaire à la descente récursive . L'encodage direct produit généralement un analyseur plus rapide que son équivalent piloté par table pour la même raison que la compilation est plus rapide que l'interprétation. Il est également (nominalement) possible d'éditer manuellement un analyseur ascendant récursif, alors qu'une implémentation tabulaire est quasiment illisible pour l'humain moyen.

L'ascension récursive a été décrite pour la première fois par Thomas Pennello dans son article Pennello, Thomas J. (1986). "Very fast LR parsing". Actes du symposium SIGPLAN 1986 sur la construction de compilateurs - SIGPLAN '86 . pp. 145–151. doi :10.1145/12276.13326. ISBN 0897911970. S2CID 17214407.en 1986. Son intention n'était pas de créer une implémentation modifiable à la main d'un analyseur LR, mais plutôt un analyseur maintenable et efficace implémenté en langage assembleur . La technique a été plus tard exposée par GH Roberts en 1988 ainsi que dans un article de Leermakers, Augusteijn, Kruseman Aretz en 1992 dans la revue Theoretical Computer Science . Une description extrêmement lisible de la technique a été écrite par Morell et Middleton .

L'ascension récursive a également été fusionnée avec la descente récursive, donnant naissance à une technique connue sous le nom d'ascension/descente récursive. Cette technique d'implémentation est sans doute plus facile à éditer manuellement en raison de la réduction des états et du fait que certains de ces états sont plus intuitivement descendants que ascendants. Elle peut également apporter quelques améliorations de performances minimales par rapport à l'ascension récursive classique.

Résumé

Intuitivement, l'ascension récursive est une implémentation littérale du concept d'analyse LR . Chaque fonction de l'analyseur représente un seul état d'automate LR . Dans chaque fonction, une instruction multibranche est utilisée pour sélectionner l'action appropriée en fonction du jeton actuel lu dans le flux d'entrée. Une fois le jeton identifié, une action est entreprise en fonction de l'état en cours d'encodage. Il existe deux actions fondamentales différentes qui peuvent être entreprises en fonction du jeton en question :

Shift - Encodé comme un appel de fonction, sautant efficacement vers un nouvel état d'automate.
Reduce - Encodé différemment selon la routine d'action sémantique pour la production concernée . Le résultat de cette routine est encapsulé dans un ADT qui est renvoyé à l'appelant. L'action de réduction doit également enregistrer le nombre de jetons qui ont été décalés avant la réduction, en renvoyant cette valeur à l'appelant avec la valeur de réduction. Ce compteur de décalage détermine à quel point de la pile d'appels la réduction doit être traitée.

Il existe également une troisième action d'automate LR qui peut être effectuée dans un état donné, mais seulement après une réduction où le compteur de décalage est descendu à zéro (indiquant que l'état actuel doit gérer le résultat). Il s'agit de l' action goto , qui est essentiellement un cas particulier de décalage conçu pour gérer les non-terminaux dans une production. Cette action doit être gérée après l'instruction multi-branches, car c'est là que les résultats de réduction « referont surface » depuis plus bas dans la pile d'appels.

Exemple

Considérez la grammaire suivante dans la syntaxe bison :

expr : expr '+' terme { $$ = $1 + $3; } | expr '-' terme { $$ = $1 - $3; } | terme { $$ = $1; } ; terme : '(' expr ')' { $$ = $2; } | num { $$ = $1; } ; nombre : '0' { $$ = 0; } | '1' { $$ = 1; } ;

Cette grammaire est LR(0) dans le sens où elle est récursive à gauche (dans le non-terminal expr ) mais ne nécessite pas de recherche anticipée. L'ascension récursive est également capable de gérer les grammaires qui sont LALR(1) de la même manière que les analyseurs pilotés par table gèrent ces cas (en précalculant les résolutions de conflit en fonction d'une recherche anticipée possible).

Ce qui suit est une implémentation Scala d'un analyseur d'ascension récursif basé sur la grammaire ci-dessus :

objet ExprParser { type privé Result = ( NonTerminal , Int ) trait privé scellé NonTerminal { val v : Int } cas privé classe NTexpr ( v : Int , in : Stream [ Char ]) étend NonTerminal cas privé classe NTterm ( v : Int , in : Stream [ Char ]) étend NonTerminal cas privé classe NTnum ( v : Int , in : Stream [ Char ]) étend NonTerminal classe ParseException ( msg : String ) étend 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  *  * '(' shift, et aller à l'état 1  * '0' shift, et aller à l'état 2  * '1' shift, et aller à l'état 3  *  * expr aller à l'état 4  * term aller à l'état 5  * num aller à l'état 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 ')'  *  * '(' shift, et aller à l'état 1  * '0' shift, et aller à l'état 2  * '1' shift, et aller à l'état 3  *  * expr aller à l'état 7  * term aller à état 5  * num aller à l'état 6  */ privé def état1 ( dans : Stream [ Char ]) : Résultat = dans match { case cur #:: tail => { def boucle ( tuple : Résultat ): Résultat = { val ( res , goto ) = tuple if ( goto == 0 ) { boucle ( 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 réduire en utilisant la règle 6 (num)  */ private def state2 ( in : Stream [ Char ]) = ( NTnum ( 0 , in ), 0 ) /*  * 7 num: '1' .  *  * $default réduire en utilisant la règle 7 (num)  */ private def state3 ( in : Stream [ Char ]) = ( NTnum ( 1 , in ), 0 ) /*  * 0 $accept : expr . $end  * 1 expr : expr . '+' terme  * 2 | expr . '-' terme  *  * $end décalage, et aller à l'état 8  * '+' décalage, et aller à l'état 9  * '-' décalage, et aller à l'état 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 réduire en utilisant la règle 3 (expr)  */ private def state5 ( in : Stream [ Char ], arg1 : Int ) = ( NTexpr ( arg1 , in ), 0 ) /*  * 5 term: num .  *  * $default réduire en utilisant la règle 5 (term)  */ private def state6 ( in : Stream [ Char ], arg1 : Int ) = ( NTterm ( arg1 , in ), 0 ) /*  * 1 expr: expr . '+' term  * 2 | expr . '-' terme  * 4 terme: '(' expr . ')'  *  * '+' décalage, et aller à l'état 9  * '-' décalage, et aller à l'état 10  * ')' décalage, et aller à l'état 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  *  * '(' shift, et aller à l'état 1  * '0' shift, et aller à l'état 2  * '1' shift, et aller à l'état 3  *  * term aller à l'état 12  * num aller à l'état 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  *  * '(' shift, et aller à l'état 1  * '0' shift, et aller à l'état 2  * '1' shift, et aller à l'état 3  *  * term aller à l'état 13  * num aller à l'état 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 ) cas '1' => état3 ( queue ) cas c => lancer une nouvelle ParseException ( c ) }) } cas Stream () => lancer une nouvelle ParseException
} 
/*  * 4 terme : '(' expr ')' .  *  * $default réduire en utilisant la règle 4 (terme)  */ private def state11 ( in : Stream [ Char ], arg1 : Int ) = ( NTterm ( arg1 , in ), 2 ) /*  * 1 expr : expr '+' terme .  *  * $default réduire en utilisant la règle 1 (expr)  */ private def state12 ( in : Stream [ Char ], arg1 : Int , arg2 : Int ) = ( NTexpr ( arg1 + arg2 , in ), 2 ) /*  * 2 expr : expr '-' terme .  *  * $default réduit en utilisant la règle 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 ) } }

Ce qui suit est une implémentation Prolog d'un analyseur d'ascension récursif basé sur la grammaire ci-dessus :

état ( S ), 
[ S ] 
--> 
[ S ]. 
état ( 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 
--> 
état ( s ([], 
[ e ( _ )])). 
r ( 1 ) 
--> 
état ( s ( Ts , 
[ t ( A1 ), 
'+' , 
e ( A0 )| Ss ]), 
s ( Ts , 
[ e ( A0 + A1 )| Ss ])). 
r ( 2 ) 
--> 
état ( s ( Ts , 
[ t ( A1 ), 
'-' , 
e ( A0 )| Ss ]), 
s ( Ts , 
[ e ( A0 - A1 )| Ss ])). 
r ( 3 ) 
--> 
état ( s ( Ts , 
[ t ( A )| Ss ]), 
s ( Ts , 
[ e ( A )| Ss ])). 
r ( 4 ) 
--> 
état ( s ( Ts , 
[ ')' , 
e ( A ), 
'(' | Ss ]), 
s ( Ts , 
[ t ( A )| Ss ])). 
r ( 5 ) 
--> 
état ( s ( Ts , 
[ n ( A )| Ss ]), 
s ( Ts , 
[ t ( A )| Ss ])). 
r ( 6 ) 
--> 
état ( s ( Ts, 
[ '0' | Ss ]), 
s ( Ts , 
[ n ( 0 )| Ss ])). 
r ( 7 ) 
--> 
état ( s ( Ts , 
[ '1' | Ss ]), 
s ( Ts , 
[ n ( 1 )| Ss ])). 
t ( T ) 
--> 
état ( 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 
--> 
accepte . 
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 ).
analyseur ( Cs , 
T ) 
:- 
longueur ( Cs , 
_ ), 
phrase ( s0 , 
[ s ( Cs , 
[])], 
[ s ([], 
[ e ( T )])]).
% état(S0, S), [S] --> [S0, S]. 
%?- S0 = [s("(1+1)", [])|_], phrase(s0, S0, [S]), maplist(portray_clause, S0).