0
$\begingroup$

I'm a bit confused about the concept of finite state automata (FSA) and regular expression (RE) in lexical analysis. I have reading some books about compiler construction. At the part of tokenization, all the books I read talk about the regular expression first to recognize the tokens. For example, the regex below is to recognize the identifier:

([a-zA -Z] | _ | $ )([a-zA -Z0 -9] | _ | $)*

Then, they jumped to explain another technique which is finite state automata (FSA). As a result, some questions have come to my mind which are:

1- What part I should learn first? RE or FSA?.

2- Programmatically, which part should be converted to other to build the lexer? RE ==> FSA or FSA to RE.
3-Since all tokens can be recognized by regular expression, then, why we need finite state automata?.

Sorry for the to many questions, but I really can't figure out how to start. many thanks in advance.

$\endgroup$

closed as unclear what you're asking by Evil, David Richerby, fade2black, Juho, Luke Mathieson Dec 13 '17 at 12:58

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

0
$\begingroup$

A regular expression is a language used to describe a finite state automaton. It allows you to define the fsa without drawing nodes and edges all over the place. The two go hand in hand in that regard.

$\endgroup$
  • $\begingroup$ So, in lexical analyzing, do you start to know FSA or RE first ? and why ? $\endgroup$ – FSm Nov 27 '17 at 19:49
  • $\begingroup$ They are the same thing. A regular expression is a textual means to describe the structure of an fsa. $\endgroup$ – Stephan Nov 27 '17 at 19:50
  • $\begingroup$ @Stephen, to be more specific, let say i want to write a program to recognize identifier and digit tokens. What should I do first? drawing the FSA then convert it to RE or the opposite? $\endgroup$ – FSm Nov 27 '17 at 19:54
  • 1
    $\begingroup$ Typically in an academic environment, you draw the fsa first. That allows someone who is not used to thinking in that way to better see the logic. Eventually with practice, you won't need the diagrams and will be able to define the process directly with the regular expression $\endgroup$ – Stephan Nov 27 '17 at 20:11
  • 1
    $\begingroup$ That is a matter of opinion. In my experience, the two were taught at the same time. $\endgroup$ – Stephan Nov 27 '17 at 20:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.