regexp_tonfa.h File Reference

Construction of a NFA from a regular expression. Thompson's et Glushkov's algorithms. More...

#include "error.h"
#include "nfa.h"
#include "nfa_intersec.h"
#include "nfa_minimization.h"
#include "regexp.h"
#include "type_boolarray.h"
#include <stdlib.h>

Go to the source code of this file.

Classes
struct	glushkov_info
	Type utilized to represent the information computed by Glushkov's algorithm from the input regular expression. More...

Functions
uint	reg_countletters (regexp *)
	Counts the number of letters in a regular expression.
glushkov_info *	reg_create_gk_emp (uint)
	Initialization of a glushkov_info for a sub-expression defining the empty language.
void	reg_gk_delete (glushkov_info *)
	Realease of a glushkov_info object.
glushkov_info *	gk_indexleaves (regexp *, uint, uint *, letter *)
	Full computation of the glushkov_info object from a regular expression.
nfa *	reg_glushkov (regexp *)
	Glushkov's algorithm.
nfa *	reg_thompson (regexp *)
	Thompson's algorithm.

Detailed Description

Construction of a NFA from a regular expression. Thompson's et Glushkov's algorithms.

Function Documentation

gk_indexleaves()

glushkov_info * gk_indexleaves	(	regexp *	exp,
		uint	size,
		uint *	i,
		letter *	map )

Full computation of the glushkov_info object from a regular expression.

The computation is recursive. The total number of letters in the complete expression must be given as input.

Remarks

The letters are renamed dynamically. Each letter is renamed by an integer. The third and fourth parameters are used for this renaming. The third one is a pointer to a counter which stores the number of letters which have already been renamed. The fourth parameter is used to return the mapping from the new names to the original letters in the expression.

Returns

The glushkov_info object.

Parameters

exp	A sub-expression of the one considered by the Glushkov's algorithm.
size	The total number of letters in the full regular expression.
i	A pointer to a counter which stores the number of letters which have already been renamed.
map	Array indexed by the letter named computed by the function. Maps each name to the original letter in the expression.

reg_countletters()

uint reg_countletters

(

regexp *

exp

)

Counts the number of letters in a regular expression.

Returns

The number of letters.

Parameters

exp	The regular expression.

reg_create_gk_emp()

glushkov_info * reg_create_gk_emp

(

uint

size

)

Initialization of a glushkov_info for a sub-expression defining the empty language.

Returns

The glushkov_info object.

Parameters

size	Total number of letters in the complete expression.

reg_gk_delete()

void reg_gk_delete

(

glushkov_info *

info

)

Realease of a glushkov_info object.

Parameters

info	The left glushkov_info object.

reg_glushkov()

nfa * reg_glushkov

(

regexp *

exp

)

Glushkov's algorithm.

Computes a NFA from a regular expression.

Remarks

Glushkov's algorithm can only handle simple regular expressions (i.e. which does not contain the intersection and complement operators). This property is checked by the algorithm and a NULL pointer is returned if it is not satisfied.

Returns

A NFA recognizing the same language as the input regular expression.

Parameters

exp	A simple regular expression.

reg_thompson()

nfa * reg_thompson

(

regexp *

expr

)

Thompson's algorithm.

Recursive computation of a NFA from a regular expression.

Remarks

Thompson's algorithm can handle arbitrary regular expressions.

Returns

A NFA recognizing the same language as the input regular expression.

Parameters

expr	A regular expression.