dfa.c File Reference

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <yaz/snprintf.h>
#include <idzebra/util.h>
#include "dfap.h"
#include "imalloc.h"

Go to the source code of this file.

Data Structures
struct	Tnode
struct	Tblock

Macros
#define	CAT   16000
#define	OR   16001
#define	STAR   16002
#define	PLUS   16003
#define	EPSILON   16004
#define	TADD   64
#define	STATE_HASH   199
#define	POSET_CHUNK   100
#define	L_LP   1
#define	L_RP   2
#define	L_CHAR   3
#define	L_CHARS   4
#define	L_ANY   5
#define	L_ALT   6
#define	L_ANYZ   7
#define	L_WILD   8
#define	L_QUEST   9
#define	L_CLOS1   10
#define	L_CLOS0   11
#define	L_END   12
#define	L_START   13

Functions
static struct Tnode *	mk_Tnode (struct DFA_parse *parse_info)
static struct Tnode *	mk_Tnode_cset (struct DFA_parse *parse_info, BSet charset)
static void	term_Tnode (struct DFA_parse *parse_info)
static void	del_followpos (struct DFA_parse *parse_info)
static void	init_pos (struct DFA_parse *parse_info)
static void	del_pos (struct DFA_parse *parse_info)
static void	mk_dfa_tran (struct DFA_parse *parse_info, struct DFA_states *dfas)
static void	add_follow (struct DFA_parse *parse_info, DFASet lastpos, DFASet firstpos)
static void	dfa_trav (struct DFA_parse *parse_info, struct Tnode *n)
static void	init_followpos (struct DFA_parse *parse_info)
static void	pr_tran (struct DFA_parse *parse_info, struct DFA_states *dfas)
static void	pr_verbose (struct DFA_parse *parse_info, struct DFA_states *dfas)
static void	pr_followpos (struct DFA_parse *parse_info)
static void	out_char (int c)
static void	lex (struct DFA_parse *parse_info)
static int	nextchar (struct DFA_parse *parse_info, int *esc)
static int	read_charset (struct DFA_parse *parse_info)
static const char *	str_char (unsigned c)
static struct Tnode *	expr_1 (struct DFA_parse *parse_info)
static struct Tnode *	expr_2 (struct DFA_parse *parse_info)
static struct Tnode *	expr_3 (struct DFA_parse *parse_info)
static struct Tnode *	expr_4 (struct DFA_parse *parse_info)
static void	do_parse (struct DFA_parse *parse_info, const char **s, struct Tnode **tnp)
static int	nextchar_set (struct DFA_parse *parse_info, int *esc)
static int	map_l_char (struct DFA_parse *parse_info)
static int	lex_sub (struct DFA_parse *parse_info)
void	dfa_parse_cmap_clean (struct DFA *d)
void	dfa_parse_cmap_new (struct DFA *d, const int *cmap)
void	dfa_parse_cmap_del (struct DFA *d, int from)
void	dfa_parse_cmap_add (struct DFA *d, int from, int to)
void	dfa_parse_cmap_thompson (struct DFA *d)
static struct DFA_parse *	dfa_parse_init (void)
static void	rm_dfa_parse (struct DFA_parse **dfap)
static struct DFA_states *	mk_dfas (struct DFA_parse *dfap, int poset_chunk)
struct DFA *	dfa_init (void)
void	dfa_anyset_includes_nl (struct DFA *dfa)
void	dfa_set_cmap (struct DFA *dfa, void *vp, const char **(*cmap)(void *vp, const char **from, int len))
int	dfa_get_last_rule (struct DFA *dfa)
int	dfa_parse (struct DFA *dfa, const char **pattern)
void	dfa_mkstate (struct DFA *dfa)
void	dfa_delete (struct DFA **dfap)

Variables
int	debug_dfa_trav = 0
int	debug_dfa_tran = 0
int	debug_dfa_followpos = 0
int	dfa_verbose = 0

Macro Definition Documentation

CAT

#define CAT   16000

Definition at line 37 of file dfa.c.

EPSILON

#define EPSILON   16004

Definition at line 41 of file dfa.c.

L_ALT

#define L_ALT   6

Definition at line 102 of file dfa.c.

L_ANY

#define L_ANY   5

Definition at line 101 of file dfa.c.

L_ANYZ

#define L_ANYZ   7

Definition at line 103 of file dfa.c.

L_CHAR

#define L_CHAR   3

Definition at line 99 of file dfa.c.

