blob: 07ce2b9bc417debe4a8be1f5d899196d32017ff7 [file] [log] [blame]
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00001/* Grammar interface */
2
3#include "bitset.h" /* Sigh... */
4
5/* A label of an arc */
6
7typedef struct _label {
8 int lb_type;
9 char *lb_str;
10} label;
11
12#define EMPTY 0 /* Label number 0 is by definition the empty label */
13
14/* A list of labels */
15
16typedef struct _labellist {
17 int ll_nlabels;
18 label *ll_label;
19} labellist;
20
21/* An arc from one state to another */
22
23typedef struct _arc {
24 short a_lbl; /* Label of this arc */
25 short a_arrow; /* State where this arc goes to */
26} arc;
27
28/* A state in a DFA */
29
30typedef struct _state {
31 int s_narcs;
32 arc *s_arc; /* Array of arcs */
33
34 /* Optional accelerators */
35 int s_lower; /* Lowest label index */
36 int s_upper; /* Highest label index */
37 int *s_accel; /* Accelerator */
38 int s_accept; /* Nonzero for accepting state */
39} state;
40
41/* A DFA */
42
43typedef struct _dfa {
44 int d_type; /* Non-terminal this represents */
45 char *d_name; /* For printing */
46 int d_initial; /* Initial state */
47 int d_nstates;
48 state *d_state; /* Array of states */
49 bitset d_first;
50} dfa;
51
52/* A grammar */
53
54typedef struct _grammar {
55 int g_ndfas;
56 dfa *g_dfa; /* Array of DFAs */
57 labellist g_ll;
58 int g_start; /* Start symbol of the grammar */
59 int g_accel; /* Set if accelerators present */
60} grammar;
61
62/* FUNCTIONS */
63
64grammar *newgrammar PROTO((int start));
65dfa *adddfa PROTO((grammar *g, int type, char *name));
66int addstate PROTO((dfa *d));
67void addarc PROTO((dfa *d, int from, int to, int lbl));
68dfa *finddfa PROTO((grammar *g, int type));
69char *typename PROTO((grammar *g, int lbl));
70
71int addlabel PROTO((labellist *ll, int type, char *str));
72int findlabel PROTO((labellist *ll, int type, char *str));
73char *labelrepr PROTO((label *lb));
74void translatelabels PROTO((grammar *g));
75
76void addfirstsets PROTO((grammar *g));
77
78void addaccellerators PROTO((grammar *g));
Guido van Rossum3f5da241990-12-20 15:06:42 +000079
80void printgrammar PROTO((grammar *g, FILE *fp));
81void printnonterminals PROTO((grammar *g, FILE *fp));