There is a wide range of tools for constructing lexical analyzers.
Lex
YACC

**A LANGUAGE FOR SPECIFYING LEXICAL
ANALYZER**

There is a wide range of tools for constructing
lexical analyzers.

Lex

YACC

Lex is a computer
program that generates lexical analyzers. Lex is commonly used with the yacc
parser generator.

**Creating a lexical analyzer**

•
First, a specification of a lexical
analyzer is prepared by creating a program lex.l in the Lex language. Then,
lex.l is run through the Lex compiler to produce a C program lex.yy.c.

•
Finally, lex.yy.c is run through the C
compiler to produce an object progra m a.out, which is the lexical analyzer
that transforms an input stream into a sequence of tokens.

**Fig1.11
Creating a lexical analyzer with lex**

**Lex Specification**

A Lex program consists of three parts:

{ definitions }

%%

{ rules }

%%

{ user subroutines }

**Definitions **include
declarations of variables, constants, and regular definitions** **

Ø
**Rules **are
statements of the form** **

p_{1}
{action_{1}}

p_{2}
{action_{2}}

…

p_{n}
{action_{n}}

where p_{i} is regular expression and action_{i}
describes what action the lexical analyzer should take

when pattern p_{i} matches a lexeme. Actions
are written in C code.

**User subroutines**are
auxiliary procedures needed by the actions. These can be compiledseparately
and loaded with the lexical analyzer.

**YACC- YET ANOTHER COMPILER-COMPILER**

Yacc provides a general
tool for describing the input to a computer program. The Yacc user specifies
the structures of his input, together with code to be invoked as each such
structure is recognized.

Yacc turns such a
specification into a subroutine that handles the input process; frequently, it
is convenient and appropriate to have most of the flow of control in the user's
application handled by this subroutine.

**Finite Automata**

Finite Automata is one
of the mathematical models that consist of a number of states and edges. It is
a transition diagram that recognizes a regular expression or grammar.

There are tow types of Finite Automata :

·
Non-deterministic Finite Automata (NFA)

·
Deterministic Finite Automata (DFA)

**Deterministic Finite Automata**

DFA is a special case of a NFA in which i) no state
has an ε-transition.

ii)
there is at most one transition from
each state on any input.

DFA has five tuples denoted by

M = {Q_{d}, Ʃ, δ, q_{0}, f_{d}}

Q_{d} – finite set of states

Ʃ
– finite set of input symbols

**Construction of DFA from regular
expression**

The following steps are involved in the construction
of DFA from regular expression:

Convert RE to NFA using Thomson’s rules

Convert NFA to DFA

Construct minimized DFA

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2021 BrainKart.com; All Rights Reserved. (BS) Developed by Therithal info, Chennai.