Pierwszeństwo funkcji w algorytmie manewrowym

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ę maxwyłączyć stacki 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-yardalgorytmu jaki jest priorytet funkcji? Czy funkcje są prawe czy lewe asocjacyjne? A może wikipedia jest po prostu niepełna / niedokładna?

Uważam, że bezpośrednią odpowiedzią jest po prostu, że funkcje nie są operatorami. Ze strony, do której linkujesz:

Jeśli token jest tokenem funkcyjnym, następnie wepchnij go na stos.

To wszystko, co trzeba powiedzieć, ponieważ przypadek funkcji (przedrostek do postfiksu) jest znacznie prostszy niż przypadek operatora (odrostek do postfiksu).

W przypadku pytań uzupełniających: Pojęcia pierwszeństwa i asocjatywności są potrzebne tylko z powodu dziedziczonej dwuznaczności w dowolnym wyrażeniu z wieloma operatorami poprawki. Tokeny funkcyjne już używają notacji prefiksowych, więc po prostu nie mają tego problemu. Nie musisz wiedzieć, czy sinczy maxma „wyższy priorytet”, aby dowiedzieć się, że maxnależy najpierw ocenić; wynika to już z kolejności tokenów. Właśnie dlatego komputery wolą na początku notację prefiksową / postfiksową i dlatego mamy ten algorytm do konwersji infixa na prefiks / postfiks.

Musisz mieć jakąś regułę, w której argumenty funkcji zaczynają się i kończą, gdy nie ma nawiasów, więc możesz powiedzieć, że funkcje „mają pierwszeństwo” przed operatorami lub odwrotnie. Jednak w przeciwieństwie do operatorów infix, jedna spójna reguła dla wszystkich funkcji wystarcza, aby ich kompozycje były całkowicie jednoznaczne.

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 jest 2 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 jak f 2 + 1zastosowanie f do 2 i f $ 2 + 1zastosowanie do reszty wyrażenia)

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:

• Naciśnij deskryptor funkcji
• Wciśnij lewy nawias początkowy argumentu „[” tak jak jego początek nawiasu podwyrażeniowego.
• Odczytaj z listy wejściowej zrównoważoną sekwencję list argumentów „(” do „)”
• Przekaż to do wyjściowego strumienia tokena
• Popchnij prawy wspornik końca argumentu „]” tak jak jego „kompensacyjny wspornik zamykający”

Infix-to-postfix (plac manewrowy):

• Dodaj kolejny stos, stos funkcji, podobnie jak stos operatora
• Podczas skanowania nazwy funkcji przesuń informację o funkcji do stosu funkcji
• Kiedy zobaczysz prawy nawias końca argumentu, pop stos funkcji na wyjście

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.