L_CHARS

#define L_CHARS   4

Definition at line 100 of file dfa.c.

L_CLOS0

#define L_CLOS0   11

Definition at line 107 of file dfa.c.

L_CLOS1

#define L_CLOS1   10

Definition at line 106 of file dfa.c.

L_END

#define L_END   12

Definition at line 108 of file dfa.c.

L_LP

#define L_LP   1

Definition at line 97 of file dfa.c.

L_QUEST

#define L_QUEST   9

Definition at line 105 of file dfa.c.

L_RP

#define L_RP   2

Definition at line 98 of file dfa.c.

L_START

#define L_START   13

Definition at line 109 of file dfa.c.

L_WILD

#define L_WILD   8

Definition at line 104 of file dfa.c.

OR

#define OR   16001

Definition at line 38 of file dfa.c.

PLUS

#define PLUS   16003

Definition at line 40 of file dfa.c.

POSET_CHUNK

#define POSET_CHUNK   100

Definition at line 64 of file dfa.c.

STAR

#define STAR   16002

Definition at line 39 of file dfa.c.

STATE_HASH

#define STATE_HASH   199

Definition at line 63 of file dfa.c.

TADD

#define TADD   64

Definition at line 62 of file dfa.c.

Function Documentation

add_follow()

static void add_follow	(	struct DFA_parse *	parse_info,
		DFASet	lastpos,
		DFASet	firstpos
	)

Definition at line 638 of file dfa.c.

References Tnode::firstpos, DFA_parse::followpos, Tnode::lastpos, DFASetElement_::next, DFA_parse::poset, union_DFASet(), and DFASetElement_::value.

Referenced by dfa_trav().

del_followpos()

static void del_followpos ( struct DFA_parse *  parse_info )

static

Definition at line 622 of file dfa.c.

References DFA_parse::followpos, and ifree().

Referenced by mk_dfas().

del_pos()

static void del_pos

(

struct DFA_parse *

parse_info

)

Definition at line 633 of file dfa.c.

References ifree(), and DFA_parse::posar.

Referenced by mk_dfas().

dfa_anyset_includes_nl()

void dfa_anyset_includes_nl

(

struct DFA *

dfa

)

Definition at line 1104 of file dfa.c.

References add_BSet(), DFA_parse::anyset, DFA_parse::charset, and DFA::parse_info.

Referenced by dict_lookup_grep().

dfa_delete()

void dfa_delete

(

struct DFA **

dfap

)

Definition at line 1158 of file dfa.c.

References ifree(), rm_dfa_parse(), and rm_DFA_states().

Referenced by actionListDel(), data1_absyn_destroy(), data1_read_absyn(), dict_lookup_grep(), lexContextDestroy(), main(), and tst().

dfa_get_last_rule()

int dfa_get_last_rule

(

struct DFA *

dfa

)

Definition at line 1116 of file dfa.c.

References DFA::parse_info, and DFA_parse::rule.

dfa_init()

struct DFA* dfa_init

(

void

)

Definition at line 1092 of file dfa.c.

References dfa_parse_cmap_thompson(), dfa_parse_init(), imalloc(), DFA::parse_info, DFA::state_info, and DFA::states.

Referenced by data1_read_absyn(), dict_lookup_grep(), lexSpecDFA(), main(), and tst().

dfa_mkstate()

void dfa_mkstate

(

struct DFA *

dfa

)

Definition at line 1148 of file dfa.c.

References mk_dfas(), DFA_states::no, DFA::no_states, DFA::parse_info, POSET_CHUNK, rm_dfa_parse(), DFA_states::sortarray, DFA::state_info, and DFA::states.

Referenced by actionListMk(), data1_read_absyn(), dict_lookup_grep(), main(), and readFileSpec().

dfa_parse()

int dfa_parse	(	struct DFA *	dfa,
		const char **	pattern
	)

Definition at line 1121 of file dfa.c.

References do_parse(), DFA_parse::err_code, mk_Tnode(), OR, Tnode::p, DFA::parse_info, Tnode::pos, DFA_parse::root, and Tnode::u.

Referenced by actionListMk(), data1_read_absyn(), dict_lookup_grep(), main(), read_rules(), readOneSpec(), and test_parse().

dfa_parse_cmap_add()

void dfa_parse_cmap_add	(	struct DFA *	d,
		int	from,
		int	to
	)

Definition at line 978 of file dfa.c.

