Estou trabalhando no algoritmo Shunting-yard , conforme descrito pela wikipedia.
A descrição do algoritmo ao lidar com operadores é a seguinte:
Se o token for um operador, o1, então:
enquanto houver um token de operador, o2, na parte superior da pilha do operador e
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,
em seguida, retire o2 da pilha do operador para a fila de saída;
pressione o1 na pilha do operador.
No entanto, eles fornecem o seguinte exemplo:
Entrada:
sin max 2 3 / 3 * 3.1415
Quando o algoritmo atinge o /
token, a descrição do que deve acontecer é a seguinte:
Token | Action | Output (in RPN) | Operator Stack
...
/ | Pop token to output | 2 3 max | / sin
...
Eles estão estalando o token função de max
desligar o stack
e colocando no queue
. De acordo com o algoritmo, isso parece significar que o token de função é um operador e tem uma precedência menor que a do /
operador.
Não há explicação se esse é o caso ou não. Então, para o Shunting-yard
algoritmo, qual é a precedência de uma função? As funções são direita ou esquerda associativas? Ou a wikipedia está incompleta / imprecisa?
fonte
sin( max( 2 3) / 3 * 3.1415)
Há dois casos diferentes a serem considerados, dependendo da sintaxe do seu idioma. Se o seu idioma usa parênteses para indicar a aplicação da função (por exemplo
f(2+1)
), a precedência é irrelevante. A função deve ser empurrada para a pilha e removida depois (no exemplo acima, o resultado é2 1 + f
). Como alternativa, você pode tratar a função como um valor e produzi-la imediatamente, e gerar uma operação de invocação de função após o parêntese próximo (que, caso contrário, deve ser tratado da mesma forma que qualquer outro parêntese), por exemplof 2 1 + $
, onde$
está a operação de invocação de função.Se seu idioma, no entanto, não usa parênteses para indicar a chamada de função, mas coloca o argumento diretamente após a função sem nenhuma pontuação especial (por exemplo
f 2 + 1
), como é aparentemente o caso do exemplo da Wikipedia, as coisas ficam um pouco mais complicadas. Observe que a expressão que acabei de dar como exemplo é ambígua: f é aplicado a 2 e 1 adicionado ao resultado ou adicionamos 2 e 1 juntos e depois chamamos f com o resultado?Novamente, existem duas abordagens. Você pode simplesmente enviar a função para a pilha do operador quando a encontrar e atribuí-la à precedência que desejar. Essa é a abordagem mais simples e, aparentemente, é o que o exemplo citado fez. Existem questões práticas, no entanto. Em primeiro lugar, como você identifica uma função? Se você tem um conjunto finito, é fácil, mas se você possui funções definidas pelo usuário, isso significa que seu analisador precisa também alimentar o seu ambiente, o que pode ficar confuso rapidamente. E como você lida com funções com vários argumentos?
Meu sentimento é que, para esse estilo de sintaxe, o uso de funções como valores mais úteis por um operador de aplicativo de função faz muito mais sentido. Então, você pode simplesmente injetar o operador do aplicativo sempre que ler um valor e a última coisa que ler também for um valor, para que você não precise de nenhuma maneira especial de dizer quais identificadores são funções. Você também pode trabalhar com expressões que retornam funções (o que é difícil ou impossível com o estilo de função como operação). E isso significa que você pode usar currying para lidar com várias funções de argumento, o que é uma simplificação maciça ao tentar lidar com elas diretamente.
A única coisa que você precisa decidir é qual é a precedência do aplicativo de funções. A escolha é sua, mas em todos os idiomas que usei que funcionam assim, ele tem sido o operador mais fortemente vinculante do idioma e tem uma associação associativa. (A única variação interessante é Haskell, que além de ter a versão fortemente vinculativa descrita, também possui um sinônimo com o símbolo
$
que é o operador mais fraco na linguagem, permitindo expressões comof 2 + 1
aplicar f a 2 ef $ 2 + 1
aplicar para todo o resto da expressão)fonte
Eu implementei as "funções no pátio de manobra" solicitadas depois de ler o pensamento original de Dijkstra (páginas 7-11 no artigo do compilador Algol 60, https://ir.cwi.nl/pub/9251 ), e necessitando de uma solução robusta, fez o seguinte:
análise:
Infix ao postfix (pátio de manobra):
Funciona perfeitamente em testes robustos e cenários complicados. No meu aplicativo (um expansor de argumentos que contém expressões de linha de comando), eu apoio funções de múltiplos argumentos e um token de vírgula "," para separá-las, e elas fluem por todo o processo.
Os exemplos se parecem com "sqrt (3 ^ 2 + 4 ^ 2)", que se torna "3 2 ^ 4 2 ^ + sqrt" e, finalmente, "5", que é o que o programa pensa ser o argumento. É bignum, então "" binomial (64, 32) / gcd (binomial (64, 32), binomial (63, 31)) "==> grandes coisas ==>" 2 "são úteis." 123456 ^ 789 " são 40.173 dígitos e o tempo mostra "avaliação = 0.000390 seg" no meu MacBookPro, tão rápido.
Eu também uso isso para expandir dados em tabelas e acho isso útil. Enfim, esta é a minha dica no caminho para lidar com cuidado com chamadas de função, vários argumentos e aninhamento profundo em um contexto de pátio de manobra de Dijkstra. Só fiz isso hoje a partir de pensamento independente. Não sei se pode haver maneiras melhores.
fonte