{"id":2756,"date":"2020-06-13T07:07:13","date_gmt":"2020-06-13T04:07:13","guid":{"rendered":"http:\/\/demensdeum.com\/blog\/?p=2756"},"modified":"2024-12-16T22:32:27","modified_gmt":"2024-12-16T19:32:27","slug":"stack-machine","status":"publish","type":"post","link":"https:\/\/demensdeum.com\/blog\/de\/2020\/06\/13\/stack-machine\/","title":{"rendered":"Stapelmaschine und RPN"},"content":{"rendered":"<p>Angenommen, wir m\u00fcssen einen einfachen Bytecode-Interpreter implementieren. Welchen Ansatz zur Implementierung dieser Aufgabe sollten wir w\u00e4hlen?<\/p>\n<p>Datenstruktur Der Stack bietet die M\u00f6glichkeit, eine einfache Bytecode-Maschine zu implementieren. Funktionen und Implementierungen von Stack-Maschinen werden in vielen Artikeln im westlichen und inl\u00e4ndischen Internet beschrieben; ich m\u00f6chte nur erw\u00e4hnen, dass die Java Virtual Machine ein Beispiel f\u00fcr eine Stack-Maschine ist.<\/p>\n<p>Das Funktionsprinzip der Maschine ist einfach: Ein Programm mit Daten und Operationscodes (Opcodes) wird dem Eingang zugef\u00fchrt und die erforderlichen Operationen werden durch Manipulationen am Stapel implementiert. Schauen wir uns ein Beispiel-Bytecode-Programm von meiner Stack-Maschine an:<\/p>\n<div class=\"hcb_wrap\">\n<pre class=\"prism line-numbers lang-unknown\" data-lang=\"unknown\"><code>\u043fMVkcatS olleH\u041f\n \n<\/code><\/pre>\n<\/div>\n<p>Am Ausgang erhalten wir die Zeichenfolge \u201eHello StackVM\u201c. Die Stapelmaschine liest das Programm von links nach rechts und l\u00e4dt Daten Zeichen f\u00fcr Zeichen auf den Stapel, wenn ein Opcode im Symbol &#8211; implementiert den Befehl mithilfe des Stapels.<\/p>\n<p>Beispiel f\u00fcr die Implementierung einer Stack-Maschine in nodejs:<\/p>\n<p><iframe loading=\"lazy\" src=\"https:\/\/repl.it\/repls\/FloralwhiteRoundScreenscraper?lite=true\" width=\"100%\" height=\"400px\" frameborder=\"no\" scrolling=\"no\" sandbox=\"allow-forms allow-pointer-lock allow-popups allow-same-origin allow-scripts allow-modals\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<h3>Umgekehrte polnische Notation (RPN)<\/h3>\n<p> Stack -Maschinen sind auch einfach zum Implementieren von Taschenrechnern zu verwenden. Daf\u00fcr verwenden sie umgekehrte polnische Notation (Postfix -Notation). <BR \/>Beispiel einer regul\u00e4ren Infix-Notation:<br \/>2*2+3*4<\/p>\n<p>Konvertiert in RPN:<br \/>22*34*+<\/p>\n<p>Um den Postfix-Datensatz zu z\u00e4hlen, verwenden wir eine Stapelmaschine:<br \/>2&#8211; an die Spitze des Stapels (Stapel: 2)<br \/>2&#8211; an die Spitze des Stapels (Stapel: 2,2)<br \/>*&#8211; Holen Sie sich zweimal die Oberseite des Stapels, multiplizieren Sie das Ergebnis und senden Sie es an die Oberseite des Stapels (Stapel: 4)<br \/>3&#8211; an die Spitze des Stapels (Stapel: 4, 3)<br \/>4&#8211; an die Spitze des Stapels (Stapel: 4, 3, 4)<br \/>*&#8211; Holen Sie sich zweimal die Oberseite des Stapels, multiplizieren Sie das Ergebnis und senden Sie es an die Oberseite des Stapels (Stapel: 4, 12)<br \/>+&#8211; Holen Sie sich zweimal die Spitze des Stapels, addieren Sie das Ergebnis und senden Sie es an die Spitze des Stapels (Stapel: 16)<\/p>\n<p>Wie Sie sehen k\u00f6nnen &#8211; Das Ergebnis der Operationen 16 verbleibt auf dem Stapel. Es kann durch Implementierung von Stapeldruck-Opcodes gedruckt werden, zum Beispiel:<br \/>p22*34*+P<\/p>\n<p>P &#8211; Stapeldruck-Start-Opcode, p &#8211; Opcode zum Fertigstellen des Stapeldrucks und zum Senden der letzten Zeile zum Rendern.<br \/>Um arithmetische Operationen von Infix in Postfix umzuwandeln, wird der Algorithmus \u201eSorting Yard\u201c von Edsger Dijkstra verwendet. Ein Beispiel f\u00fcr die Implementierung finden Sie oben oder im Repository des NodeJS-Maschinenstack-Projekts unten.<\/p>\n<h3>Quellen<\/h3>\n<p><a href=\"https:\/\/tech.badoo.com\/ru\/article\/579\/interpretatory-bajt-kodov-svoimi-rukami\/\" target=\"_blank\" rel=\"noopener noreferrer\">https:\/ \/tech.badoo.com\/ru\/article\/579\/interpretatory-bajt-kodov-svoimi-rukami\/<\/a><br \/><a href=\"https:\/\/ru.wikipedia.org\/wiki\/\u041e\u0431\u0440\u0430\u0442\u043d\u0430\u044f_\u043f\u043e\u043b\u044c\u0441\u043a\u0430\u044f_\u0437\u0430\u043f\u0438\u0441\u044c\" target=\"_blank\" rel=\"noopener noreferrer\">https:\/\/ru.wikipedia.org\/wiki\/\u041e\u0431\u0440\u0430\u0442\u043d\u0430\u044f_\u043f\u043e\u043b\u044c\u0441\u043a\u0430\u044f_\u0437\u0430\u043f\u0438\u0441\u044c<\/a><\/p>\n<h3>Quellcode<\/h3>\n<p><a href=\"https:\/\/gitlab.com\/demensdeum\/stackvm\/\" target=\"_blank\" rel=\"noopener noreferrer\">https:\/\/gitlab.com\/demensdeum\/stackvm\/<\/a>< \/p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Angenommen, wir m\u00fcssen einen einfachen Bytecode-Interpreter implementieren. Welchen Ansatz zur Implementierung dieser Aufgabe sollten wir w\u00e4hlen? Datenstruktur Der Stack bietet die M\u00f6glichkeit, eine einfache Bytecode-Maschine zu implementieren. Funktionen und Implementierungen von Stack-Maschinen werden in vielen Artikeln im westlichen und inl\u00e4ndischen Internet beschrieben; ich m\u00f6chte nur erw\u00e4hnen, dass die Java Virtual Machine ein Beispiel f\u00fcr eine<a class=\"more-link\" href=\"https:\/\/demensdeum.com\/blog\/de\/2020\/06\/13\/stack-machine\/\">Continue reading <span class=\"screen-reader-text\">&#8220;Stapelmaschine und RPN&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[61,52],"tags":[160,157,158,159],"class_list":["post-2756","post","type-post","status-publish","format-standard","hentry","category-techie","category-tutorials","tag-bytecode","tag-datastructures","tag-stack","tag-vm","entry"],"translation":{"provider":"WPGlobus","version":"3.0.2","language":"de","enabled_languages":["en","ru","zh","de","fr","ja","pt","hi"],"languages":{"en":{"title":true,"content":true,"excerpt":false},"ru":{"title":true,"content":true,"excerpt":false},"zh":{"title":true,"content":true,"excerpt":false},"de":{"title":true,"content":true,"excerpt":false},"fr":{"title":true,"content":true,"excerpt":false},"ja":{"title":true,"content":true,"excerpt":false},"pt":{"title":true,"content":true,"excerpt":false},"hi":{"title":false,"content":false,"excerpt":false}}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/posts\/2756","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/comments?post=2756"}],"version-history":[{"count":14,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/posts\/2756\/revisions"}],"predecessor-version":[{"id":3911,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/posts\/2756\/revisions\/3911"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/media?parent=2756"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/categories?post=2756"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/tags?post=2756"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}