[25584] | 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 | }
|
---|