Analizador de precedencia de operadores

En informática , un analizador sintáctico de precedencia de operadores es un analizador 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 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 maniobras de Edsger Dijkstra se utiliza habitualmente para implementar analizadores sintácticos de precedencia de operadores.

Relación con otros analizadores sintácticos

Un analizador sintáctico de precedencia de operadores es un analizador simple de desplazamiento-reducción capaz de analizar un subconjunto de gramáticas LR(1) . Más precisamente, este analizador puede analizar todas las gramáticas LR(1) en las que dos no terminales consecutivos y épsilon nunca aparecen en el lado derecho de ninguna regla.

Los analizadores sintácticos de precedencia de operadores no se utilizan con frecuencia en la práctica; sin embargo, poseen algunas propiedades que los hacen útiles dentro de un diseño más amplio. En primer lugar, son lo suficientemente sencillos como para escribirlos manualmente, lo que no suele ocurrir con los analizadores sintácticos de desplazamiento a la derecha y reducción más sofisticados. En segundo lugar, pueden escribirse para consultar una tabla de operadores en tiempo de ejecución , lo que los hace adecuados para lenguajes que permiten añadir o modificar operadores durante el análisis sintáctico. (Un ejemplo es Haskell , que permite operadores infijos definidos por el usuario con asociatividad y precedencia personalizadas; por consiguiente, es necesario ejecutar un analizador sintáctico de precedencia de operadores en el programa después de analizar todos los módulos referenciados).

Raku intercala un analizador de precedencia de operadores entre dos analizadores descendentes recursivos para lograr un equilibrio entre velocidad y dinamismo. Los analizadores de C y C++ de GCC , que son analizadores descendentes recursivos codificados manualmente, 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 se integran en los analizadores generados por el compilador para acelerar notablemente el enfoque descendente recursivo para el análisis de expresiones. ^{[ 1 ]}

Método de ascenso de precedencia

El método de ascenso 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 expresiones en notación infija en formato EBNF generalmente tendrá este aspecto:

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 recursivo descendente puede volverse ineficiente. Analizar un número, por ejemplo, puede requerir cinco llamadas a funciones: una por cada no terminal en la gramática hasta llegar al primario .

Un analizador de precedencia de operadores puede hacer lo mismo de manera más eficiente. ^{[ 1 ]} La idea es que podemos asociar por la izquierda las operaciones aritméticas siempre que encontremos operadores con la misma precedencia, pero debemos 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 implementarla.

El algoritmo no es un analizador sintáctico de precedencia de operadores puro como el algoritmo de patio de maniobras de Edsger Dijkstra . Presupone que el no terminal primario se analiza en una subrutina separada, como en un analizador sintáctico descendente recursivo.

Pseudocódigo

El pseudocódigo del algoritmo es el siguiente. El analizador sintáctico 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 := peek next token mientras lookahead es un operador binario cuya precedencia es >= min_precedence op := lookahead avanzar al siguiente token rhs := parse_primary () lookahead := peek next token mientras que lookahead es un operador binario cuya precedencia es mayor que op ' s, o un operador asociativo derecho cuya precedencia es igual a la de op' rhs := parse_expression_1 ( rhs , precedencia de op + (1 si la precedencia de lookahead es mayor, de lo contrario 0)) lookahead := mira el siguiente token lhs := el resultado de aplicar op con 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 solo operadores binarios cuya precedencia sea > min_precedence .

Ejemplo de ejecución del algoritmo

Un ejemplo de ejecución de la expresión 2 + 3 * 4 + 5 == 19 es el siguiente. Damos precedencia 0 a las expresiones de igualdad, 1 a las expresiones aditivas y 2 a las expresiones multiplicativas.

analizar_expresión_1 ( lhs = 2, min_precedencia = 0)

El token de anticipación es +, con precedencia 1. Se entra en el bucle while externo.
La operación es + (precedencia 1) y la entrada es avanzada.
rhs es 3
El token de anticipación es *, con precedencia 2. Se entra en el bucle while interno. parse_expression_1 ( lhs = 3, min_precedence = 2)

El token de anticipación es *, con precedencia 2. Se entra en el bucle while externo.

La operación es * (precedencia 2) y la entrada es avanzada.
rhs es 4
El siguiente token es +, con precedencia 1. No se entra en el bucle while interno.
A lh se le asigna 3*4 = 12
El siguiente token es +, con precedencia 1. El bucle while exterior queda a la izquierda.

Se devuelve 12.

El token de anticipación es +, con precedencia 1. No se entra en el bucle while interno.
A lh se le asigna 2+12 = 14
El token de anticipación es +, con precedencia 1. El bucle while externo no se deja.
La operación es + (precedencia 1) y la entrada es avanzada.
rhs es 5
El siguiente token es ==, con precedencia 0. No se entra en el bucle while interno.
A lh se le asigna 14+5 = 19
El siguiente token es ==, con precedencia 0. El bucle while externo no se abandona.
op es == (precedencia 0) y la entrada es avanzada
rhs es 19
El siguiente token es fin de línea , que no es un operador. No se entra en el bucle while interno.
A lhs se le asigna el resultado de evaluar 19 == 19, por ejemplo 1 (como en el estándar C).
El siguiente token es fin de línea , que no es un operador. El bucle while externo queda a la izquierda.

Se devuelve 1.

Análisis de Pratt

Otro analizador de precedencia conocido como análisis de 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 análisis de precedencia ascendente, puede considerarse una generalización de este último ^{[ 4 ] .}

Pratt diseñó el analizador sintáctico 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:

Douglas Crockford basó el analizador de JavaScript en JSLint en el análisis de Pratt. ^{[ 6 ]}
Comparación entre implementaciones en Python de ascenso de precedencia y análisis sintáctico de Pratt: "Pratt Parsing and Precedence Climbing Are the Same Algorithm" (2016) por Andy Chu
Tutorial sobre el uso de Rust : "Análisis de Pratt simple pero potente" (2020) por Aleksey Kladov
Tutorial con Rust : "La técnica de análisis sintáctico de Pratt" (2024) por William Rågstad
Tutorial con Python : "Análisis sintáctico descendente simple en Python" (2008) por Fredrik Lundh. Archivado el 28 de febrero de 2015 en Wayback Machine.
Tutorial con Java : "Pratt Parsers: Expression Parsing Made Easy" (2011) de Bob Nystrom, autor de Crafting Interpreters.
Implementación en C# : "Gratt: Un analizador genérico de precedencia de operadores descendente de Vaughn Pratt para .NET Standard" (una versión genérica inspirada en la implementación de Java presentada por Bob Nystrom en "Pratt Parsers: Expression Parsing Made Easy" )

Métodos alternativos

Existen otras formas de aplicar las reglas de precedencia de operadores. Una de ellas consiste en construir un árbol de la expresión original y luego aplicarle las reglas de reescritura de árboles.

Estos árboles no necesariamente tienen que implementarse utilizando las estructuras de datos convencionales para árboles. En cambio, los tokens pueden almacenarse en estructuras planas, como tablas, creando simultáneamente una lista de prioridades que indique qué elementos procesar y en qué orden.

Paréntesis completo

Otro enfoque consiste en poner primero la expresión completamente entre paréntesis, insertando varios paréntesis alrededor de cada operador, de manera que conduzcan a la precedencia correcta incluso cuando se analice con un analizador lineal de izquierda a derecha. Este algoritmo se utilizó en el compilador FORTRAN I inicial : ^{[ 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 –con ))+((y ))-((, respectivamente;
reemplazar *y /con )*(y )/(, respectivamente;
agregar ((al principio de cada expresión y después de cada paréntesis izquierdo en la expresión original; y
agregar ))al final de la expresión y antes de cada paréntesis derecho en la expresión original.
Aunque no era obvio, el algoritmo era correcto y, en palabras de Knuth , “La fórmula resultante está correctamente entre paréntesis, lo creas o no”. ^{[ 8 ]}

Código de ejemplo de una aplicación simple en C que maneja la interpolación de operadores matemáticos básicos ( +, -, *, /, ^, (y )):

#include <stdio.h> #include <string.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: ya sea primero o tenía un operador esperando un argumento secundario if ( i == 1 || strchr ( "(^*/+-" , * argv [ i -1 ])) printf ( "+" ); else printf ( ")))+(((" ); continue ; case '-' : if ( i == 1 || strchr ( "(^*/+-" , * argv [ i -1 ])) printf ( "-" ); else printf ( ")))-(((" ); continue ; } } printf ( "%s" ,argv [ i ]); } printf ( ")))) \n " ); return0 ; }

Primero, necesitas compilar tu programa. Suponiendo que tu programa está escrito en C y el código fuente se encuentra en un archivo llamado program.c, usarías el siguiente comando:

Programa gcc.c -o programa

El comando anterior le indica a gcc que compile program.c y cree un archivo 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 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. Ejecutar el programa con esta entrada

- a ^ 2

produce esta salida

((((-a)^(2))))

lo cual probablemente no es lo que se pretende.

Referencias

1 2 Harwell, Sam (2008-08-29). "Analizador de precedencia de operadores" . ANTLR3 Wiki . Recuperado el 2017-10-25 .
↑ Richards, Martin; Whitby-Strevens, Colin (1979). BCPL: el lenguaje y su compilador . Cambridge University Press. ISBN 9780521219655.
↑ Pratt, Vaughan. " Precedencia de operadores 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 mediante descenso recursivo" . www.engr.mun.ca. El propósito de esta publicación es [... comenzar] con el ascenso de precedencia y refactorizarlo para usar el patrón de comando hasta llegar a un analizador Pratt. [Este es el autor que acuñó el término "ascenso de precedencia".]
↑ Van De Vanter, Michael L. " Formalización y prueba de 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 (2007-02-21). "Precedencia del operador de arriba hacia abajo" .
↑ Padua, David (2000). "The Fortran I Compiler" (PDF) . Computing in Science & Engineering . 2 (1): 70– 75. Bibcode : 2000CSE.....2a..70P . doi : 10.1109/5992.814661 . Archivado del original (PDF) el 17 de junio de 2020. Consultado el 29 de marzo de 2016 .
↑ Knuth, Donald E. (1962). "UNA HISTORIA DE LA ESCRITURA DE COMPILADORES" . Computers and Automation . 11 (12). Edmund C. Berkeley: 8– 14.

Enlaces externos

Clarke, Keith (1992-05-26). "Re: análisis recursivo descendente compacto de expresiones" . Recuperado el 24 de enero de 2012 .
Código C++ de ejemplo de Keith Clarke para analizar expresiones infijas utilizando el método de ascenso de precedencia.
Samelson, Klaus ; Friedrich L. Bauer (febrero de 1960). "Traducción de fórmulas secuenciales" . Communications of the ACM . 3 (2): 76– 83. doi : 10.1145/366959.366968 .
Analizador sintáctico para expresiones con notación infija mediante listas de precedencia.