[TheUninvited_mybb_import15721]

This is just one of the topics i will be touching base on in my [Compiler] series, So Lets get started, Lexical Analysis is important when we talk about creating compilers, so i thought i would create a thread to help anyone who is looking to create a compiler of any sort understand lexical analysis better
---------------------------
Definition Table
--------------------------
Automation - the technique of making an apparatus, a process, or a system operate automatically

Symbol Table - In computer science, a symbol table is a data structure used by a language translator such as a compiler or interpreter

NFA(Nondeterministic finite automaton) - In automata theory, a nondeterministic finite automaton (NFA), or nondeterministic finite state machine, is a finite state machine that does not require input symbols for state transitions and is capable of transitioning to zero or two or more states for a given start state and input symbol

DFA(deterministic finite automaton) - In automata theory, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite state machine—is a finite state machine that accepts/rejects finite strings of symbols and only produces a unique computation (or run) of the automaton for each input string. 'Deterministic' refers to the uniqueness of the computation

finite State - A finite-state machine or finite-state automaton, or simply a state machine, is a mathematical model of computation used to design both computer programs and sequential logic circuits.

e-closures - The e-closure of a subset of states.




Lexical Analysis

It is important when we talk about creating compilers, so I thought I would create a thread to help anyone who is looking to create a compiler of any sort understand lexical analysis better.

The first phase of the compiler is the lexical analyzer, also known as the scanner, which recognizes the basic language units, called tokens.
The exact characters in a token is called its lexeme.

Tokens are classified by token types, e.g. identifiers, constant literals, strings, operators, punctuation marks, and key words. Different types of tokens may have their own semantic attributes
(or values) which must be extracted and stored in the symbol table.

The lexical analyzer may perform semantic actions to extract such values and insert them in the symbol table.

How to classify token types ?

It mainly depends on what form of input is needed by the next compiler
phase, the parser. (The parser takes a sequence of tokens as its input.)

After we decide how to classify token types, we can use one of several ways to precisely express the classification. A common method is to use a finite automaton to define all character sequences (i.e. strings) which belong to a particular token type.

We will look at several examples of token types and their corresponding finite automata. The states, the starting state, the accepting states
of a finite automaton. An accepting state is also called a final state.

Given the definitions of different token types, it is possible for a string to belong to more than one type. Such ambiguity is resolved by assigning priorities to token types.
For example: Key words have a higher priority over identifiers.

Finite automata for different token types are combined into a transition diagram for the lexical analyzer.

Following the "longest match" rule - keep scanning the next character until there is no corresponding transition. The longest string which matches an acceptance state during the scanning is the recognized token.

Semantic actions can be specified in the transition diagram (The lexical analyzer can also be used to remove comments from the program). Merging several transition diagrams into one may create the problem of nondeterminism.

A Non Deterministic finite automaton (NFA) accepts an input string x if and only if there exists some path from the start state to some accepting state, such that the edge labels along the path spell out x.

Let us look at examples of NFAs accepting and rejecting strings.

Code:

x: ²y = y and y² = y.

Scanners based on NFAs can be inefficient due to the possibility of backtracking. We study an algorithm which transform an NFA into a
DFA (deterministic finite automaton).

The intuition behind the algorithm which transforms an NFA to a DFA is factoring. Let us look at an extremely simple example first, to see the idea of factoring. The idea is formalized by identifying a set of states
which can be reached after scanning a substring.

For an NFA which contains 'e' edges, we also need to define the e-closure of a state 's', which the set of states reachable from 's' by taking e transitions. The e-closure of 's' of course includes 's' itself.



i hope this tutorial gives you some insight on lexical analysis, Next time i will touch on the subject of regular expressions thank you for reading..

Tutorial List For [Compilers]
-----------------------------------------------------------
1. Lexical Analysis
2. Parsing
3. Semantic Analysis
4. Optimization
5. Code Generation