En informática , un analizador de precedencia de operadores es un analizador de abajo hacia arriba que interpreta una gramática de precedencia de operadores . Por ejemplo, la mayoría de las calculadoras utilizan analizadores de precedencia de operadores para convertir de la notación infija legible por humanos basándose en el orden de las operaciones a un formato optimizado para la evaluación como la notación polaca inversa (RPN).
El algoritmo del patio de maniobras de Edsger Dijkstra se usa comúnmente para implementar analizadores de precedencia de operadores.
Relación con otros analizadores
Un analizador de precedencia de operadores es un analizador de reducción de cambios simple que es capaz de analizar un subconjunto de gramáticas LR (1) . Más precisamente, el analizador de precedencia de operadores puede analizar todas las gramáticas LR (1) donde dos no terminales consecutivos y épsilon nunca aparecen en el lado derecho de ninguna regla.
Los analizadores de precedencia de operadores no se utilizan con frecuencia en la práctica; sin embargo, tienen algunas propiedades que las hacen útiles dentro de un diseño más grande. En primer lugar, son lo suficientemente simples como para escribir a mano, lo que generalmente no es el caso de los analizadores sintácticos con desplazamiento-reducción a la derecha más sofisticados. En segundo lugar, se pueden escribir para consultar una tabla de operadores en tiempo de ejecución , lo que los hace adecuados para idiomas que pueden agregar o cambiar sus operadores durante el análisis. (Un ejemplo es Haskell , que permite operadores infijos definidos por el usuario con asociatividad y precedencia personalizadas; en consecuencia, se debe ejecutar un analizador de precedencia de operadores en el programa después de analizar todos los módulos referenciados).
Raku intercala un analizador sintáctico de precedencia de operadores entre dos analizadores sintácticos descendentes recursivos para lograr un equilibrio de velocidad y dinamismo. Los analizadores sintácticos C y C ++ de GCC , que son analizadores sintácticos descendentes recursivos codificados a mano, son ambos acelerados por un analizador de precedencia de operadores que puede examinar rápidamente expresiones aritméticas. Los analizadores de precedencia de operadores también están integrados en analizadores generados por compilador-compilador para acelerar notablemente el enfoque de descenso recursivo para el análisis de expresiones. [1]
Método de escalada de precedencia
El método de escalada de precedencia es un algoritmo compacto, eficiente y flexible para analizar expresiones que fue descrito por primera vez por Martin Richards y Colin Whitby-Strevens. [2]
Una gramática de expresión de notación infija en formato EBNF generalmente se verá así:
expresión :: = expresión-igualdad expresión- igualdad :: = expresión-aditiva ( ( '==' | '! =' ) expresión-aditiva ) * expresión-aditiva :: = expresión-multiplicativa ( ( '+' | '- ' ) expresión-multiplicativa ) * expresión-multiplicativa :: = primario ( ( ' * ' | ' / ' ) primario ) * primario :: = ' (' expresión ') ' | NUMBER | VARIABLE | '-' primario
Con muchos niveles de precedencia, la implementación de esta gramática con un analizador de descenso recursivo predictivo puede volverse ineficaz. Analizar un número, por ejemplo, puede requerir cinco llamadas a funciones: una para cada no terminal en la gramática hasta llegar a primaria .
Un analizador de precedencia de operadores puede hacer lo mismo de manera más eficiente. [1] La idea es que podemos dejar asociar las operaciones aritméticas siempre que encontremos operadores con la misma precedencia, pero tenemos que guardar un resultado temporal para evaluar operadores de mayor precedencia. El algoritmo que se presenta aquí no necesita una pila explícita; en su lugar, utiliza llamadas recursivas para implementar la pila.
El algoritmo no es un analizador de precedencia de operadores puro como el algoritmo del patio de maniobras de Dijkstra. Se asume que el no terminal primario se analiza en una subrutina separada, como en un analizador de descenso recursivo.
Pseudocódigo
El pseudocódigo del algoritmo es el siguiente. El analizador comienza en la función parse_expression . Los niveles de precedencia son mayores o iguales que 0.
parse_expression () return parse_expression_1 (parse_primary (), 0)
parse_expression_1 (lhs, min_precedence) lookahead : = mirar el siguiente token mientras lookahead es un operador binario cuya precedencia es> = min_precedence op : = lookahead avanzar al siguiente token rhs : = parse_primary () lookahead : = mirar el siguiente token mientras que lookahead es un operador binario cuya precedencia es mayor que op 's, o un operador asociativo a la derecha cuya prioridad es igual a op' s rhs : = parse_expression_1 ( RHS , min_precedence + 1) lookahead : = peek siguiente token LHS : = el resultado de aplicar op con operandos LHS y RHS vuelven LHS
Tenga en cuenta que en el caso de una regla de producción como esta (donde el operador solo puede aparecer una vez):
expresión-igualdad :: = expresión-aditiva ('==' | '! =') expresión-aditiva
el algoritmo debe modificarse para aceptar solo operadores binarios cuya precedencia sea> min_precedence .
Ejecución de ejemplo del algoritmo
Una ejecución de ejemplo en la expresión 2 + 3 * 4 + 5 == 19 es la siguiente. Damos precedencia 0 a expresiones de igualdad, 1 a expresiones aditivas, 2 a expresiones multiplicativas.
parse_expression_1 ( LHS = 2, min_precedence = 0)
- el token de anticipación es +, con prioridad 1. Se ingresa el ciclo while externo.
- op es + (precedencia 1) y la entrada es avanzada
- rhs es 3
- el token de anticipación es *, con precedencia 2. se ingresa el bucle while interno.
parse_expression_1 ( LHS = 3, min_precedence = 2)
- el token de anticipación es *, con precedencia 2. se ingresa el ciclo while externo.
- op es * (precedencia 2) y la entrada es avanzada
- rhs es 4
- el siguiente token es +, con precedencia 1. no se ingresa el ciclo while interno.
- lhs se asigna 3 * 4 = 12
- el siguiente token es +, con precedencia 1. el bucle externo while queda a la izquierda.
- Se devuelve 12.
- el token de anticipación es +, con precedencia 1. No se ingresa el bucle while interno.
- lhs se asigna 2 + 12 = 14
- el token de anticipación es +, con precedencia 1. el bucle externo while no se deja.
- op es + (precedencia 1) y la entrada es avanzada
- rhs es 5
- el siguiente token es ==, con precedencia 0. no se ingresa el ciclo while interno.
- lhs se asigna 14 + 5 = 19
- el siguiente token es ==, con precedencia 0. el ciclo externo while no se deja.
- op es == (precedencia 0) y la entrada es avanzada
- rhs es 19
- el siguiente token es el final de línea , que no es un operador. el bucle while interno no se ingresa.
- A lhs se le asigna el resultado de evaluar 19 == 19, por ejemplo 1 (como en el estándar C).
- el siguiente token es el final de línea , que no es un operador. el bucle exterior while queda a la izquierda.
Se devuelve 1.
Análisis de Pratt
Otro analizador de precedencia conocido como análisis sintáctico de Pratt fue descrito por primera vez por Vaughn Pratt en el artículo de 1973 "Prioridad del operador de arriba hacia abajo", [3] basado en el descenso recursivo . Aunque es anterior a la escalada por precedencia, puede verse como una generalización de la escalada por precedencia [4]
Pratt diseñó originalmente el analizador sintáctico para implementar el lenguaje de programación CGOL , y fue tratado con mucha más profundidad en una tesis de maestría bajo su supervisión. [5]
Tutoriales e implementaciones:
- Douglas Crockford basó el analizador de JavaScript en JSLint en el análisis de Pratt. [6]
- Comparación entre las implementaciones de Python de la escalada de precedencia y el análisis sintáctico de Pratt: "El análisis de Pratt y la escalada de precedencia son el mismo algoritmo" (2016) por Andy Chu
- Tutorial usando Rust : "Análisis de Pratt simple pero poderoso" (2020) por Aleksey Kladov
- Tutorial usando Python : "Análisis simple de arriba hacia abajo en Python" (2008) por Fredrik Lundh
- Tutorial con Java : "Analizadores de Pratt: análisis de expresiones más fácil" (2011) de Bob Nystrom, autor de Crafting Interpreters
Metodos alternativos
Hay otras formas de aplicar reglas de precedencia de operadores. Una es construir un árbol de la expresión original y luego aplicarle reglas de reescritura de árbol.
Estos árboles no necesitan necesariamente implementarse utilizando estructuras de datos que se usan convencionalmente para árboles. En cambio, los tokens se pueden almacenar en estructuras planas, como tablas, al construir simultáneamente una lista de prioridades que indica qué elementos procesar en qué orden.
Otro enfoque es primero poner completamente entre paréntesis la expresión, insertando varios paréntesis alrededor de cada operador, de modo que conduzcan a la precedencia correcta incluso cuando se analizan con un analizador lineal de izquierda a derecha. Este algoritmo se utilizó en el primer compilador de FORTRAN I : [7]
El compilador de Fortran I expandiría cada operador con una secuencia de paréntesis. En una forma simplificada del algoritmo, sería
- reemplazar
+
y–
con))+((
y))-((
, respectivamente;- reemplazar
*
y/
con)*(
y)/(
, respectivamente;- agregue
((
al principio de cada expresión y después de cada paréntesis izquierdo en la expresión original; y- agregue
))
al final de la expresión y antes de cada paréntesis derecho en la expresión original.Aunque no es obvio, el algoritmo era correcto y, en palabras de Knuth , "la fórmula resultante está correctamente entre paréntesis, lo crea o no". [8]
Código de ejemplo de una sencilla aplicación C que los mangos parenthesisation de operadores matemáticos básicos ( +
, -
, *
, /
, ^
, (
y )
):
#include #include int main ( int argc , char * argv []) { int i ; printf ( "((((" ); for ( i = 1 ; i ! = argc ; i ++ ) { if ( argv [ i ] && ! argv [ i ] [ 1 ]) { switch ( * argv [ i ] ) { caso '(' : printf ( "((((" ); continuar ; caso ')' : printf ( "))))" ); continuar ; caso '^' : printf ( ") ^ (" ); continuar ; caso '*' : printf ( ")) * ((" ); continuar ; caso '/' : printf ( ")) / ((" ); continuar ; caso '+' : if ( i == 1 | | strchr ( "(^ * / + -" , * argv [ i -1 ])) printf ( "+" ); si no printf ( "))) + (((" ); continuar ; caso '-' : si ( i == 1 || strchr ( "(^ * / + -" , * argv [ i -1 ])) printf ( "-" ); si no printf ( "))) - (((" ); continuar ; } } printf ( "% s" , argv [ i ]); } printf ( ")))) \ n " ); return 0 ; }
Por ejemplo, cuando se compila e invoca desde la línea de comando con parámetros
a * b + c ^ d / e
produce
((((a)) * ((b))) + (((c) ^ (d)) / ((e))))
como salida en la consola.
Una limitación de esta estrategia es que todos los operadores unarios deben tener mayor precedencia que los operadores infijos. El operador "negativo" en el código anterior tiene mayor precedencia que la exponenciación. Ejecutando el programa con esta entrada
- a ^ 2
produce esta salida
((((-a) ^ (2))))
que probablemente no sea lo que se pretende.
Referencias
- ↑ a b Harwell, Sam (29 de agosto de 2008). "Analizador de precedencia de operadores" . Wiki de ANTLR3 . Consultado el 25 de octubre de 2017 .
- ^ Richards, Martin; Whitby-Strevens, Colin (1979). BCPL: el lenguaje y su compilador . Prensa de la Universidad de Cambridge. ISBN 9780521219655.
- ^ Pratt, Vaughan. " Precedencia del operador de arriba hacia abajo ". Actas del 1er Simposio anual ACM SIGACT-SIGPLAN sobre principios de lenguajes de programación (1973).
- ^ Norvell, Theodore. "Análisis de expresiones por descendencia recursiva" . www.engr.mun.ca .
El propósito de esta publicación es [...] comenzar con la escalada de precedencia y refactorizarla para usar el patrón de comando hasta que lleguemos a un analizador de Pratt. [Este es el autor que acuñó el término "escalada de precedencia".]
- ^ Van De Vanter, Michael L. " Una prueba de formalización y corrección del sistema de lenguaje CGOL ". (Tesis de maestría). Informe técnico del Laboratorio de Ciencias de la Computación del MIT MIT-LCS-TR-147 (Cambridge, Massachusetts). 1975.
- ^ Crockford, D (21 de febrero de 2007). "Prioridad del operador de arriba hacia abajo" .
- ^ Padua, David (2000). "El compilador de Fortran I" (PDF) . Computación en ciencia e ingeniería . 2 (1): 70–75. Código Bibliográfico : 2000CSE ..... 2a..70P . doi : 10.1109 / 5992.814661 .
- ^ Knuth, Donald E. (1962). "UNA HISTORIA DE LA ESCRITURA DE COMPILADORES" . Informática y Automatización . Edmund C. Berkeley. 11 (12): 8-14.
enlaces externos
- Clarke, Keith (26 de mayo de 1992). "Re: análisis compacto recursivo-descendente de expresiones" . Consultado el 24 de enero de 2012 .
- Ejemplo de código C ++ de Keith Clarke para analizar expresiones infijas utilizando el método de escalada de precedencia
- Samelson, Klaus ; Friedrich L. Bauer (febrero de 1960). "Traducción secuencial de fórmulas". Comunicaciones de la ACM . 3 (2): 76–83. doi : 10.1145 / 366959.366968 .
- Analizador de expresión con notación infija usando listas de precedencia