Yksinkertaisen skriptikielen suunnittelu ja toteutus pelimoottorien käytön tueksi
Takala, Ilkka (2024)
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:amk-202404106211
https://urn.fi/URN:NBN:fi:amk-202404106211
Tiivistelmä
Tämän opinnäytetyön tavoitteena oli tutkia tulkattujen kielten luomista ja käyttöä. Opinnäytetyön aikana tutkittiin useita erilaisia lähestymistapoja koodin kääntämiseen, jäsentämiseen ja tuottamiseen ja näistä valittiin sopivimmat menetelmät EMI-skriptikielen toteuttamiseen. Toteutettu kieli tukee lukuisia nykyaikaisten ohjelmointikielten ominaisuuksia ja sitä voidaan käyttää ohjelmien luomiseen. Kääntäjä ja suoritusympäristö luotiin puhtaina C++-kirjastoina minimaalisilla riippuvuuksilla käyttäen CMakea käännösjärjestelmänä.
Ensimmäinen askel uuden kielen luomisessa oli tutkia kielen piirteitä ja tarvittavia ominaisuuksia. Tämä vai-he käytettiin eri kielten opiskeluun ja erilaisten mahdollisten piirteiden tutkimiseen. Lopullinen kielen syntaksi vastaa C-tyyliä, ja suurin ero ominaisuuksissa on dynaaminen tyypitys ja valinnaiset tyypittömät muuttujat. Kielen jäsentäminen tehdään LALR-jäsentäjällä, joka sisältää operaattorin ensisijaisuus- ja assosiatiivisuustaulukot. Tuloksena oleva konkreettinen syntaksipuu ohitetaan ja käsitellään suoraan abstraktiksi syntaksipuuksi jo jäsentämisen aikana tarpeettomien puusolmujen välttämiseksi. LALR-jäsentäjän käyttämät tokenit noudetaan lähdekoodista käyttämällä lekseriä, joka etsii syötevirrasta ennalta määritettyjä merkkisarjoja.
EMI-virtuaaliympäristö on rekisteripohjainen virtuaalikone, joka lukee ja suorittaa kääntäjän tuottamaa tavukoodia. Kääntäjä kävelee AST:n ja luo ennalta määritetyn käskysekvenssin kullekin solmutyypille. Rekisterivaraus käyttää yksinkertaistettua lineaarista varausmallia. Käännöstulos on yksinkertainen tavukoodi, joka sisältää rekistereitä ja käskyjä 32-bittisissä arvoissa, joita tarvitaan virtuaalikoneen ohjaamiseen. Luodun koodin suorituksessa käytetään epäsuoraa suoritusta linkittämään käskyt todelliseen konekieliseen koodiin.
Luotua kieltä ja ympäristöä testattiin kirjoittamalla yksinkertainen reitinhaku A*-algoritmilla. Ympäristön suoritusteho oli odotettua parempi ja se kykeni suorittamaan reitinhaun hyväksyttävissä ajoissa. EMIScriptiä, projektin lopputuotetta, voidaan käyttää tukemaan pelimoottoreiden käyttöä asynkronisilla skripteillä ja toiminnallisella koodilla. This thesis aimed to study the creation and use of interpreted languages. During the thesis multiple differ-ent approaches to compilation, parsing, and generating of code were studied, and most suitable methods were selected for the implementation of EMI scripting language. The implemented language supports many features present in modern programming languages and can be used to create programs. The com-piler and execution environment were created as pure C++-libraries with minimal dependencies using CMake as the build system.
The first step of creating a new language was to study the needs and required features of the language. This phase was mostly done by studying languages and conducting research on different possible features. The final language syntax matches C style and the largest difference in features is dynamic typing and op-tional untyped variables. The language parsing is done with LALR-parser which includes operator prece-dence and associativity tables. The resulting concrete syntax tree is partially skipped and directly parsed into abstract syntax tree during parsing to avoid unnecessary tree nodes. Tokens for the LALR parser are retrieved from source code using a lexer that matches predefined character sequences in the input stream.
The EMI virtual environment is a register-based machine that reads and executes bytecode generated by the compiler. The compiler walks the AST and generates the predefined sequence of opcodes for each node type. Register allocation uses simplified linear allocation model. The compilation result is simple bytecode that contains registers and opcodes needed to direct the virtual machine in 32-bit values. Evalu-ation of the generated code uses indirect dispatch to map opcodes to actual machine code.
The resulting language and environment were tested by creating a simple pathfinder using A*-algorithm. The execution performance of the environment was better than expected and could execute the path-finder in suitable times. EMIScript, the final product of the project, can be used to easily augment game engines with asynchronous scripts and functional code.
Ensimmäinen askel uuden kielen luomisessa oli tutkia kielen piirteitä ja tarvittavia ominaisuuksia. Tämä vai-he käytettiin eri kielten opiskeluun ja erilaisten mahdollisten piirteiden tutkimiseen. Lopullinen kielen syntaksi vastaa C-tyyliä, ja suurin ero ominaisuuksissa on dynaaminen tyypitys ja valinnaiset tyypittömät muuttujat. Kielen jäsentäminen tehdään LALR-jäsentäjällä, joka sisältää operaattorin ensisijaisuus- ja assosiatiivisuustaulukot. Tuloksena oleva konkreettinen syntaksipuu ohitetaan ja käsitellään suoraan abstraktiksi syntaksipuuksi jo jäsentämisen aikana tarpeettomien puusolmujen välttämiseksi. LALR-jäsentäjän käyttämät tokenit noudetaan lähdekoodista käyttämällä lekseriä, joka etsii syötevirrasta ennalta määritettyjä merkkisarjoja.
EMI-virtuaaliympäristö on rekisteripohjainen virtuaalikone, joka lukee ja suorittaa kääntäjän tuottamaa tavukoodia. Kääntäjä kävelee AST:n ja luo ennalta määritetyn käskysekvenssin kullekin solmutyypille. Rekisterivaraus käyttää yksinkertaistettua lineaarista varausmallia. Käännöstulos on yksinkertainen tavukoodi, joka sisältää rekistereitä ja käskyjä 32-bittisissä arvoissa, joita tarvitaan virtuaalikoneen ohjaamiseen. Luodun koodin suorituksessa käytetään epäsuoraa suoritusta linkittämään käskyt todelliseen konekieliseen koodiin.
Luotua kieltä ja ympäristöä testattiin kirjoittamalla yksinkertainen reitinhaku A*-algoritmilla. Ympäristön suoritusteho oli odotettua parempi ja se kykeni suorittamaan reitinhaun hyväksyttävissä ajoissa. EMIScriptiä, projektin lopputuotetta, voidaan käyttää tukemaan pelimoottoreiden käyttöä asynkronisilla skripteillä ja toiminnallisella koodilla.
The first step of creating a new language was to study the needs and required features of the language. This phase was mostly done by studying languages and conducting research on different possible features. The final language syntax matches C style and the largest difference in features is dynamic typing and op-tional untyped variables. The language parsing is done with LALR-parser which includes operator prece-dence and associativity tables. The resulting concrete syntax tree is partially skipped and directly parsed into abstract syntax tree during parsing to avoid unnecessary tree nodes. Tokens for the LALR parser are retrieved from source code using a lexer that matches predefined character sequences in the input stream.
The EMI virtual environment is a register-based machine that reads and executes bytecode generated by the compiler. The compiler walks the AST and generates the predefined sequence of opcodes for each node type. Register allocation uses simplified linear allocation model. The compilation result is simple bytecode that contains registers and opcodes needed to direct the virtual machine in 32-bit values. Evalu-ation of the generated code uses indirect dispatch to map opcodes to actual machine code.
The resulting language and environment were tested by creating a simple pathfinder using A*-algorithm. The execution performance of the environment was better than expected and could execute the path-finder in suitable times. EMIScript, the final product of the project, can be used to easily augment game engines with asynchronous scripts and functional code.