Micro Lesson plan

     

    👉Formal Languages and Automata Theory

     About FLAT :

      Automata Theory is a branch of computer science that deals with designing abstract self-propelled computing devices that follow a predetermined sequence of operations automatically. An automaton with a finite number of states is called a Finite Automaton. This is a brief and concise tutorial that introduces the fundamental concepts of Finite Automata, Regular Languages, and Pushdown Automata before moving onto Turing machines and Decidability.

Deterministic Finite Automaton (DFA)

In DFA, for each input symbol, one can determine the state to which the machine will move. Hence, it is called Deterministic Automaton. As it has a finite number of states, the machine is called Deterministic Finite Machine or Deterministic Finite Automaton.

Formal Definition of a DFA

A DFA can be represented by a 5-tuple (Q, ∑, δ, q0, F) where −

• Q is a finite set of states.

• ∑ is a finite set of symbols called the alphabet.

• δ is the transition function where δ: Q × ∑ → Q

• q0 is the initial state from where any input is processed (q0 ∈ Q).

• F is a set of final state/states of Q (F ⊆ Q).

Graphical Representation of a DFA

A DFA is represented by digraphs called state diagram.

• The vertices represent the states.
• The arcs labeled with an input alphabet show the transitions.
• The initial state is denoted by an empty single incoming arc.
• The final state is indicated by double circles

👉Compiler Design 

      

      About Compiler design:

The compiler is software that converts a program written in a high-level language (Source Language) to low-level language (Object/Target/Machine Language). 

 

 

• Cross Compiler that runs on a machine ‘A’ and produces a code for another machine ‘B’. It is capable of creating code for a platform other than the one on which the compiler is running.
• Source-to-source Compiler or transcompiler or transpiler is a compiler that translates source code written in one programming language into the source code of another programming language.

Language processing systems (using Compiler) – 
We know a computer is a logical assembly of Software and Hardware. The hardware knows a language, that is hard for us to grasp, consequently, we tend to write programs in a high-level language, that is much less complicated for us to comprehend and maintain in thoughts. Now, these programs go through a series of transformations so that they can readily be used by machines. This is where language procedure systems come in handy. 
 

 

• High-Level Language – If a program contains #define or #include directives such as #include or #define it is called HLL. They are closer to humans but far from machines. These (#) tags are called preprocessor directives. They direct the pre-processor about what to do.
• Pre-Processor – The pre-processor removes all the #include directives by including the files called file inclusion and all the #define directives using macro expansion. It performs file inclusion, augmentation, macro-processing, etc.
• Assembly Language – It’s neither in binary form nor high level. It is an intermediate state that is a combination of machine instructions and some other useful data needed for execution.
• Assembler – For every platform (Hardware + OS) we will have an assembler. They are not universal since for each platform we have one. The output of the assembler is called an object file. Its translates assembly language to machine code.
• Interpreter – An interpreter converts high-level language into low-level machine language, just like a compiler. But they are different in the way they read the input. The Compiler in one go reads the inputs, does the processing, and executes the source code whereas the interpreter does the same line by line. Compiler scans the entire program and translates it as a whole into machine code whereas an interpreter translates the program one statement at a time. Interpreted programs are usually slower with respect to compiled ones.
• Relocatable Machine Code – It can be loaded at any point and can be run. The address within the program will be in such a way that it will cooperate with the program movement.
• Loader/Linker – It converts the relocatable code into absolute code and tries to run the program resulting in a running program or an error message (or sometimes both can happen). Linker loads a variety of object files into a single file to make it executable. Then loader loads it in memory and executes it.

Phases of a Compiler – 
There are two major phases of compilation, which in turn have many parts. Each of them takes input from the output of the previous level and works in a coordinated way. 
 

Analysis Phase – An intermediate representation is created from the given source code : 
 

1. Lexical Analyzer
2. Syntax Analyzer
3. Semantic Analyzer
4. Intermediate Code Generator

Lexical analyzer divides the program into “tokens”, Syntax analyzer recognizes “sentences” in the program using the syntax of the language and Semantic analyzer checks static semantics of each construct. Intermediate Code Generator generates “abstract” code. 
Synthesis Phase – Equivalent target program is created from the intermediate representation. It has two parts : 
 

1. Code Optimizer
2. Code Generator

Code Optimizer optimizes the abstract code, and the final Code Generator translates abstract intermediate code into specific machine instructions.