jwajgelt / sernick Goto Github PK

• Regex -> Regex<TAtom>
• IDfa<TState> -> IDfa<TState, TAtom>

Implement type checking.
The inputs are the AST of the program, and the result of name resolution.
The result is a mapping Expression (ASTNode) -> Type, defining the type for each expression.

The possible errors are:

• using a variable of wrong type (check assignments, operators, function calls...)

Add the type checking step to the compiler frontend

Using the action table, Parser should compute a ParseTree for a sequence of token categories given as leaves on the input.

• Factory methods:
  • static Regex.Atom(char): Regex
  • static Regex.Union(IEnumerable<Regex>): Regex
  • static Regex.Concat(IEnumerable<Regex>): Regex
  • static Regex.Star(Regex): Regex)
• Normalization
  1. X \cup X == X
  2. X \cup Y == Y \cup X
  3. (X \cup Y) \cup Z == X \cup (Y \cup Z)
  4. \empty \cup X == X
  5. \neg\empty \cup X == \neg\empty
  6. (XY)Z == X(YZ)
  7. \empty * X == X * \empty == \empty
  8. \eps * X == X * \eps == X
  9. X^^ == X^
  10. \eps^ == \empty^ = \eps
  11. \neg(\neg X) == X

Based on our Language notes in #1 , let's divide test into 8 roughly equal parts:

1. Test types and naming of types/variables/functions -- @bartlomiejbloniarz
2. Test functions -- naming, readonly arguments -- @aleksanderkatan
3. Test functions -- argument types, default value syntax @krzysztofziobro
4. Test control flow -- if/else -- @jwajgelt
5. Test Loops -- @ssalabura
6. Test comments and line separators -- @Kaliciak
7. Test blocks of code -- grouping by {} and (), introducing new scope only by {} -- @LukaszSelwa
8. Variable declaration/initialization syntax -- @dembanakh

Each part/suite should contain not less than 5 good and 5 bad examples of code (remember, we use .ser extension)

Implement Equals and GetHashCode methods for every class inheriting from Regex class (AtomRegex, StarRegex, UnionRegex, ConcatRegex).
Methods assume that Regexes are normalized and compare them structurally.

Change IInput Interface and change StringInput implementation,

IInput proposition

public interface IInput
{
    /// <summary>
    ///     Advances input to the next element.
    ///     Upon creation input is positioned on the Start location.
    /// </summary>
    /// <returns>
    ///     false if after execution input's location points to End;
    ///     true otherwise 
    /// </returns>
    bool MoveNext();
    
    void MoveTo(ILocation location);
    ILocation CurrentLocation { get; }
    
    /// <summary>
    ///     Returns the location of the first char in input.
    /// </summary>
    ILocation Start { get; }
    
    /// <summary>
    ///     Returns location after the last character in input.
    /// </summary>
    ILocation End { get; }
}

The method takes a Grammar and prepares all data needed for the constructor call:

• Converts Grammar into a DfaGrammar
• Performs an analysis of it (computes Nullable, First and Follow sets)
• Computes reversed automata of given productions

Provide implementation for visitor VariableAccessVisitor, it should (based on AST) construct VariableAccessMap which can:

• For a specified function output all it's variable accesses along with mode (Read/Write)
• Check if a function has exclusive write access to a variable

Write integration tests checking the example sernick programs checking for:

• parser errors
• name resolution errors
• type checking errors
  By passing the programs to the compiler frontend once these parts have been implemented.

Implement and test public methods of RegexDfa class.
RegexDfa should work as described in the first lecture (please see slides "Alternatywna Konstrukcja RE -> DFA")

Additionally, merge IDfaWithConfig into IDfa.

Create a skeleton hierarchy of the future AST nodes (e.g. Expression, FunctionDefinition, FunctionArgument etc.). The base class is Parser.Ast.AstNode

• Add Diagnostics and Diagnostic classes (+Severity enum)
• Separate frontend and backend stages
• Add compiler's main function
• Add ASTNode base class
• Add Grammar<TSymbol> and Production<TSymbol> classes
• Add DfaGrammar<TSymbol, TState> class
• Declare .Nullable(), .First(), and .Follow()

/* comment */
const a = 5;
/* comment */

is being parsed as a single comment (from the first char till the last)

For each type NodeType implementing ASTNode, add a method public TResult visitNodeType(NodeType node, TParam param), with the default implementation delegating to visitNodeSuperType(node, param), where NodeSuperType is the immediate supertype of NodeType in the ASTNode types' hierarchy.

• Remove whitespaces
• Pack tokens into ParseTree leaves
• Construct Parser and call the process method

While empty input produces a non-null parse tree, it is not clear what are Start and End of that tree, because there is nowhere to get them from

Test these three methods separately - i.e. for the test grammar