References DFA_parse::charMap, DFA_parse::charMapSize, ifree(), imalloc(), and DFA::parse_info.

Referenced by lexSpecDFA().

dfa_parse_cmap_clean()

void dfa_parse_cmap_clean

(

struct DFA *

d

)

Definition at line 926 of file dfa.c.

References DFA_parse::charMap, DFA_parse::charMapSize, imalloc(), and DFA::parse_info.

dfa_parse_cmap_del()

void dfa_parse_cmap_del	(	struct DFA *	d,
		int	from
	)

Definition at line 960 of file dfa.c.

References DFA_parse::charMap, and DFA::parse_info.

Referenced by lexSpecDFA().

dfa_parse_cmap_new()

void dfa_parse_cmap_new	(	struct DFA *	d,
		const int *	cmap
	)

Definition at line 940 of file dfa.c.

References DFA_parse::charMap, DFA_parse::charMapSize, DFA_parse::cmap, ifree(), imalloc(), and DFA::parse_info.

Referenced by dfa_parse_cmap_thompson().

dfa_parse_cmap_thompson()

void dfa_parse_cmap_thompson

(

struct DFA *

d

)

Definition at line 1006 of file dfa.c.

References dfa_parse_cmap_new(), L_ALT, L_ANY, L_CLOS0, L_CLOS1, L_END, L_LP, L_QUEST, L_RP, and L_START.

Referenced by dfa_init().

dfa_parse_init()

static struct DFA_parse* dfa_parse_init ( void  )

static

Definition at line 1027 of file dfa.c.

References add_BSet(), DFA_parse::anyset, DFA_parse::charMap, DFA_parse::charMapSize, DFA_parse::charset, DFA_parse::cmap, com_BSet(), DFA_parse::end, imalloc(), DFA_parse::max_Tnode, mk_BSet(), mk_BSetHandle(), DFA_parse::position, res_BSet(), DFA_parse::root, DFA_parse::rule, DFA_parse::start, and DFA_parse::use_Tnode.

Referenced by dfa_init().

dfa_set_cmap()

void dfa_set_cmap	(	struct DFA *	dfa,
		void *	vp,
		const char **(*)(void *vp, const char **from, int len)	cmap
	)

Definition at line 1109 of file dfa.c.

References DFA_parse::cmap, DFA_parse::cmap_data, and DFA::parse_info.

Referenced by dict_lookup_grep().

dfa_trav()

static void dfa_trav	(	struct DFA_parse *	parse_info,
		struct Tnode *	n
	)

Definition at line 650 of file dfa.c.

References add_DFASet(), add_follow(), CAT, Tnode::ch, debug_dfa_trav, EPSILON, Tnode::firstpos, Tnode::lastpos, merge_DFASet(), mk_DFASet(), Tnode::nullable, OR, out_char(), Tnode::p, PLUS, Tnode::pos, DFA_parse::posar, DFA_parse::poset, pr_DFASet(), rm_DFASet(), STAR, Tnode::u, and union_DFASet().

Referenced by mk_dfas().

do_parse()

static void do_parse ( struct DFA_parse *  parse_info, const char **  s, struct Tnode **  tnp  )

static

Definition at line 246 of file dfa.c.

References CAT, Tnode::ch, DFA_ERR_LP, DFA_ERR_RP, DFA_ERR_SYNTAX, DFA_parse::err_code, expr_1(), DFA_parse::expr_ptr, DFA_parse::inside_string, L_END, L_LP, L_RP, L_START, lex(), DFA_parse::lookahead, mk_Tnode(), Tnode::p, Tnode::pos, DFA_parse::position, DFA_parse::rule, and Tnode::u.

Referenced by dfa_parse().

expr_1()

static struct Tnode * expr_1 ( struct DFA_parse *  parse_info )

static

Definition at line 117 of file dfa.c.

References expr_2(), L_ALT, lex(), DFA_parse::lookahead, mk_Tnode(), OR, Tnode::p, Tnode::pos, and Tnode::u.

Referenced by do_parse(), and expr_4().

expr_2()

static struct Tnode * expr_2

(

struct DFA_parse *

parse_info

)

Definition at line 138 of file dfa.c.

References CAT, expr_3(), L_ANY, L_ANYZ, L_CHAR, L_CHARS, L_LP, L_WILD, DFA_parse::lookahead, mk_Tnode(), Tnode::p, Tnode::pos, and Tnode::u.

Referenced by expr_1().

expr_3()

