IDZEBRA  2.1.2
Data Structures | Macros | Functions | Variables
dfa.c File Reference
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.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 Tnodemk_Tnode (struct DFA_parse *parse_info)
 
static struct Tnodemk_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 Tnodeexpr_1 (struct DFA_parse *parse_info)
 
static struct Tnodeexpr_2 (struct DFA_parse *parse_info)
 
static struct Tnodeexpr_3 (struct DFA_parse *parse_info)
 
static struct Tnodeexpr_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_parsedfa_parse_init (void)
 
static void rm_dfa_parse (struct DFA_parse **dfap)
 
static struct DFA_statesmk_dfas (struct DFA_parse *dfap, int poset_chunk)
 
struct DFAdfa_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

#define CAT   16000

Definition at line 35 of file dfa.c.

Referenced by dfa_trav(), do_parse(), and expr_2().

#define EPSILON   16004

Definition at line 39 of file dfa.c.

Referenced by dfa_trav(), expr_3(), expr_4(), and mk_Tnode_cset().

#define L_ALT   6

Definition at line 100 of file dfa.c.

Referenced by dfa_parse_cmap_thompson(), and expr_1().

#define L_ANY   5

Definition at line 99 of file dfa.c.

Referenced by dfa_parse_cmap_thompson(), expr_2(), and expr_4().

#define L_ANYZ   7

Definition at line 101 of file dfa.c.

Referenced by expr_2(), and expr_4().

#define L_CHAR   3

Definition at line 97 of file dfa.c.

Referenced by expr_2(), expr_4(), and map_l_char().

#define L_CHARS   4

Definition at line 98 of file dfa.c.

Referenced by expr_2(), expr_4(), and read_charset().

#define L_CLOS0   11

Definition at line 105 of file dfa.c.

Referenced by dfa_parse_cmap_thompson(), and expr_3().

#define L_CLOS1   10

Definition at line 104 of file dfa.c.

Referenced by dfa_parse_cmap_thompson(), and expr_3().

#define L_END   12

Definition at line 106 of file dfa.c.

Referenced by dfa_parse_cmap_thompson(), and do_parse().

#define L_LP   1

Definition at line 95 of file dfa.c.

Referenced by dfa_parse_cmap_thompson(), do_parse(), expr_2(), and expr_4().

#define L_QUEST   9

Definition at line 103 of file dfa.c.

Referenced by dfa_parse_cmap_thompson(), and expr_3().

#define L_RP   2

Definition at line 96 of file dfa.c.

Referenced by dfa_parse_cmap_thompson(), do_parse(), and expr_4().

#define L_START   13

Definition at line 107 of file dfa.c.

Referenced by dfa_parse_cmap_thompson(), and do_parse().

#define L_WILD   8

Definition at line 102 of file dfa.c.

Referenced by expr_2(), and expr_4().

#define OR   16001

Definition at line 36 of file dfa.c.

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

#define PLUS   16003

Definition at line 38 of file dfa.c.

Referenced by dfa_trav(), and expr_3().

#define POSET_CHUNK   100

Definition at line 62 of file dfa.c.

Referenced by dfa_mkstate().

#define STAR   16002

Definition at line 37 of file dfa.c.

Referenced by dfa_trav(), expr_3(), and expr_4().

#define STATE_HASH   199

Definition at line 61 of file dfa.c.

Referenced by mk_dfas().

#define TADD   64

Definition at line 60 of file dfa.c.

Referenced by mk_Tnode().

Function Documentation

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

Definition at line 620 of file dfa.c.

References DFA_parse::followpos, and ifree().

Referenced by mk_dfas().

static void del_pos ( struct DFA_parse parse_info)

Definition at line 631 of file dfa.c.

References ifree(), and DFA_parse::posar.

Referenced by mk_dfas().

void dfa_anyset_includes_nl ( struct DFA dfa)

Definition at line 1102 of file dfa.c.

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

Referenced by dict_lookup_grep().

void dfa_delete ( struct DFA **  dfap)
int dfa_get_last_rule ( struct DFA dfa)

Definition at line 1114 of file dfa.c.

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

struct DFA* dfa_init ( void  )
void dfa_mkstate ( struct DFA dfa)
int dfa_parse ( struct DFA dfa,
const char **  pattern 
)
void dfa_parse_cmap_add ( struct DFA d,
int  from,
int  to 
)

Definition at line 976 of file dfa.c.

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

Referenced by lexSpecDFA().

void dfa_parse_cmap_clean ( struct DFA d)

Definition at line 924 of file dfa.c.

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

void dfa_parse_cmap_del ( struct DFA d,
int  from 
)

Definition at line 958 of file dfa.c.

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

Referenced by lexSpecDFA().

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

Definition at line 938 of file dfa.c.

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

Referenced by dfa_parse_cmap_thompson().

void dfa_parse_cmap_thompson ( struct DFA d)

Definition at line 1004 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().

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

Definition at line 1107 of file dfa.c.

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

Referenced by dict_lookup_grep().

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

Definition at line 115 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().

static struct Tnode * expr_2 ( struct DFA_parse parse_info)

Definition at line 136 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().

static struct Tnode * expr_3 ( struct DFA_parse parse_info)

Definition at line 161 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().

static struct Tnode * expr_4 ( struct DFA_parse parse_info)
static void init_followpos ( struct DFA_parse parse_info)

Definition at line 752 of file dfa.c.

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

Referenced by mk_dfas().

static void init_pos ( struct DFA_parse parse_info)

Definition at line 625 of file dfa.c.

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

Referenced by mk_dfas().

static void lex ( struct DFA_parse parse_info)

Definition at line 501 of file dfa.c.

References lex_sub(), and DFA_parse::lookahead.

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

static int lex_sub ( struct DFA_parse parse_info)
static
static int map_l_char ( struct DFA_parse parse_info)
static

Definition at line 448 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().

static void mk_dfa_tran ( struct DFA_parse parse_info,
struct DFA_states dfas 
)
static struct DFA_states* mk_dfas ( struct DFA_parse dfap,
int  poset_chunk 
)
static
static struct Tnode * mk_Tnode ( struct DFA_parse parse_info)
static
struct Tnode * mk_Tnode_cset ( struct DFA_parse parse_info,
BSet  charset 
)
static
static int nextchar ( struct DFA_parse parse_info,
int *  esc 
)
static

Definition at line 312 of file dfa.c.

References DFA_parse::expr_ptr.

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

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

Definition at line 346 of file dfa.c.

References DFA_parse::expr_ptr, and nextchar().

Referenced by read_charset().

static void out_char ( int  c)

Definition at line 545 of file dfa.c.

References str_char().

Referenced by dfa_trav(), and pr_followpos().

static void pr_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 int read_charset ( struct DFA_parse parse_info)

ch0 is last met character ch1 is "next" char

Definition at line 356 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().

static void rm_dfa_parse ( struct DFA_parse **  dfap)
static

Definition at line 1049 of file dfa.c.

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

Referenced by dfa_delete(), and dfa_mkstate().

static const char * str_char ( unsigned  c)
static

Definition at line 506 of file dfa.c.

Referenced by out_char(), and pr_tran().

static void term_Tnode ( struct DFA_parse parse_info)
static

Definition at line 550 of file dfa.c.

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

Referenced by rm_dfa_parse().

Variable Documentation

int debug_dfa_followpos = 0

Definition at line 66 of file dfa.c.

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

int debug_dfa_tran = 0
int debug_dfa_trav = 0

Definition at line 64 of file dfa.c.

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

int dfa_verbose = 0

Definition at line 67 of file dfa.c.

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