Precedencia de la función en el algoritmo de Shunting-yard

7

Estoy trabajando a través del Algoritmo de Shunting-yard , como lo describe wikipedia.

La descripción del algoritmo cuando se trata de operadores es la siguiente:

  

Si el token es un operador, o1, entonces:

     

mientras hay un token de operador, o2, en la parte superior del operador   apilar, y cualquiera de ellos

o1 is left-associative and its precedence is less than or equal to
that of o2, or

o1 is right associative, and has precedence less than that of o2,
     

luego, extraiga o2 de la pila del operador, en la cola de salida;

     

presiona o1 en la pila del operador.

Sin embargo, dan el siguiente ejemplo:

  

Entrada: sin max 2 3 / 3 * 3.1415

Cuando el algoritmo golpea el token / , la descripción de lo que debería suceder es la siguiente:

Token |        Action       |   Output (in RPN) |   Operator Stack
...
/     | Pop token to output | 2 3 max           | / sin 
...

Están haciendo estallar la función token max del stack y colocando en el queue . De acuerdo con su algoritmo, esto parece significar que la función token es a la vez un operador y tiene una prioridad menor que la del operador / .

No hay ninguna explicación sobre si este es el caso o no. Entonces, para el algoritmo Shunting-yard , ¿cuál es la prioridad de una función? ¿Son las funciones derecha o izquierda asociativa? ¿O es wikipedia incompleta / inexacta?

    
pregunta MirroredFate 17.07.2015 - 20:06

2 respuestas

5

Creo que la respuesta directa es simplemente que las funciones no son operadores. Desde la página que has enlazado:

  

Si el token es un token de función, empújalo en la pila.

Esto es todo lo que necesita decir, ya que el caso de la función (prefijo a postfix) es mucho más simple que el caso del operador (infijo a postfix).

Para las preguntas de seguimiento: las nociones de precedencia y asociatividad solo son necesarias debido a la ambigüedad hereditaria en cualquier expresión con múltiples operadores de infijo. Los tokens de funciones ya están usando la notación de prefijo, por lo que simplemente no tienen ese problema. No necesita saber si sin o max tiene "mayor prioridad" para determinar que max debe evaluarse primero; Ya está claro del orden de los tokens. Es por eso que las computadoras prefieren comenzar con la notación pre / postfix, y porque tenemos este algoritmo para convertir infijo en pre / postfix.

Es necesario tener algún tipo de regla sobre dónde comienzan y terminan los argumentos de una función cuando no hay paréntesis, por lo que podría decir que las funciones "tienen prioridad" sobre los operadores o viceversa. Pero a diferencia de los operadores de infijo, una sola regla consistente para todas las funciones es suficiente para hacer que sus composiciones sean completamente inequívocas.

    
respondido por el Ixrec 17.07.2015 - 22:45
1

Hay dos casos diferentes a considerar, dependiendo de la sintaxis de su idioma. Si su idioma usa paréntesis para indicar la aplicación de la función (por ejemplo, f(2+1) ), la prioridad es irrelevante. La función se debe empujar en la pila y se saca después (para el ejemplo anterior, el resultado es 2 1 + f ). Alternativamente, puede tratar la función como un valor y generarla inmediatamente, y generar una operación de invocación de la función después del paréntesis de cierre (que, de lo contrario, debería tratarse igual que cualquier otro paréntesis), por ejemplo, f 2 1 + $ , donde $ es la función Operación de invocación.

Sin embargo, si su idioma no usa paréntesis para indicar la invocación de la función, sino que coloca el argumento directamente después de la función sin ninguna puntuación especial (por ejemplo, f 2 + 1 ), como aparentemente es el caso para el ejemplo de Wikipedia, entonces las cosas son Un poco más complicado. Tenga en cuenta que la expresión que acabo de dar es un ejemplo ambiguo: se aplica f a 2 y 1 agregado al resultado, o agregamos 2 y 1 juntos y luego llamamos a f con el resultado?

De nuevo, hay dos enfoques. Simplemente puede empujar la función a la pila de operadores cuando la encuentre y asignarla cualquier prioridad que desee. Este es el enfoque más simple, y aparentemente es lo que ha hecho el ejemplo citado. Hay cuestiones prácticas, sin embargo. En primer lugar, ¿cómo se identifica una función? Si tiene un conjunto finito, es fácil, pero si tiene funciones definidas por el usuario, esto significa que su analizador también necesita retroalimentación en su entorno, que puede ensuciarse rápidamente. ¿Y cómo manejas las funciones con múltiples argumentos?

Mi sensación es que para este estilo de sintaxis, usar las funciones como valores que son más prácticos para un operador de aplicaciones de función tiene mucho más sentido. Luego, puede simplemente inyectar el operador de la aplicación cada vez que lea un valor y lo último que leyó también fue un valor, por lo que no necesita ninguna forma especial de indicar qué identificadores son funciones. También puede trabajar con expresiones que devuelven funciones (lo cual es difícil o imposible con el estilo de función como operación). Y esto significa que puede usar el curry para manejar múltiples funciones de argumento, lo cual es una simplificación masiva al tratar de manejarlas directamente.

Lo único que debe decidir entonces es cuál es la prioridad de la aplicación de función. La elección depende de usted, pero en todos los idiomas que he usado que funcionan de esta manera, ha sido el operador con mayor vinculación en el idioma y ha sido asociativo. (La única variación interesante es Haskell, que además de tener la versión fuertemente vinculante descrita, también tiene un sinónimo con el símbolo $ , que es el operador de enlace más débil en el idioma, permitiendo que se apliquen expresiones como f 2 + 1 f a 2 y f $ 2 + 1 para aplicarlo al resto de la expresión)

    
respondido por el Jules 04.06.2017 - 20:45

Lea otras preguntas en las etiquetas