static struct Tnode * expr_3

(

struct DFA_parse *

parse_info

)

Definition at line 163 of file dfa.c.

References EPSILON, expr_4(), L_CLOS0, L_CLOS1, L_QUEST, lex(), DFA_parse::lookahead, mk_Tnode(), OR, Tnode::p, PLUS, Tnode::pos, STAR, and Tnode::u.

Referenced by expr_2().

expr_4()

static struct Tnode * expr_4

(

struct DFA_parse *

parse_info

)

Definition at line 198 of file dfa.c.

References DFA_parse::anyset, Tnode::ch, EPSILON, expr_1(), L_ANY, L_ANYZ, L_CHAR, L_CHARS, L_LP, L_RP, L_WILD, lex(), DFA_parse::look_ch, DFA_parse::look_chars, DFA_parse::lookahead, mk_Tnode(), mk_Tnode_cset(), OR, Tnode::p, Tnode::pos, DFA_parse::position, STAR, and Tnode::u.

Referenced by expr_3().

init_followpos()

static void init_followpos

(

struct DFA_parse *

parse_info

)

Definition at line 754 of file dfa.c.

References DFA_parse::followpos, imalloc(), mk_DFASet(), DFA_parse::poset, and DFA_parse::position.

Referenced by mk_dfas().

init_pos()

static void init_pos

(

struct DFA_parse *

parse_info

)

Definition at line 627 of file dfa.c.

References imalloc(), DFA_parse::posar, and DFA_parse::position.

Referenced by dict_lookup_grep(), grep(), and mk_dfas().

lex()

static void lex

(

struct DFA_parse *

parse_info

)

Definition at line 503 of file dfa.c.

References lex_sub(), and DFA_parse::lookahead.

Referenced by do_parse(), expr_1(), expr_3(), expr_4(), and main().

lex_sub()

static int lex_sub ( struct DFA_parse *  parse_info )

static

Definition at line 474 of file dfa.c.

References DFA_parse::charMap, DFA_parse::expr_ptr, DFA_parse::inside_string, DFA_parse::look_ch, map_l_char(), nextchar(), and read_charset().

Referenced by lex().

map_l_char()

static int map_l_char ( struct DFA_parse *  parse_info )

static

Definition at line 450 of file dfa.c.

References DFA_parse::cmap, DFA_parse::cmap_data, DFA_parse::expr_ptr, L_CHAR, and DFA_parse::look_ch.

Referenced by lex_sub().

mk_dfa_tran()

static void mk_dfa_tran	(	struct DFA_parse *	parse_info,
		struct DFA_states *	dfas
	)

Definition at line 764 of file dfa.c.

References add_DFA_state(), add_DFA_tran(), Tnode::ch, DFA_parse::charset, cp_DFASet(), Tnode::firstpos, DFA_parse::followpos, get_DFA_state(), ifree(), imalloc(), mk_DFASet(), DFASetElement_::next, DFA_state::no, Tnode::pos, DFA_parse::posar, DFA_parse::poset, DFA_parse::position, DFA_parse::root, DFA_state::rule_nno, DFA_state::rule_no, DFA_state::set, BSetHandle_::size, sort_DFA_states(), Tnode::u, union_DFASet(), and DFASetElement_::value.

Referenced by mk_dfas().

mk_dfas()

static struct DFA_states* mk_dfas ( struct DFA_parse *  dfap, int  poset_chunk  )

static

Definition at line 1062 of file dfa.c.

References debug_dfa_followpos, debug_dfa_tran, del_followpos(), del_pos(), dfa_trav(), dfa_verbose, init_DFA_states(), init_followpos(), init_pos(), mk_dfa_tran(), mk_DFASetType(), DFA_parse::poset, pr_followpos(), pr_tran(), pr_verbose(), rm_DFASetType(), DFA_parse::root, and STATE_HASH.

Referenced by dfa_mkstate().

mk_Tnode()

static struct Tnode * mk_Tnode ( struct DFA_parse *  parse_info )

static

Definition at line 563 of file dfa.c.

References DFA_parse::end, imalloc(), DFA_parse::max_Tnode, Tblock::next, DFA_parse::start, TADD, Tblock::tarray, and DFA_parse::use_Tnode.

Referenced by dfa_parse(), do_parse(), expr_1(), expr_2(), expr_3(), expr_4(), and mk_Tnode_cset().

mk_Tnode_cset()

struct Tnode * mk_Tnode_cset ( struct DFA_parse *  parse_info, BSet  charset  )

static

Definition at line 584 of file dfa.c.

References Tnode::ch, DFA_parse::charset, EPSILON, mk_Tnode(), OR, Tnode::p, Tnode::pos, DFA_parse::position, BSetHandle_::size, trav_BSet(), travi_BSet(), and Tnode::u.

Referenced by expr_4().

nextchar()

static int nextchar ( struct DFA_parse *  parse_info, int *  esc  )

static

Definition at line 314 of file dfa.c.

References DFA_parse::expr_ptr.

Referenced by lex_sub(), nextchar_set(), and read_charset().

nextchar_set()

static int nextchar_set ( struct DFA_parse *  parse_info, int *  esc  )

static

Definition at line 348 of file dfa.c.

References DFA_parse::expr_ptr, and nextchar().

Referenced by read_charset().

out_char()

static void out_char

(

int

c

)

Definition at line 547 of file dfa.c.

References str_char().

Referenced by dfa_trav(), and pr_followpos().

pr_followpos()

static void pr_followpos

(

struct DFA_parse *

parse_info

)

Definition at line 897 of file dfa.c.

References Tnode::ch, DFA_parse::followpos, out_char(), DFA_parse::posar, DFA_parse::poset, DFA_parse::position, pr_DFASet(), and Tnode::u.

Referenced by mk_dfas().

pr_tran()

static void pr_tran	(	struct DFA_parse *	parse_info,
		struct DFA_states *	dfas
	)

Definition at line 846 of file dfa.c.

References DFA_tran::ch, DFA_states::no, DFA_state::no, DFA_parse::poset, pr_DFASet(), DFA_state::rule_nno, DFA_state::rule_no, DFA_state::set, DFA_states::sortarray, str_char(), DFA_tran::to, DFA_state::tran_no, and DFA_state::trans.

Referenced by mk_dfas().

pr_verbose()

static void pr_verbose	(	struct DFA_parse *	parse_info,
		struct DFA_states *	dfas
	)

Definition at line 883 of file dfa.c.

References DFA_parse::charset, inf_BSetHandle(), inf_DFASetType(), DFA_parse::max_Tnode, DFA_states::no, DFA_parse::poset, and DFA_parse::use_Tnode.

Referenced by mk_dfas().

read_charset()

static int read_charset

(

struct DFA_parse *

parse_info

)

ch0 is last met character ch1 is "next" char

Definition at line 358 of file dfa.c.

References add_BSet(), DFA_parse::charset, DFA_parse::cmap, DFA_parse::cmap_data, com_BSet(), L_CHARS, DFA_parse::look_chars, mk_BSet(), nextchar(), nextchar_set(), and res_BSet().

Referenced by lex_sub().

rm_dfa_parse()

static void rm_dfa_parse ( struct DFA_parse **  dfap )

static

Definition at line 1051 of file dfa.c.

References DFA_parse::charMap, DFA_parse::charset, ifree(), rm_BSetHandle(), and term_Tnode().

Referenced by dfa_delete(), and dfa_mkstate().

str_char()

static const char * str_char ( unsigned  c )

static

Definition at line 508 of file dfa.c.

Referenced by out_char(), and pr_tran().

term_Tnode()

static void term_Tnode ( struct DFA_parse *  parse_info )

static

Definition at line 552 of file dfa.c.

References ifree(), Tblock::next, DFA_parse::start, and Tblock::tarray.

Referenced by rm_dfa_parse().

Variable Documentation

debug_dfa_followpos

int debug_dfa_followpos = 0

Definition at line 68 of file dfa.c.

Referenced by agrep_options(), dict_lookup_grep(), lexer_options(), main(), mk_dfas(), and readFileSpec().

debug_dfa_tran

int debug_dfa_tran = 0

Definition at line 67 of file dfa.c.

Referenced by actionListMk(), agrep_options(), dict_lookup_grep(), lexer_options(), main(), mk_dfas(), and readFileSpec().

debug_dfa_trav

int debug_dfa_trav = 0

Definition at line 66 of file dfa.c.

Referenced by agrep_options(), dfa_trav(), dict_lookup_grep(), lexer_options(), main(), and readFileSpec().

dfa_verbose

int dfa_verbose = 0

Definition at line 69 of file dfa.c.

Referenced by agrep_options(), dict_lookup_grep(), lexer_options(), main(), mk_dfas(), and readFileSpec().