+- Sinisterly (https://sinister.ly)
+-- Forum: Coding (https://sinister.ly/Forum-Coding)
+--- Forum: Coding (https://sinister.ly/Forum-Coding--71)
+--- Thread: [Compiler] - Lexical Analysis (/Thread-Compiler-Lexical-Analysis)
Pages:
1
2
[Compiler] - Lexical Analysis - TheUninvited_mybb_import15721 - 03-14-2014
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
RE: [Compiler] - Lexical Analysis - Psycho_Coder - 03-14-2014
Well you have explained the things very simply and thats good but you made it very messy. Your presentation is not good. Its not that you need to use a lot of colors but proper formatting of the the thread is important.
You wrote 1/3rd of the whole space that you could have used. The paragraphs were not distinct. Also there are several terms which may be new to many others and hence a little definition would be great, like Automaton, SymbolTable, NFA, State etc.
I would have done it the following way.
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.
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.
You wrote 1/3rd of the whole space that you could have used. The paragraphs were not distinct. Also there are several terms which may be new to many others and hence a little definition would be great, like Automaton, SymbolTable, NFA, State etc.
I would have done it the following way.
Spoiler:
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.
Also people not from CS background may not know about automation and hence terms like NFA, state tables can be explained with a little example.
Well you're a good member trying to contribute. I hope you become much better
You need any help just ask us. For further explanation please ask.
Please correct the errors if you want so that it becomes a better thread.
RE: [Compiler] - Lexical Analysis - TheUninvited_mybb_import15721 - 03-14-2014
@Psycho_Coder thank you i defiantly will message you back and forth and again like you said i am new so getting used to posting correctly will take some time, thank you very much for your positive feed back and i will correct my error's right away
RE: [Compiler] - Lexical Analysis - Psycho_Coder - 03-14-2014
Now it looks better and more readable. You see by doing this a thread becomes more appealing and reader becomes interested to read the article
RE: [Compiler] - Lexical Analysis - TheUninvited_mybb_import15721 - 03-14-2014
(03-14-2014, 08:36 PM)Psycho_Coder Wrote: Now it looks better and more readable. You see by doing this a thread becomes more appealing and reader becomes interested to read the article
Yes thank you for the feed back
RE: [Compiler] - Lexical Analysis - Psycho_Coder - 03-14-2014
You used wrong Thread tags. Its a tutorial and not a resource. Well I am editing it for now but from next time please take care. Thank you.
RE: [Compiler] - Lexical Analysis - Deque - 03-15-2014
@TheUninvited:
It is very good that you contribute a lot. So thanks for your shares. I also see that you have the ability to take criticism very well, which is something I respect in people.
Now about your paper:
The definitions for NFA and DFA are wrong (they could as well describe e.g. a turing machine). Leave them away, because properly defining them is not possible without a basic background in theoretical computer science. In spite of Psycho_Coder's suggestion I don't think you should define everything, otherwise we can only have papers here that are written for noobs, which results in seeing no quality content for the advanced users. But you can say right in the beginning that you expect a certain background knowledge, maybe give some links as well. But don't write wrong content, that is the worst of all options.
However, this is meant as introduction into lexical analysis, which means it is aimed at people that don't know about lexical analysis. So the terms that are specific for lexical analysis have to be explained and that's where your paper is lacking a lot of information. And I mean really a lot. It is hard to follow.
Some examples: The relationship to compiling is not made clear. Why do you need that to make a compiler? What phases are there when you compile? (I know the answer of these questions, but it should be explained in the paper) You even mention compiler phases as if every reader knows about them -- but how should a reader know who is completely new to lexical analysis? This is a matter of the target audience. Define the target audience before you start to write. Always compare what you have written if that's appropriate for the knowledge of your target audience. In this case we have a lot of mismatch and that renders the paper useless, because people who don't know won't understand a thing, and people who already know, don't need your paper.
Examples are lacking completely, although you write: "Let us look at an extremely simple example first". Where is this example?
To understand the relationship between token, lexem and so on, an example will help a lot too.
Quote:Let us look at examples of NFAs accepting and rejecting strings.
Where is the NFA you are talking about?
Quote:We will look at several examples of token types and their corresponding finite automata.
Again: I see not a single example.
It's like you take a book and throw out every example or picture that might help to understand things. Did you write everything on your own or did you copy some stuff? Because the latter would explain the lack of a golden thread. What are your sources? Mention them.
Quote:Scanners based on NFAs can be inefficient due to the possibility of backtracking
This needs an explanation as well, because backtracking is not inefficient per se.
Quote:x: ²y = y and y² = y.
What is this supposed to be? Maybe it is one of the examples, but it is not explained anywhere.
My final suggestion to you: Rather put more work into a few high quality papers that go in depth than throwing out a bunch of papers that are low quality.
A topic like this one is great btw. I would love to see more.
RE: [Compiler] - Lexical Analysis - Psycho_Coder - 03-15-2014
@Deque you are completely correct and I agree with everything you said. I did say him the same thing earlier and in a PM as well about giving examples, little code snippets (if possible) and how the thing is being built or driven and what are the other approaches to this subject.
I asked him to define the terms specifically because after seeing his paper I understood that his target audience is not advanced users but noobs but even for noobs the thread content is not appropriate, even I feel that he is not much experienced with compiler designing or its sub systems. Hence, I left it there and wanted him to gain experience and learn by himself.
Even his other tutorials need a few more elements to be said as complete and I have tried to make him understand that fact. I hope that he eventually learns.
Well I liked one thing about him and that is he takes criticism and understands them instead of overreacting. Reminds me of myself just about a year ago, hahahaha
If this lexical analysis is taken into concern then I think I should post a thread on the subject as I have some experience on it.
Thank you for your suggestions I learnt a few things too
RE: [Compiler] - Lexical Analysis - TheUninvited_mybb_import15721 - 03-15-2014
Yes thank you again for all your criticism even though i am very new to the forum and community it will take some time for me to really get better at releasing amazing threads and content all i can do is continue to learn from you guys who i am very fortunate for and move forward thank you very much for everything you are attempting to help me with and i will try my hardest to get better in my next tutorials @Psycho_Coder @Deque Once again Thank you i will try to work on my content as i grow in this comunity
RE: [Compiler] - Lexical Analysis - Psycho_Coder - 03-15-2014
(03-15-2014, 05:28 PM)TheUninvited Wrote: Yes thank you again for all your criticism even though i am very new to the forum and community it will take some time for me to really get better at releasing amazing threads and content all i can do is continue to learn from you guys who i am very fortunate for and move forward thank you very much for everything you are attempting to help me with and i will try my hardest to get better in my next tutorials @Psycho_Coder @Deque Once again Thank you i will try to work on my content as i grow in this comunity
Am I there for anyone who wants to learn, earlier I had the same problem but now I am different and a great credit goes to Deque, ArkPhaze and a few others and hence I will do the same and help as much as I can