En informática , un analizador sintáctico de precedencia de operadores es un analizador sintáctico ascendente que interpreta una gramática de precedencia de operadores . Por ejemplo, la mayoría de las calculadoras utilizan analizadores sintácticos de precedencia de operadores para convertir de la notación infija legible por humanos que se basa en el orden de las operaciones a un formato optimizado para la evaluación, como la notación polaca inversa (RPN).
El algoritmo de patio de maniobras de Edsger Dijkstra se utiliza comúnmente para implementar analizadores sintácticos de precedencia de operadores.
Un analizador sintáctico de precedencia de operadores es un analizador sintáctico de desplazamiento-reducción simple que es capaz de analizar un subconjunto de gramáticas LR(1) . Más precisamente, el analizador sintáctico 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 con precedencia de operadores no se utilizan a menudo en la práctica; sin embargo, tienen algunas propiedades que los hacen útiles dentro de un diseño más amplio. En primer lugar, son lo suficientemente simples como para escribirlos a mano, lo que generalmente no es el caso de los analizadores con reducción por desplazamiento 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 lenguajes que pueden agregar o cambiar sus operadores mientras analizan. (Un ejemplo es Haskell , que permite operadores infijos definidos por el usuario con asociatividad y precedencia personalizadas; en consecuencia, se debe ejecutar un analizador con precedencia de operadores en el programa después de analizar todos los módulos a los que se hace referencia).
Raku intercala un analizador de precedencia de operadores entre dos analizadores de descenso recursivo para lograr un equilibrio entre velocidad y dinamismo. Los analizadores de C y C++ de GCC , que son analizadores de descenso recursivo codificados a mano, se aceleran mediante 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 dentro de los analizadores generados por compiler-compiler para acelerar notablemente el enfoque de descenso recursivo para el análisis de expresiones. [1]
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 normalmente se verá así:
expresión :: = expresión-de-igualdad expresión-de-igualdad :: = expresión-aditiva ( ( ' == ' | '! = ' ) expresión-aditiva ) * expresión-aditiva :: = expresión-multiplicativa ( ( '+' | '-' ) expresión-multiplicativa ) * expresión-multiplicativa :: = primaria ( ( ' * ' | ' / ' ) primaria ) * primaria :: = ' ( ' expresión ' ) ' | NÚMERO | VARIABLE | '-' primaria Con muchos niveles de precedencia, implementar esta gramática con un analizador predictivo de descenso recursivo puede resultar ineficiente. Analizar un número, por ejemplo, puede requerir cinco llamadas de función: una para cada no terminal en la gramática hasta llegar a primary .
Un analizador de precedencia de operadores puede hacer lo mismo de manera más eficiente. [1] La idea es que podemos 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 cambio, utiliza llamadas recursivas para implementar la pila.
El algoritmo no es un analizador sintáctico basado únicamente en la precedencia de operadores, como el algoritmo de Dijkstra para el patio de maniobras. Supone que el no terminal primario se analiza en una subrutina independiente, como en un analizador sintáctico descendente recursivo.
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 a 0.
parse_expression() devuelve parse_expression_1(parse_primary(), 0)
parse_expression_1(lhs, min_precedence) lookahead := mirar el siguiente token mientras que 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 por la derecha cuya precedencia es igual a la de op rhs := parse_expression_1 ( rhs , precedencia de op + (1 si la precedencia de búsqueda anticipada es mayor, de lo contrario 0)) lookahead := peek next token lhs := el resultado de aplicar op con los operandos lhs y rhs return 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-de-igualdad :: = expresión-aditiva ( ' == ' | '! = ' ) expresión-aditiva El algoritmo debe modificarse para aceptar sólo operadores binarios cuya precedencia sea > min_precedence .
A continuación se muestra un ejemplo de ejecución de la expresión 2 + 3 * 4 + 5 == 19. Damos prioridad 0 a las expresiones de igualdad, 1 a las expresiones aditivas y 2 a las expresiones multiplicativas.
parse_expression_1 ( lhs = 2, min_precedence = 0)
Se devuelve 1.
Otro analizador de precedencia conocido como análisis Pratt fue descrito por primera vez por Vaughan Pratt en el artículo de 1973 "Top Down Operator Precedence", [3] basado en el descenso recursivo . Aunque es anterior al ascenso de precedencia, puede verse como una generalización del ascenso de precedencia. [4]
Pratt diseñó el analizador originalmente 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:
Existen otras formas de aplicar las reglas de precedencia de operadores. Una de ellas es crear un árbol de la expresión original y luego aplicarle reglas de reescritura de árboles.
No es necesario implementar estos árboles utilizando estructuras de datos que se usan convencionalmente para árboles. En cambio, los tokens se pueden almacenar en estructuras planas, como tablas, creando simultáneamente una lista de prioridades que indique qué elementos se deben procesar y en qué orden.
Otro enfoque consiste en poner primero entre paréntesis la expresión, insertando una cantidad de paréntesis alrededor de cada operador, de modo que lleven a la precedencia correcta incluso cuando se analicen con un analizador lineal de izquierda a derecha. Este algoritmo se utilizó en el primer compilador FORTRAN I : [7]
El compilador Fortran I expandiría cada operador con una secuencia de paréntesis. En una forma simplificada del algoritmo, sería
- reemplazar
+y–por))+((y))-((, respectivamente;- reemplazar
*y/por)*(y)/(, respectivamente;- añadir
((al principio de cada expresión y después de cada paréntesis izquierdo en la expresión original; y- añadir
))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 aplicación C simple que maneja la paréntesis de operadores matemáticos básicos ( +, -, *, /, ^, (y )):
#include <stdio.h> #include <cadena.h> // El límite del argumento de la línea de comandos es nuestro analizador léxico. int main ( int argc , char * argv []) { int i ; printf ( "((((" ); for ( i = 1 ; i != argc ; i ++ ) { // strlen(argv[i]) == 2 if ( argv [ i ] && ! argv [ i ][ 1 ]) { switch ( * argv [ i ]) { case '(' : printf ( "((((" ); continue ; case ')' : printf ( "))))" ); continue ; case '^' : printf ( ")^(" ); continue ; case '*' : printf ( "))*((" ) ; continue ; case '/' : printf ( "))/((" ); continue ; case '+' : // comprobación unaria: o bien el primero o tenía un operador que esperaba un argumento secundario if ( i == 1 || strchr ( "(^*/+-" , * argv [ i -1 ])) printf ( "+" ); de lo contrario printf ( ")))+(((" ); continuar ; caso '-' : si ( i == 1 || strchr ( "(^*/+-" , * argv [ i -1 ])) printf ( "-" ); de lo contrario printf ( ")))-(((" ); continuar ; } } printf ( "%s" ,argv [ i ]); } printf ( ")))) \n " ); devolver 0 ; }Primero, debes compilar tu programa. Suponiendo que tu programa está escrito en C y el código fuente está en un archivo llamado program.c, deberás usar el siguiente comando:
gcc programa.c -o programa
El comando anterior le dice a gcc que compile program.c y cree un ejecutable llamado program.
Comando para ejecutar el programa con parámetros, por ejemplo; a*b+c^d/e
./programa a '*' b + c '^' d / e
produce
((((a))*((b)))+(((c)^(d))/((e))))
como salida en la consola.
Una limitación de esta estrategia es que 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. Ejecutar el programa con esta entrada
- un ^ 2
produce esta salida
((((-a)^(2))))
lo cual probablemente no es lo que se pretende.
El propósito de esta publicación es [... comenzar] con el ascenso de precedencia y refactorizarlo para usar el patrón de comando hasta que lleguemos a un analizador Pratt. [Este es el autor que acuñó el término "ascenso de precedencia".]