En informática , el análisis ascendente recursivo es una técnica para implementar un analizador LR que utiliza funciones recursivas mutuas en lugar de tablas. Por lo tanto, el analizador se codifica directamente en el lenguaje anfitrión de manera similar al descenso recursivo . La codificación directa generalmente produce un analizador que es más rápido que su equivalente controlado por tablas [1] por la misma razón que la compilación es más rápida que la interpretación. También es (nominalmente) posible editar manualmente un analizador ascendente recursivo, mientras que una implementación tabular es casi ilegible para el ser humano promedio.
El ascenso recursivo fue descrito por primera vez por Thomas Pennello en su artículo Pennello, Thomas J. (1986). "Very fast LR parsing". Actas del simposio SIGPLAN de 1986 sobre construcción de compiladores - SIGPLAN '86 . págs. 145–151. doi :10.1145/12276.13326. ISBN 0897911970. Número de identificación del sujeto 17214407.en 1986. No tenía intención de crear una implementación editable a mano de un analizador LR, sino más bien un analizador mantenible y eficiente implementado en lenguaje ensamblador . La técnica fue expuesta más tarde por GH Roberts [2] en 1988, así como en un artículo de Leermakers, Augusteijn, Kruseman Aretz [3] en 1992 en la revista Theoretical Computer Science . Morell y Middleton [4] escribieron una descripción extremadamente legible de la técnica en 2003. También se puede encontrar una buena exposición en un artículo de TOPLAS de Sperber y Thiemann. [5]
El ascenso recursivo también se ha fusionado con el descenso recursivo, lo que ha dado lugar a una técnica conocida como ascenso/descenso recursivo. Se podría decir que esta técnica de implementación es más fácil de editar manualmente debido a la reducción de estados y al hecho de que algunos de estos estados son más intuitivamente de arriba hacia abajo que de abajo hacia arriba. También puede producir algunas mejoras mínimas de rendimiento en comparación con el ascenso recursivo convencional. [6]
De manera intuitiva, el ascenso recursivo es una implementación literal del concepto de análisis LR . Cada función del analizador representa un único estado del autómata LR . Dentro de cada función, se utiliza una declaración de múltiples ramas para seleccionar la acción adecuada en función del token actual leído del flujo de entrada. Una vez que se ha identificado el token, se toma la acción en función del estado que se está codificando. Hay dos acciones fundamentales diferentes que se pueden tomar en función del token en cuestión:
También hay una tercera acción del autómata LR que se puede llevar a cabo en un estado determinado, pero solo después de una reducción en la que el contador de desplazamiento ha disminuido a cero (lo que indica que el estado actual debe manejar el resultado). Esta es la acción goto , que es esencialmente un caso especial de desplazamiento diseñado para manejar elementos no terminales en una producción. Esta acción debe manejarse después de la declaración de múltiples ramas, ya que aquí es donde cualquier resultado de reducción "resurgirá" desde más abajo en la pila de llamadas.
Considere la siguiente gramática en sintaxis de bisonte :
expr : expr '+' término { $$ = $1 + $3; } | expr '-' término { $$ = $1 - $3; } | término { $$ = $1; } ;término: '(' expr ')' { $$ = $2; } | num { $$ = $1; } ;número: '0' { $$ = 0; } | '1' { $$ = 1; } ;Esta gramática es LR(0) en el sentido de que es recursiva por la izquierda (en la expresión no terminal) pero no requiere ninguna búsqueda anticipada. El ascenso recursivo también es capaz de manejar gramáticas que son LALR(1) de la misma manera que los analizadores sintácticos controlados por tablas manejan tales casos (al calcular previamente las resoluciones de conflictos en función de una posible búsqueda anticipada).
La siguiente es una implementación de Scala de un analizador ascendente recursivo basado en la gramática anterior:
objeto ExprParser { tipo privado Result = ( NonTerminal , Int ) rasgo privado sellado NonTerminal { val v : Int } clase de caso privado NTexpr ( v : Int , in : Stream [ Char ]) extiende NonTerminal clase de caso privado NTterm ( v : Int , in : Stream [ Char ]) extiende NonTerminal clase de caso privado NTnum ( v : Int , in : Stream [ Char ]) extiende NonTerminal clase ParseException ( msg : String ) extiende 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 * * '(' desplaza y va al estado 1 * '0' desplaza y va al estado 2 * '1' desplaza y va al estado 3 * * expr va al estado 4 * término va al estado 5 * num va al estado 6 */ private def state0 ( in : Stream [ Char ]) = in match { case cur #:: tail => { def loop ( tuple : Result ): Result = { val ( res , goto ) = tupla 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 término: '(' . expr ')' * * '(' desplazar, y va al estado 1 * '0' desplazar, y va al estado 2 * '1' desplazar, y va al estado 3 * * expr va al estado 7 * término va al estado 5 * num va al estado 6 */ private def state1 ( in : Stream [ Char ]): Resultado = in match { case cur #:: tail => { def loop ( tuple : Resultado ): Resultado = { val ( res , goto ) = tuple if ( goto == 0 ) { loop ( res match { case NTexpr ( v , en ) => estado7 ( en , v ) caso NTterm ( v , en ) => estado5 ( en , v ) caso NTnum ( v , en ) => estado6 ( en , v ) }) } else ( res , goto - 1 ) } loop ( cur match { caso '(' => estado1 ( cola ) caso '0' => estado2 ( cola ) caso '1' => estado3 ( cola ) caso c => lanzar nueva ParseException ( c ) }) } caso Stream () => lanzar nueva ParseException } /* * 6 num: '0' . * * $reducción predeterminada usando la regla 6 (num) */ def privada estado2 ( en : Stream [ Char ]) = ( NTnum ( 0 , en ), 0 ) /* * 7 num: '1' . * * $reducción predeterminada usando la regla 7 (num) */ def privada state3 ( in : Stream [ Char ]) = ( NTnum ( 1 , in ), 0 ) /* * 0 $accept: expr . $end * 1 expr: expr . '+' término * 2 | expr . '-' término * * $end desplaza y va al estado 8 * '+' desplaza y va al estado 9 * '-' desplaza y va al estado 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: término . * * $reducción predeterminada usando la regla 3 (expr) */ private def state5 ( in : Stream [ Char ], arg1 : Int ) = ( NTexpr ( arg1 , in ), 0 ) /* * 5 término: num . * * $reducción predeterminada usando la regla 5 (término) */ private def state6 ( in : Stream [ Char ], arg1 : Int ) = ( NTterm ( arg1 , in ), 0 ) /* * 1 expr: expr . '+' término * 2 | expr . '-' término * 4 término: '(' expr . ')' * * '+' desplaza y va al estado 9 * '-' desplaza y va al estado 10 * ')' desplaza y va al estado 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 ) caso c => lanzar nueva ParseException ( c ) }) } caso Stream () => lanzar nueva ParseException } /* * 0 $aceptar: expr $fin . * * $aceptar predeterminado */ privada def estado8 ( arg1 : Int ) = ( NTexpr ( arg1 , Stream ()), 1 ) /* * 1 expr: expr '+' . término * * '(' desplaza, y va al estado 1 * '0' desplaza, y va al estado 2 * '1' desplaza, y va al estado 3 * * término va al estado 12 * num va al estado 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 ( cola ) caso '1' => estado3 ( cola ) caso c => lanzar nueva ParseException ( c ) }) } caso Stream () => lanzar nueva ParseException } /* * 2 expr: expr '-' . término * * '(' desplaza, y va al estado 1 * '0' desplaza, y va al estado 2 * '1' desplaza, y va al estado 3 * * término va al estado 13 * num va al estado 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' => estado2 ( cola ) caso '1' => estado3 ( cola ) caso c => lanzar nueva ParseException ( c ) }) } caso Stream () => lanzar nueva ParseException } /* * 4 término: '(' expr ')' . * * $reducción predeterminada usando la regla 4 (término) */ private def state11 ( in : Stream [ Char ], arg1 : Int ) = ( NTterm ( arg1 , in ), 2 ) /* * 1 expr: expr '+' término . * * $reducción predeterminada usando la regla 1 (expr) */ private def state12 ( in : Stream [ Char ], arg1 : Int , arg2 : Int ) = ( NTexpr ( arg1 + arg2 , in ), 2 ) /* * 2 expr: expr '-' término . * * $reducción predeterminada usando la regla 2 (expr) */ def privada estado13 ( en : Stream [ Char ], arg1 : Int , arg2 : Int ) = ( NTexpr ( arg1 - arg2 , en ), 2 ) def privada decremento ( tupla : Resultado ) = { val ( res , goto ) = tupla assert ( goto != 0 ) ( res , goto - 1 ) } } La siguiente es una implementación de Prolog de un analizador ascendente recursivo basado en la gramática anterior:
estado ( S ), [ S ] --> [ S ]. estado ( 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 */ aceptar --> estado ( s ([], [ e ( _ )])). r ( 1 ) --> estado ( s ( Ts , [ t ( A1 ), '+' , e ( A0 )| Ss ]), s ( Ts , [ e ( A0 + A1 )| Ss ])). r ( 2 ) --> estado ( s ( Ts , [ t ( A1 ), '-' , e ( A0 )| Ss ]), s ( Ts , [ e ( A0 - A1 )| Ss ])). r ( 3 ) --> estado ( s ( Ts , [ t ( A )| Ss ]), s ( Ts , [ e ( A )| Ss ])). r ( 4 ) --> estado ( s ( Ts , [ ')' , e ( A ), '(' | Ss ]), s ( Ts , [ t ( A )| Ss ])). r ( 5 ) --> estado ( s ( Ts , [ n ( A )| Ss ]), s ( Ts , [ t ( A )| Ss ])). r ( 6 ) --> estado ( s ( Ts, [ '0' | Ss ]), s ( Ts , [ n ( 0 )| Ss ])). r ( 7 ) --> estado ( s ( Ts , [ '1' | Ss ]), s ( Ts , [ n ( 1 )| Ss ])). t ( T ) --> estado ( 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 --> aceptar . 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 ).analizador sintáctico ( Cs , T ) :- longitud ( Cs , _ ), frase ( s0 , [ s ( Cs , [])], [ s ([], [ e ( T )])]).% estado(S0, S), [S] --> [S0, S]. %?- S0 = [s("(1+1)", [])|_], frase(s0, S0, [S]), maplist(cláusula_retrato, S0).{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )