https://github.com/mrLSD/semantic-analyzer-rs Skip to content Toggle navigation Sign in * Product + Actions Automate any workflow + Packages Host and manage packages + Security Find and fix vulnerabilities + Codespaces Instant dev environments + Copilot Write better code with AI + Code review Manage code changes + Issues Plan and track work + Discussions Collaborate outside of code Explore + All features + Documentation + GitHub Skills + Blog * Solutions For + Enterprise + Teams + Startups + Education By Solution + CI/CD & Automation + DevOps + DevSecOps Resources + Learning Pathways + White papers, Ebooks, Webinars + Customer Stories + Partners * Open Source + GitHub Sponsors Fund open source developers + The ReadME Project GitHub community articles Repositories + Topics + Trending + Collections * Pricing Search or jump to... Search code, repositories, users, issues, pull requests... Search [ ] Clear Search syntax tips Provide feedback We read every piece of feedback, and take your input very seriously. [ ] [ ] Include my email address so I can be contacted Cancel Submit feedback Saved searches Use saved searches to filter your results more quickly Name [ ] Query [ ] To see all available qualifiers, see our documentation. Cancel Create saved search Sign in Sign up You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert {{ message }} mrLSD / semantic-analyzer-rs Public * Notifications * Fork 1 * Star 12 Semantic analyzer library for compilers written in Rust for semantic analysis of programming languages AST License MIT license 12 stars 1 fork Activity Star Notifications * Code * Issues 3 * Pull requests 1 * Actions * Wiki * Security * Insights Additional navigation options * Code * Issues * Pull requests * Actions * Wiki * Security * Insights mrLSD/semantic-analyzer-rs This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository. master Switch branches/tags [ ] Branches Tags Could not load branches Nothing to show {{ refName }} default View all branches Could not load tags Nothing to show {{ refName }} default View all tags Name already in use A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch? Cancel Create 2 branches 13 tags Code * Local * Codespaces * Clone HTTPS GitHub CLI [https://github.com/m] Use Git or checkout with SVN using the web URL. [gh repo clone mrLSD/] Work fast with our official CLI. Learn more about the CLI. * Open with GitHub Desktop * Download ZIP Sign In Required Please sign in to use Codespaces. Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Launching Xcode If nothing happens, download Xcode and try again. Launching Visual Studio Code Your codespace will open once ready. There was a problem preparing your codespace, please try again. Latest commit @mrLSD mrLSD Merge pull request #26 from mrLSD/feat/refactor-tests-struct ... 53b67a0 Dec 16, 2023 Merge pull request #26 from mrLSD/feat/refactor-tests-struct Feat: refactor tests structure organization 53b67a0 Git stats * 263 commits Files Permalink Failed to load latest commit information. Type Name Latest commit message Commit time .github Added serde to AST types. Changed CI December 9, 2023 16:43 src Extend serde tests and added serde rules December 12, 2023 17:48 tests Refactore tests: utils.rs and codec.rs December 16, 2023 13:19 .gitignore Type check for: condition_expression August 13, 2023 17:45 Cargo.toml Extend serde tests for AST December 12, 2023 08:18 LICENSE Extended README and added CI May 24, 2023 01:27 README.md Extend README, and CI. Related to #21 December 7, 2023 00:15 View code [ ] mrLSD/semantic-analyzer-rs What is the library for and what tasks does it solve Features Semantic State Tree Structure of Semantic State Tree Subset of programming languages [?] Examples Features MIT LICENSE README.md License: MIT Lints Tests Crates.io version codecov mrLSD/semantic-analyzer-rs Semantic analyzer is an open source semantic analyzer for programming languages that makes it easy to build your own efficient compilers. What is the library for and what tasks does it solve Creating a compilers for a programming language is process that involves several key stages. Most commonly it is: >[?] Lexical Analysis (Lexer): This stage involves breaking down the input stream of characters into a series of tokens. Tokens are the atomic elements of the programming language, such as identifiers, keywords, operators, etc. >[?] Syntax Analysis (Parsing): At this stage, the tokens obtained in the previous stage are grouped according to the grammar rules of the programming language. The result of this process is an Abstract Syntax Tree (AST), which represents a hierarchical structure of the code. [?] Semantic Analysis: This stage involves checking the semantic correctness of the code. This can include type checking, scope verification of variables, etc. >[?] Intermediate Code Optimization: At this stage, the compiler tries to improve the intermediate representation of the code to make it more efficient. This can include dead code elimination, expression simplification, etc. >[?] Code Generation: This is the final stage where the compiler transforms the optimized intermediate representation (IR) into machine code specific to the target architecture. This library represent Semantic Analysis stage. Features Name Binding and Scope Checking: The analyzer verifies that all variables, constants, functions are declared before they're used, and that they're used within their scope. It also checks for name collisions, where variables, constants, functions, types in the same scope have the same name. Checking Function Calls: The analyzer verifies that functions are called with the number of parameters and that the type of arguments matches the type expected by the function. Scope Rules: Checks that variables, functions, constants, types are used within their scope, and available in the visibility scope. Type Checking: The analyzer checks that operations are performed on compatible types for expressions, functions, constant, bindings. For operations in expressions. It is the process of verifying that the types of expressions are consistent with their usage in the context. Flow Control Checking: The analyzer checks that the control flow statements (if-else, loop, return, break, continue) are used correctly. Supported condition expressions and condition expression correctness check. Building the Symbol Table: For analyzing used the symbol table as data structure used by the semantic analyzer to keep track of symbols (variables, functions, constants) in the source code. Each entry in the symbol table contains the symbol's name, type, and scope related for block state, and other relevant information. Semantic State Tree The result of executing and passing stages of the semantic analyzer is: Semantic State Tree. This can be used for Intermediate Code Generation, for further passes semantic tree optimizations, linting, backend codegen (like LLVM) to target machine. Structure of Semantic State Tree * blocks state and related block state child branches. It's a basic entity for scopes: variables, blocks (function, if, loop). Especially it makes sense for expressions. This allows you to granularly separate the visibility scope and its visibility limits. In particular - all child elements can access parent elements. However, parent elements cannot access child elements, which effectively limits the visibility scope and entity usage. + variables state: block state entity, contains properties of variable in current state like: name, type, mutability, allocation, mallocation. + inner variables state: block state entity, contains inner variables names. It's useful for Intermediate Representation for codegen backends like LLVM. Where shadowed name variables should have different inner names. It means inner variables always unique. + labels state: block state entity, that contains all information about control flow labels. * Global state: contains global state of constants, declared functions and types. * State entity: contains: + Global State + Errors results + Semantic tree results All of that source data, that can be used for Intermediate Representation for next optimizations and compilers codegen. Subset of programming languages The input parameter for the analyzer is a predefined AST (abstract syntax tree). As a library for building AST and the only dependency used nom_locate - which allows getting all the necessary information about the source code, for further semantic analysis and generating relevant and informative error messages. Currently decided that the AST is a fixed structure because it is a fundamental element that defines the lexical representation of a programming language. On the other hand, it allows you to implement any subset of the programming language that matches syntax tree. It also implies a subset of lexical representations from which an AST can be generated that meets the initial requirements of the semantic analyzer. As a library for lexical analysis and source code parsing, it is recommended to use: nom is a parser combinators library. AST displays the Turing complete programming language and contains all the necessary elements for this. [?] Examples * There is the example implementation separate project Toy Codegen. The project uses the SemanticStack results and converts them into Code Generation logic. Which clearly shows the possibilities of using the results of the semantic-analyzer-rs SemanticStackContext results. LLVM is used as a backend, inkwell as a library for LLVM codegen, and compiled into an executable program. The source of data is the AST structure itself. Features Available library rust features: * codec - enable serialization and deserialization with Serde. This is especially convenient in the process of forming AST, Codegen, a serialized representation of the SemanticState. Another important nuance is that any library that implements Serde can act as a serializer codec. For example formats: json, toml, yaml, binary, and many others that can use serde library. The main entities, which apply the codec feature is: + [*] AST -[?] AST data source can be presented with serialized source. This is especially useful for designing and testing Codegen, AST data transfer pipeline, and also for use as a data generation source for AST - any programming language that can generate serialized AST data. + [*] State -[?] SematnisState can be obtained in the form of serialized data. This is especially convenient for storing state before code generation with different parameters, post-analysis, optimizations - which will allow to work with already analyzed data. + [*] SemanticStack -[?] contains a set of instructions for Codegen. Representation in serialized form may be convenient for cases: code generation without repeated semantic analysis, only based on instructions for the code generator generated by the semantic analyzer. Serialized data represented SemanticStack - opens up wide possibilities for using any third-party code generators and compilers implemented in any programming language. MIT LICENSE About Semantic analyzer library for compilers written in Rust for semantic analysis of programming languages AST Topics programming-language compiler compiler-design semantic-analysis abstract-syntax-tree compiler-construction semantic-analyzer Resources Readme License MIT license Activity Stars 12 stars Watchers 3 watching Forks 1 fork Report repository Releases 13 v0.3.3 Latest Dec 12, 2023 + 12 releases Languages * Rust 100.0% Footer (c) 2023 GitHub, Inc. Footer navigation * Terms * Privacy * Security * Status * Docs * Contact * Manage cookies * Do not share my personal information You can't perform that action at this time.