Skip to content
Snippets Groups Projects
Select Git revision
  • 96bb9a0c984515881b04763e811445460e382587
  • master default protected
  • home_exam
3 results

HOME_EXAM.md

Blame
    • Forked from Per Lindgren / D7050E
    15 commits ahead of the upstream repository.
    HOME_EXAM.md 4.50 KiB

    Home Exam D7050E

    • Fork this repo and put your answers (or links to answers) in THIS file.

    Your repo

    Your syntax

    • Give an as complete as possible EBNF grammar for your language: ebnf.ebnf

    • Give an example that showcases all rules of your EBNF. The program should "do" something as used in the next excercise: programs/prime_gen

    Your semantics

    • Give an as complete as possible Structural Operetional Semantics (SOS) for your language: structural_operational_semantics.pdf

    • Explain (in text) what an interpretation of your example should produce, do that by dry running your given example step by step. Relate back to the SOS rules. You may skip repetions to avoid cluttering: walkthrough.md

    Your type checker

    • Give an as complete as possible set of Type Checking Rules for your language (those rules look very much like the SOS rules, but over types not values): type_checking_rules.pdf

    • Demonstrate each "type rule" by an example: programs/type_checking

    Your borrow checker

    • Give a specification for well versus ill formed borrows. (What are the rules the borrow checker should check).

      • Two parameter references may not refer to the same value, even if the references themselves are different.
      • The return lifetime must be declared.
      • The return lifetime must exist in the parameter lifetimes.
      • Two return lifetimes that are declared identical must originate from the same function's state.
      • The declared return lifetime must correspond with the lifetime of return statements, calculated by tracking references through the function's program flow.

    • Demonstrate the cases of ill formed borrows that your borrow checker is able to detect and reject: programs/bad_borrows

    Overall course goals and learning outcomes.

    Comment on the alignment of the concrete course goals (taken from the course description) to the theory presented, work You have done and knowledge You have gained. (I have put some comments in [...]).

    • Lexical analysis, syntax analysis, and translation into abstract syntax.

      • Probably the hardest part theoretically as it was important to get the data structures right here. However, it was the easiest part to program in Rust due to the strictly hierarchial structure of the program flow. Precedence climbing and figuring out in what order the parser should check for things was fun problems to work with. This was the part I had the best knowledge of beforehand.
      • The work I did here on piggybacknig meta-data to the AST proved very helpful when implementing error messages.

    • Regular expressions and grammars, context-free languages and grammars, lexer and parser generators. [Nom is lexer/parser library (and replaces the need for a generator, while lalr-pop is a classical parser generator)]

      • I basically read through the code yesterday and build my context-free grammar from that. This was very easy, as it was simply a translation of the existing code. EBNF is rather trivial, so it did not pose a problem.

    • Identifier handling and symbol table organization. Type-checking, logical inference systems. [SOS is a logical inference system]

      • I find SOS a hard concept to grasp. It works well for simple expressions and statements, but what about function calls and return statements?
      • The same is true for the Type Checking rules for statements, as my statements are type free (although they are dependent on internal type-checking).
      • The practical type-checking worked out rather well though. It's very liberating when working with the interpreter to know that the AST is type-correct.
      • Ditto for borrow-checking.

    • Intermediate representations and transformations for different languages. [LLVM is a cross language compiler infrastructure]

      • I did very little work in this area.

    • Code optimization and register allocation. Machine code generation for common architectures. [LLVM is a cross target compiler infrastructure, doing the "dirty work" of optimazation/register allocation leveraging the SSA form of the LLVM-IR]

      • I did very little work in this area.

    Comment on additional things that you have experienced and learned throughout the course.