1
/* This file is part of Malaga, a system for Natural Language Analysis.
2
* Copyright (C) 1995-1999 Bjoern Beutel
5
* Universitaet Erlangen-Nuernberg
6
* Abteilung fuer Computerlinguistik
9
* e-mail: malaga@linguistik.uni-erlangen.de
11
* This program is free software; you can redistribute it and/or modify
12
* it under the terms of the GNU General Public License as published by
13
* the Free Software Foundation; either version 2 of the License, or
14
* (at your option) any later version.
16
* This program is distributed in the hope that it will be useful,
17
* but WITHOUT ANY WARRANTY; without even the implied warranty of
18
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19
* GNU General Public License for more details.
21
* You should have received a copy of the GNU General Public License
22
* along with this program; if not, write to the Free Software
23
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
25
/* description ==============================================================*/
27
/* This module defines the data types needed for Malaga rules. */
29
/* constants ================================================================*/
31
/* The rule-internal state is described by the following variables:
32
* <S> is the rule stack, a stack of values.
33
* <SP> (stack pointer) is the index of the first free element in <S>.
34
* <BP> (base pointer) is the index of the first element in <S> local to the
36
* <I> is information that is stored in the instruction itself.
37
* <PC> is the program counter, i.e. index of the next node to be executed.
38
* <B>, the backtrace stack, is a stack of triples: (PC, BP, S).
39
* <BTP> is the top index of <B>. */
41
{ /* These are the opcodes of the rule instructions. */
43
/* control instructions */
44
INS_ERROR, /* terminate all paths and report Error(I). */
45
INS_TERMINATE, /* terminate this path. */
46
INS_NOP, /* do nothing. */
47
INS_TERMINATE_IF_NULL, /* SP--; if (S[SP] == NULL) then terminate; */
49
/* result instructions */
50
INS_ADD_END_STATE, /* result = S[SP-1]; rule_successful = TRUE; SP-- */
51
INS_ADD_STATE, /* result = S[SP]; rules = rules[I];
52
* rule_successful = TRUE; SP-- */
53
INS_ADD_ALLO, /* surf = S[SP-2]; allo = S[SP-1];
54
* rule_successful = TRUE; SP-= 2 */
55
INS_ACCEPT, /* rule_successful = TRUE; */
57
/* stack management instructions */
58
INS_PUSH_NULL, /* for (i = 0; i < I; i++) { S[SP+i] = NULL; } SP += I; */
59
INS_PUSH_VAR, /* S[SP] = S[I]; SP++; */
60
INS_PUSH_CONST, /* S[SP] = Const(I); SP++; */
61
INS_PUSH_SYMBOL, /* S[SP] = Symbol(I); SP++; */
62
INS_PUSH_PATTERN_VAR, /* S[SP] = Pattern_Var(I); SP++; */
63
INS_POP, /* SP -= I; */
65
/* value instructions */
66
INS_BUILD_LIST, /* S[SP-I] = <S[SP-I],..,S[SP-1]>; SP -= (I-1); */
67
INS_BUILD_RECORD, /* S[SP-2I] =
68
* "[" S[SP-2I] : S[SP-2I+1] ,.., S[SP-2 ] : S[SP-1] "]";
70
INS_BUILD_PATH, /* SP[SP-I]= "." S[SP-I] "." .. "." S[SP-1];
72
INS_DOT_OPERATION, /* S[SP-2] = S[SP-2] "." S[SP-1]; SP--; */
73
INS_PLUS_OPERATION, /* S[SP-2] := S[SP-2] "+" S[SP-1]; SP--; */
74
INS_MINUS_OPERATION, /* S[SP-2] = S[SP-2] "-" S[SP]; SP--; */
75
INS_ASTERISK_OPERATION, /* S[SP-2] = S[SP-2] "*" S[SP]; SP--; */
76
INS_SLASH_OPERATION, /* S[SP-2] = S[SP-2] "/" S[SP]; SP--; */
77
INS_UNARY_MINUS_OP, /* S[SP-1] = "-" S[SP-1]; */
78
INS_GET_ATTRIBUTE, /* S[SP-1] = S[SP-1] "." Symbol(I); */
79
INS_REMOVE_ATTRIBUTE, /* S[SP-1] = S[SP-1] "-" Symbol(I); */
80
INS_STD_FUNCTION, /* S[SP-1] = function_I (S[SP-1]); */
81
INS_MATCH, /* S[SP-1] = S[SP-1] "match" String(I); (yes or no) */
83
/* instructions to modify variables */
84
INS_SET_VAR, /* S[I] = S[SP-1]; SP--; */
85
INS_PLUS_VAR, /* S[I] = S[I] "+" S[SP-1]; SP--; */
86
INS_MINUS_VAR, /* S[I] = S[I] "-" S[SP-1]; SP--; */
87
INS_ASTERISK_VAR, /* S[I] = S[I] "*" S[SP-1]; SP--; */
88
INS_SLASH_VAR, /* S[I] = S[I] "/" S[SP-1]; SP--; */
89
INS_SET_VAR_PATH, /* (S[I] "." S[SP]) = S[SP+1]; SP -= 2; */
90
INS_PLUS_VAR_PATH, /* (S[I] "." S[SP]) = (S[I] "." S[SP]) "+" S[SP+1];
92
INS_MINUS_VAR_PATH, /* (S[I] "." S[SP]) = (S[I] "." S[SP]) "-" S[SP+1];
94
INS_ASTERISK_VAR_PATH, /* (S[I] "." S[SP]) = (S[I] "." S[SP]) "*" S[SP+1];
96
INS_SLASH_VAR_PATH, /* (S[I] "." S[SP]) = (S[I] "." S[SP]) "/" S[SP+1];
99
/* instructions to support loops */
100
INS_GET_1ST_ELEMENT, /* S[SP-1] = 1st element/attrib/ordinal of S[SP-1]; */
101
INS_ITERATE, /* S[I-1] must be a list, a record, or a number
102
* and S[I] the n-th element/attrib/ordinal of S[I-1].
103
* S[I] = (n+1)-th element/attr/ordinal of S[I-1]; */
105
/* jump instructions */
106
INS_JUMP, /* PC = I. */
107
INS_JUMP_IF_EQUAL, /* if (S[SP-2] "=" S[SP-1]) {PC = I;} SP -= 2; */
108
INS_JUMP_IF_NOT_EQUAL, /* if (! S[SP-2] "=" S[SP-1]) {PC = I;} SP -= 2; */
109
INS_JUMP_IF_CONGR, /* if (S[SP-2] "~" S[SP-1]) {PC = I;} SP -= 2; */
110
INS_JUMP_IF_NOT_CONGR, /* if (! S[SP-2] "~" S[SP-1]) {PC = I;} SP -= 2; */
111
INS_JUMP_IF_IN, /* if (S[SP-2] "in" S[SP-1]) {PC = I;} SP -= 2; */
112
INS_JUMP_IF_NOT_IN, /* if (! S[SP-2] "in" S[SP-1]) {PC = I;} SP -= 2; */
113
INS_JUMP_IF_LESS, /* if (S[SP-2] < S[SP-1]) {PC = I;} SP -= 2; */
114
INS_JUMP_IF_NOT_LESS, /* if (! S[SP-2] < S[SP-1]) {PC = I;} SP -= 2; */
115
INS_JUMP_IF_GREATER, /* if (S[SP-2] > S[SP-1]) {PC = I;} SP -= 2; */
116
INS_JUMP_IF_NOT_GREATER, /* if (! S[SP-2] > S[SP-1]) {PC = I;} SP -= 2; */
117
INS_JUMP_IF_NULL, /* if (S[SP-1] == NULL) {PC = I;} SP--; */
118
INS_JUMP_IF_NOT_NULL, /* if (! S[SP-1] == NULL) {PC = I;} SP--; */
119
INS_JUMP_IF_YES, /* if (S[SP-1] == yes) {PC = I;} SP--; */
120
INS_JUMP_IF_NO, /* if (S[SP-1] == no) {PC = I;} SP--; */
121
INS_JUMP_NOW, /* B[BTP] = {PC, BP, S}; PC = I; BTP++; */
122
INS_JUMP_LATER, /* B[BTP] = {I, BP, S}; BTP++; */
123
INS_JUMP_SUBRULE, /* Push BP; Push PC+1; BP = TOP; PC = first_instr (I); */
124
INS_RETURN /* SP = BP; Pop PC; Pop BP; Pop (I-1); */
127
/* The possible error values for INS_ERROR */
128
enum {ASSERTION_ERROR, NO_RETURN_ERROR};
130
/* The possible standard functions for <standard_function>. */
131
enum {FUNC_TO_ATOMS, FUNC_IS_CAPITAL, FUNC_GET_LENGTH, FUNC_TO_MULTI,
132
FUNC_TO_SET, FUNC_GET_SWITCH, FUNC_GET_VALUE_TYPE, FUNC_GET_VALUE_STRING,
133
FUNC_TRANSMIT, FUNC_FLOOR};
135
#define INSTR_INFO_MIN (-1L << 23)
136
#define INSTR_INFO_MAX ((1L << 23) - 1)
137
/* Never use an instruction info smaller than INSTR_INFO_MIN and
138
* greater than INSTR_INFO_MAX. */
140
#define OPCODE_MAX 255 /* the largest opcode possible */
142
/* macros ===================================================================*/
144
#define INSTR(opcode, instr_info) ((opcode) | (u_int_t) (instr_info) << 8)
145
/* Use this macro to create an instruction. */
147
#define OPCODE(instr) ((instr) & OPCODE_MAX)
148
/* Use this macro to get the opcode of an instruction. */
150
#define INSTR_INFO(instr) ((int_t) (instr) >> 8)
151
/* Use this macro to get the info of an instruction. */
153
/* types ====================================================================*/
155
typedef u_int_t instr_t;
156
/* An instruction is an u_int_t whose lower 8 bits are used
157
* to store the opcode. The upper 24 bits are used to store a signed value. */
159
typedef enum /* possible rule types */
161
ALLO_RULE, COMBI_RULE, END_RULE, FILTER_RULE, PRUNING_RULE, ROBUST_RULE,
165
typedef struct /* defines a rule */
167
int_t name; /* string table index to rule name */
168
int_t first_instr; /* code index of rule start */
169
rule_type_t type; /* type of the rule */
170
int_t num_params; /* number of parameters the rule takes */
174
/* establishes a correspondence between a source line and a rule code index. */
176
int_t line; /* number of source line or -1 if instruction can't be
177
* associated with a specific source line */
178
int_t file; /* string table index to source file name or -1 (see "line") */
179
int_t instr; /* index of first instruction that belongs to src_line */
182
typedef struct /* defines a variable name and all its scopes */
184
int_t name; /* string table index to variable name */
185
int_t first_scope; /* index to first scope of this variable
187
int_t number_of_scopes; /* number of scopes of this variable */
190
typedef struct /* defines a single scope of a variable */
192
int_t first_instr; /* index of first instruction where var is defined */
193
int_t last_instr; /* index of last instruction where var is defined */
194
int_t stack_index; /* index of variable in rule stack */
197
/* end of file ==============================================================*/