1 | /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
|
---|
2 | * JFlex 1.4.3 *
|
---|
3 | * Copyright (C) 1998-2009 Gerwin Klein <[email protected]> *
|
---|
4 | * All rights reserved. *
|
---|
5 | * *
|
---|
6 | * This program is free software; you can redistribute it and/or modify *
|
---|
7 | * it under the terms of the GNU General Public License. See the file *
|
---|
8 | * COPYRIGHT for more information. *
|
---|
9 | * *
|
---|
10 | * This program is distributed in the hope that it will be useful, *
|
---|
11 | * but WITHOUT ANY WARRANTY; without even the implied warranty of *
|
---|
12 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
|
---|
13 | * GNU General Public License for more details. *
|
---|
14 | * *
|
---|
15 | * You should have received a copy of the GNU General Public License along *
|
---|
16 | * with this program; if not, write to the Free Software Foundation, Inc., *
|
---|
17 | * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA *
|
---|
18 | * *
|
---|
19 | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
|
---|
20 | package JFlex;
|
---|
21 |
|
---|
22 | import java.io.File;
|
---|
23 |
|
---|
24 | /**
|
---|
25 | * Performs simple semantic analysis on regular expressions.
|
---|
26 | *
|
---|
27 | * @author Gerwin Klein
|
---|
28 | * @version JFlex 1.4.3, $Revision: 433 $, $Date: 2009-01-31 19:52:34 +1100 (Sat, 31 Jan 2009) $
|
---|
29 | */
|
---|
30 | public final class SemCheck {
|
---|
31 |
|
---|
32 | // stored globally since they are used as constants in all checks
|
---|
33 | private static Macros macros;
|
---|
34 |
|
---|
35 | /**
|
---|
36 | * Performs semantic analysis for all expressions.
|
---|
37 | *
|
---|
38 | * Currently checks for empty expressions only.
|
---|
39 | *
|
---|
40 | * @param rs the reg exps to be checked
|
---|
41 | * @param m the macro table (in expanded form)
|
---|
42 | * @param f the spec file containing the rules
|
---|
43 | */
|
---|
44 | public static void check(RegExps rs, Macros m, File f) {
|
---|
45 | macros = m;
|
---|
46 | int num = rs.getNum();
|
---|
47 | for (int i = 0; i < num; i++) {
|
---|
48 | RegExp r = rs.getRegExp(i);
|
---|
49 | RegExp l = rs.getLookAhead(i);
|
---|
50 | Action a = rs.getAction(i);
|
---|
51 |
|
---|
52 | if (r != null && l != null && maybeEmtpy(r)) {
|
---|
53 | if (a == null)
|
---|
54 | Out.error(ErrorMessages.EMPTY_MATCH, "");
|
---|
55 | else
|
---|
56 | Out.error(f, ErrorMessages.EMPTY_MATCH, a.priority-1, -1);
|
---|
57 | }
|
---|
58 | }
|
---|
59 | }
|
---|
60 |
|
---|
61 |
|
---|
62 | /**
|
---|
63 | * Checks if the expression potentially matches the empty string.
|
---|
64 | *
|
---|
65 | */
|
---|
66 | public static boolean maybeEmtpy(RegExp re) {
|
---|
67 | RegExp2 r;
|
---|
68 |
|
---|
69 | switch (re.type) {
|
---|
70 |
|
---|
71 | case sym.BAR: {
|
---|
72 | r = (RegExp2) re;
|
---|
73 | return maybeEmtpy(r.r1) || maybeEmtpy(r.r2);
|
---|
74 | }
|
---|
75 |
|
---|
76 | case sym.CONCAT: {
|
---|
77 | r = (RegExp2) re;
|
---|
78 | return maybeEmtpy(r.r1) && maybeEmtpy(r.r2);
|
---|
79 | }
|
---|
80 |
|
---|
81 | case sym.STAR:
|
---|
82 | case sym.QUESTION:
|
---|
83 | return true;
|
---|
84 |
|
---|
85 | case sym.PLUS: {
|
---|
86 | RegExp1 r1 = (RegExp1) re;
|
---|
87 | return maybeEmtpy((RegExp) r1.content);
|
---|
88 | }
|
---|
89 |
|
---|
90 | case sym.CCLASS:
|
---|
91 | case sym.CCLASSNOT:
|
---|
92 | case sym.CHAR:
|
---|
93 | case sym.CHAR_I:
|
---|
94 | return false;
|
---|
95 |
|
---|
96 | case sym.STRING:
|
---|
97 | case sym.STRING_I: {
|
---|
98 | String content = (String) ((RegExp1) re).content;
|
---|
99 | return content.length() == 0;
|
---|
100 | }
|
---|
101 |
|
---|
102 | case sym.TILDE:
|
---|
103 | return false;
|
---|
104 |
|
---|
105 | case sym.BANG: {
|
---|
106 | RegExp1 r1 = (RegExp1) re;
|
---|
107 | return !maybeEmtpy((RegExp) r1.content);
|
---|
108 | }
|
---|
109 |
|
---|
110 | case sym.MACROUSE:
|
---|
111 | return maybeEmtpy(macros.getDefinition((String) ((RegExp1) re).content));
|
---|
112 | }
|
---|
113 |
|
---|
114 | throw new Error("Unkown expression type "+re.type+" in "+re); //$NON-NLS-1$ //$NON-NLS-2$
|
---|
115 | }
|
---|
116 |
|
---|
117 | /**
|
---|
118 | * Returns length if expression has fixed length, -1 otherwise.
|
---|
119 | *
|
---|
120 | * Negation operators are treated as always variable length.
|
---|
121 | */
|
---|
122 | public static int length(RegExp re) {
|
---|
123 | RegExp2 r;
|
---|
124 |
|
---|
125 | switch (re.type) {
|
---|
126 |
|
---|
127 | case sym.BAR: {
|
---|
128 | r = (RegExp2) re;
|
---|
129 | int l1 = length(r.r1);
|
---|
130 | if (l1 < 0) return -1;
|
---|
131 | int l2 = length(r.r2);
|
---|
132 |
|
---|
133 | if (l1 == l2)
|
---|
134 | return l1;
|
---|
135 | else
|
---|
136 | return -1;
|
---|
137 | }
|
---|
138 |
|
---|
139 | case sym.CONCAT: {
|
---|
140 | r = (RegExp2) re;
|
---|
141 | int l1 = length(r.r1);
|
---|
142 | if (l1 < 0) return -1;
|
---|
143 | int l2 = length(r.r2);
|
---|
144 | if (l2 < 0) return -1;
|
---|
145 | return l1+l2;
|
---|
146 | }
|
---|
147 |
|
---|
148 | case sym.STAR:
|
---|
149 | case sym.PLUS:
|
---|
150 | case sym.QUESTION:
|
---|
151 | return -1;
|
---|
152 |
|
---|
153 | case sym.CCLASS:
|
---|
154 | case sym.CCLASSNOT:
|
---|
155 | case sym.CHAR:
|
---|
156 | case sym.CHAR_I:
|
---|
157 | return 1;
|
---|
158 |
|
---|
159 | case sym.STRING:
|
---|
160 | case sym.STRING_I: {
|
---|
161 | String content = (String) ((RegExp1) re).content;
|
---|
162 | return content.length();
|
---|
163 | }
|
---|
164 |
|
---|
165 | case sym.TILDE:
|
---|
166 | case sym.BANG:
|
---|
167 | // too hard to calculate at this level, use safe approx
|
---|
168 | return -1;
|
---|
169 |
|
---|
170 | case sym.MACROUSE:
|
---|
171 | return length(macros.getDefinition((String) ((RegExp1) re).content));
|
---|
172 | }
|
---|
173 |
|
---|
174 | throw new Error("Unkown expression type "+re.type+" in "+re); //$NON-NLS-1$ //$NON-NLS-2$
|
---|
175 | }
|
---|
176 |
|
---|
177 | /**
|
---|
178 | * Returns true iff the expression is a finite choice of fixed length
|
---|
179 | * expressions.
|
---|
180 | *
|
---|
181 | * Negation operators are treated as always variable length.
|
---|
182 | */
|
---|
183 | public static boolean isFiniteChoice(RegExp re) {
|
---|
184 | RegExp2 r;
|
---|
185 |
|
---|
186 | switch (re.type) {
|
---|
187 |
|
---|
188 | case sym.BAR: {
|
---|
189 | r = (RegExp2) re;
|
---|
190 | return isFiniteChoice(r.r1) && isFiniteChoice(r.r2);
|
---|
191 | }
|
---|
192 |
|
---|
193 | case sym.CONCAT: {
|
---|
194 | r = (RegExp2) re;
|
---|
195 | int l1 = length(r.r1);
|
---|
196 | if (l1 < 0) return false;
|
---|
197 | int l2 = length(r.r2);
|
---|
198 | return l2 >= 0;
|
---|
199 | }
|
---|
200 |
|
---|
201 | case sym.STAR:
|
---|
202 | case sym.PLUS:
|
---|
203 | case sym.QUESTION:
|
---|
204 | return false;
|
---|
205 |
|
---|
206 | case sym.CCLASS:
|
---|
207 | case sym.CCLASSNOT:
|
---|
208 | case sym.CHAR:
|
---|
209 | case sym.CHAR_I:
|
---|
210 | return true;
|
---|
211 |
|
---|
212 | case sym.STRING:
|
---|
213 | case sym.STRING_I: {
|
---|
214 | return true;
|
---|
215 | }
|
---|
216 |
|
---|
217 | case sym.TILDE:
|
---|
218 | case sym.BANG:
|
---|
219 | return false;
|
---|
220 |
|
---|
221 | case sym.MACROUSE:
|
---|
222 | return isFiniteChoice(macros.getDefinition((String) ((RegExp1) re).content));
|
---|
223 | }
|
---|
224 |
|
---|
225 | throw new Error("Unkown expression type "+re.type+" in "+re); //$NON-NLS-1$ //$NON-NLS-2$
|
---|
226 | }
|
---|
227 | }
|
---|