1. Compute NULLABLE manually
2. Test that grammar.Nullable() generates a correct set of symbols (=NULLABLE)
3. Compute FIRST(A) manually
4. Test that grammar.First(NULLABLE) generates a correct function of symbols (=FIRST(A))
5. Compute FOLLOW(A) manually
6. Test that grammar.Follow(NULLABLE, FIRST) generates a correct function of symbols (=FOLLOW(A))

Implement FuctionPreprocessVisitor which should construct a map from FunctionDefinitions (AstNode) to IFunctionContext (in the future it will provide functionalities for generating function's code).

Consult StringToRegex API and create Regular Expressions for categories needed in Sernick.
Decide how we store categories (Enum or classes inhering from abstract category class).

We need categories for:

• Keywords
• Variable identificators
• Type identificators
• Code blocks brackets
• Operators

We will probably have to decide on categories priorities (eg, that keywords have bigger priority then identificators)

Inlcude more specific details (e.g. alternative next symbols)

Once implementations of Nullable, First and Follow are completed, unskip all tests

Implement First method in Grammar.Dfa.GrammarAnalysis. It should return a Dict<Symbol, Set<Symbol>>
Details in 02-parsing.pdf lecture slides

Consult and implement API of StringToRegex class

• it should simplify the process of defining more complex regular expressions
• use Regex static methods to build RegularExpression

How to reproduce:

• Run CompilerFrontendTest.cs tests

Issue:

1. There is a production cycle Expression -> X1 -> X2 -> X3 -> Expression

Shift/reduce conflict between symbol Semicolon(;) and production X3 -> Expression | X3*BinaryOperatorPriority3*Expression

Implement and test methods ContainsEpsilon and Derivative for every class inheriting from Regex

Base abstract class Regex (in Sernick.Compiler namespace? take care of some initial folder structure as well please)

Prepare a hierarchy of CodeTree nodes such that they represent all low level operations sufficient to represent sernick's functionality (without control flow).

1. Add LexicalError : IDiagnosticItem { Start, End: ILocation }
2. Modify Lexer.Process() so that it reports any error it finds to diagnostics
3. Test Frontend
   • implement ReadFile method in Utility.FileUtility
   • create a FakeDiagnostics class, which makes checking if some specific error was reported easier
   • create a helper method, which accepts a file name (*.ser), reads its content into IInput, executes a frontend compilation pass, and returns a FakeDiagnostics object
   • using that helper method, test some small sernick programs against our compiler

1. Implement Diagnostics class
2. Implement initial frontend compilation pass
   • call Lexer
   • react to any critical (or non-critical) errors reported
3. Implement compiler's entry point in Main.cs (mind that C# doesn't require explicit main() function)
   • receive file name to be compiled
   • read file contents into IInput
   • call frontend

Add mention about true/false and Int literals

Test the implementation of Parser using simple grammars and inputs and compare the resulting ParseTree to what is expected.

Implement Follow method in Grammar.Dfa.GrammarAnalysis. It should return a Dict<Symbol, Set<Symbol>>
Details in 02-parsing.pdf lecture slides

Prepare inputs that represent hard cases in AST - > CFG conversion.

For each use of a variable x, we need to know where that variable was defined (either via a new variable binding var x, or a function parameter binding fun f(x){...}).
For each function call f() we need to know where that function was defined.

The result of the name resolution are three mappings:

• variable use -> variable declaration | function parameter
• variable assignment -> variable declaration
• function call -> function declaration

Note: the variable and function names live in the same namespace - new function declarations can shadow variable declarations from previous scopes, and the other way around. It's illegal to declare a function and a variable using the same identifier in a single scope.

Errors to be returned:

• multiple declarations of same identifier (variable or function name) in one scope
• use of undeclared identifiers
• use of a variable name as function or a function name as variable

To be implemented using the ASTVisitor, using the functional algorithm presented at the lecture.

Add the name resolution step to the compiler frontend.

Currently in our AST we have some of our variable declarations outside any function, which won't work well with our approach.
So, there is a need to somehow change AST so the whole body of the program will be treated as a function, my proposal:

• convert to AST
• wrap the whole resulting Expression into a FuctionDefinition (probably named "" [empty string])
• make new expression consisting only of main FunctionDefinition, and main FunctionCall

Tests for IDfa need to be expanded to handle new methods

• AcceptingStates
• GetTransitionsFrom(state)
• GetTransitionsTo(state)

Implement Nullable method in Grammar.Dfa.GrammarAnalysis. It should return a set of symbols
Details in 02-parsing.pdf lecture slides

Provide implementation for CallGraphVisitor so it extracts call graph from our AST

• write parse tree to AST conversion
• add the conversion to Compiler Frontend pipeline
• tests

Implement public methods and constructor of StringInput class.
Write unit tests for StringInput class

Mention that in docs and in tests (if not yet present)

The private constructor should compute the action table for parser's processing.

Implement Lexer class

• Do it according to the alternative lexer construction presented on the first lecture (RE -> DFA)
• Decide how do we deal with conflicts (prioritise categories/return every possible category for token), this will probably require to change Lexer API a bit