Pracuję nad algorytmem Shunting-yard , opisanym przez wikipedia.
Opis algorytmu w kontaktach z operatorami jest następujący:
Jeśli token jest operatorem, o1, to:
podczas gdy na górze stosu operatora znajduje się token operatora, o2, i jedno z nich
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,
następnie zrzuć o2 ze stosu operatora do kolejki wyjściowej;
wepchnij o1 na stos operatora.
Dają jednak następujący przykład:
Wejście:
sin max 2 3 / 3 * 3.1415
Gdy algorytm uderza w /
token, opis tego, co powinno się wydarzyć, jest następujący:
Token | Action | Output (in RPN) | Operator Stack
...
/ | Pop token to output | 2 3 max | / sin
...
Są one pojawiały tokenu funkcję max
wyłączyć stack
i oddanie do queue
. Według ich algorytmu wydaje się, że oznacza to, że token funkcji jest jednocześnie operatorem i ma pierwszeństwo mniejsze niż /
operator.
Nie ma wyjaśnienia, czy tak jest. Zatem w przypadku Shunting-yard
algorytmu jaki jest priorytet funkcji? Czy funkcje są prawe czy lewe asocjacyjne? A może wikipedia jest po prostu niepełna / niedokładna?
źródło
sin( max( 2 3) / 3 * 3.1415)
if there is a left parenthesis at the top of the operator stack, then: pop the operator from the operator stack and discard it
należy dodać kolejny wiersz: jeśli teraz na górze stosu znajduje się nazwa funkcji, wyskocz ze stosu i wciśnij na wynik . Innymi słowy, lewy „(” powinien być zawsze wyświetlany wraz z nazwą funkcji, jeśli są one umieszczone razem, jak sugeruje składnia funkcji: „name(
”.W zależności od składni języka należy rozważyć dwa różne przypadki. Jeśli twój język używa nawiasów do wskazania zastosowania funkcji (np.
f(2+1)
), Wówczas pierwszeństwo nie ma znaczenia. Funkcję należy wypchnąć na stos i wyskoczyć po niej (w powyższym przykładzie wynik jest2 1 + f
). Alternatywnie możesz traktować funkcję jako wartość i wyprowadzać ją natychmiast, a następnie wywołać operację wywołania funkcji po zamkniętym nawiasie (który w przeciwnym razie powinien być traktowany tak samo jak każdy inny nawias), np.f 2 1 + $
Gdzie$
jest operacja wywołania funkcji.Jeśli jednak twój język nie używa nawiasów w celu wskazania wywołania funkcji, ale zamiast tego umieszcza argument bezpośrednio za funkcją bez specjalnej interpunkcji (np.
f 2 + 1
), Jak najwyraźniej ma to miejsce w przypadku Wikipedii, sprawy są nieco bardziej skomplikowane. Zauważ, że wyrażenie, które właśnie podałem, jest niejednoznaczne: czy f jest stosowane do 2 i 1 dodanych do wyniku, czy też dodajemy 2 i 1 razem, a następnie wywołujemy f z wynikiem?Ponownie istnieją dwa podejścia. Możesz po prostu przesunąć funkcję na stos operatora, gdy ją napotkasz, i przypisać jej dowolny priorytet. Jest to najprostsze podejście i najwyraźniej to, co zrobił cytowany przykład. Istnieją jednak problemy praktyczne. Po pierwsze, jak rozpoznać funkcję? Jeśli masz skończony zestaw, jest to łatwe, ale jeśli masz funkcje zdefiniowane przez użytkownika, oznacza to, że twój parser musi również przesyłać informacje zwrotne do twojego środowiska, które może szybko się popsuć. Jak radzisz sobie z funkcjami z wieloma argumentami?
Mam wrażenie, że dla tego stylu składni używanie funkcji jako wartości obsługiwanych przez operatora aplikacji funkcji ma o wiele większy sens. Następnie możesz po prostu wstrzyknąć operatorowi aplikacji za każdym razem, gdy czytasz wartość, a ostatnią rzeczą, którą czytasz, była również wartością, więc nie potrzebujesz żadnego specjalnego sposobu określania, które identyfikatory są funkcjami. Możesz także pracować z wyrażeniami, które zwracają funkcje (co jest trudne lub niemożliwe ze stylem funkcji jako operacji). A to oznacza, że możesz używać curry do obsługi wielu funkcji argumentów, co jest ogromnym uproszczeniem w stosunku do próby bezpośredniego obsługiwania ich.
Jedyną rzeczą, którą musisz wtedy zdecydować, jest pierwszeństwo zastosowania funkcji. Wybór należy do ciebie, ale w każdym używanym przeze mnie języku, który działa w ten sposób, był to najsilniej wiążący operator w tym języku i miał właściwą asocjację. (Jedyną interesującą odmianą jest Haskell, która oprócz opisanej silnie wiążącej wersji, ma również swój synonim z symbolem,
$
który jest najsłabiej wiążącym operatorem w języku, umożliwiając wyrażenia takie jakf 2 + 1
zastosowanie f do 2 if $ 2 + 1
zastosowanie do reszty wyrażenia)źródło
Zaimplementowałem zapytanie o „funkcje w stoczni manewrowej” po przeczytaniu oryginalnego sposobu myślenia Dijkstry (strony 7-11 w dokumencie kompilatora Algol 60, https://ir.cwi.nl/pub/9251 ) i potrzebowałem solidnego rozwiązania, ja wykonał następujące czynności:
rozbiór gramatyczny zdania:
Infix-to-postfix (plac manewrowy):
Działa doskonale w niezawodnych testach i skomplikowanych scenariuszach. W mojej aplikacji (ekspander argumentów zawierających wyrażenia w wierszu poleceń) obsługuję funkcje wielu argumentów oraz token przecinek „,”, aby je rozdzielić, i przepływają przez cały proces.
Przykłady wyglądają jak „sqrt (3 ^ 2 + 4 ^ 2)”, który staje się „3 2 ^ 4 2 ^ + sqrt” i ostatecznie „5”, co program uważa za argument. Jest bignum, więc „” dwumianowy (64, 32) / gcd (dwumianowy (64, 32), dwumianowy (63, 31)) ”==> duże rzeczy ==>„ 2 ”jest pomocne.” 123456 ^ 789 ” ma 40 173 cyfry, a czas pokazuje „ocena = 0,000390 s” na moim MacBookPro, tak szybko.
Używam tego również do rozwijania danych w tabelach i uważam to za przydatne. W każdym razie, to moja wskazówka na temat ostrożnego obchodzenia się z wywołaniami funkcji, wieloma argumentami i głębokim zagnieżdżaniem w kontekście pola manewrowego Dijkstra. Właśnie to zrobiłem dzisiaj z niezależnego myślenia. Nie wiem, czy mogą być lepsze sposoby.
źródło