baonguyenduy2002 / dsaassignment

DSAassignment

Assignment1:

After completing this assignment, students review and make good use of: • Designing and using recursion • Object Oriented Programming (OOP) • List data structures

Symbol table is a crucial data structure, made and maintained by compilers to trace semantics of identifiers (e.g information about name, type, scope, e.t.c). Among the stages that the compiler takes to convert source code into executable code, semantic analysis is one of the most critical stage to validate correctness of the source code, such as checking whether a variable has been declared prior to being used, or whether the assignment of a value to a variable is type matched, e.t.c. The semantic analysis stage demands the symbol table in order to trace the information required in those checks. In this assignment, students are required to implement a simulation of a record table, using list data structures.

Assignment2:

After completing this assignment, students review and make good use of: • Designing and using recursion • Object Oriented Programming (OOP) • Searching algorithms and hash data structures

Symbol table is a crucial data structure, made and maintained by compilers to trace semantics of identifiers (e.g information about name, type, scope, e.t.c). In the previous assignment, students were required to implement simulations of symbol table via list data structure. However, indexing speed for checking purpose in this kind of data structure is not efficient. Whenever the source program has plenty of variables, saved in various scopes, it will become ineffective. On the other hand, in practice, programmers often tend to use newly declared or recently used identifiers for the next command lines, making the process of indexing those identifiers becomes more popular. In this assignment, students are required to implement a simulation of a symbol table, using splay tree data structures to facilitate those disadvantages mentioned above.

Assignment3:

After completing this assignment, students review and make good use of: • Designing and using recursion • Object Oriented Programming (OOP) • Searching algorithms and hash data structures

Symbol table is a crucial data structure, made and maintained by compilers to trace semantics of identifiers (e.g information about name, type, scope, e.t.c). In the previous assignment, students were required to implement the simulations of symbol table via list and tree. To optimize searching progress, hash table is among one of the most suitable data structures. Moreover, in this assignment, students are also introduced how to build a symbol table for languages using type inference. Type inference programming languages, in general, is a programming language, in which, when declaring identifiers, it does not require explicitly declare the corresponding types. However, the way that type of an identifier is set is related to statements or expressions, in which the identifier is used. In this assignment, students are required to implement a simulation of a symbol table, using hash table data structures.