KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > net > percederberg > grammatica > parser > Automaton


1 /*
2  * Automaton.java
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public License
6  * as published by the Free Software Foundation; either version 2.1
7  * of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the Free
16  * Software Foundation, Inc., 59 Temple Place, Suite 330, Boston,
17  * MA 02111-1307, USA.
18  *
19  * Copyright (c) 2004-2005 Per Cederberg. All rights reserved.
20  */
21
22 package net.percederberg.grammatica.parser;
23
24 import java.io.IOException JavaDoc;
25
26 /**
27  * A deterministic finite state automaton. This is a simple automaton
28  * for character sequences, currently used for string token patterns.
29  * It only handles single character transitions between states, but
30  * supports running in an all case-insensitive mode.
31  *
32  * @author Per Cederberg, <per at percederberg dot net>
33  * @version 1.5
34  * @since 1.5
35  */
36 class Automaton {
37
38     /**
39      * The state value.
40      */
41     private Object JavaDoc value = null;
42
43     /**
44      * The automaton state transition tree. Each transition from this
45      * state to another state is added to this tree with the
46      * corresponding character.
47      */
48     private AutomatonTree tree = new AutomatonTree();
49
50     /**
51      * Creates a new empty automaton.
52      */
53     public Automaton() {
54     }
55
56     /**
57      * Adds a string match to this automaton. New states and
58      * transitions will be added to extend this automaton to support
59      * the specified string.
60      *
61      * @param str the string to match
62      * @param caseInsensitive the case-insensitive match flag
63      * @param value the match value
64      */
65     public void addMatch(String JavaDoc str, boolean caseInsensitive, Object JavaDoc value) {
66         Automaton state;
67
68         if (str.equals("")) {
69             this.value = value;
70         } else {
71             state = tree.find(str.charAt(0), caseInsensitive);
72             if (state == null) {
73                 state = new Automaton();
74                 state.addMatch(str.substring(1), caseInsensitive, value);
75                 tree.add(str.charAt(0), caseInsensitive, state);
76             } else {
77                 state.addMatch(str.substring(1), caseInsensitive, value);
78             }
79         }
80     }
81
82     /**
83      * Checks if the automaton matches an input stream. The matching
84      * will be performed from a specified position. This method will
85      * not read any characters from the stream, just peek ahead. The
86      * comparison can be done either in case-sensitive or
87      * case-insensitive mode.
88      *
89      * @param input the input stream to check
90      * @param pos the starting position
91      * @param caseInsensitive the case-insensitive match flag
92      *
93      * @return the match value, or
94      * null if no match was found
95      *
96      * @throws IOException if an I/O error occurred
97      */
98     public Object JavaDoc matchFrom(LookAheadReader input,
99                             int pos,
100                             boolean caseInsensitive)
101         throws IOException JavaDoc {
102
103         Object JavaDoc result = null;
104         Automaton state;
105         int c;
106
107         c = input.peek(pos);
108         if (tree != null && c >= 0) {
109             state = tree.find((char) c, caseInsensitive);
110             if (state != null) {
111                 result = state.matchFrom(input, pos + 1, caseInsensitive);
112             }
113         }
114         return (result == null) ? value : result;
115     }
116
117
118     /**
119      * An automaton state transition tree. This class contains a
120      * binary search tree for the automaton transitions from one state
121      * to another. All transitions are linked to a single character.
122      *
123      * @author Per Cederberg, <per at percederberg dot net>
124      * @version 1.5
125      * @since 1.5
126      */
127     private class AutomatonTree {
128
129         /**
130          * The transition character. If this value is set to the zero
131          * character ('\0'), this tree is empty.
132          */
133         private char value = '\0';
134
135         /**
136          * The transition state.
137          */
138         private Automaton state = null;
139
140         /**
141          * The left subtree.
142          */
143         private AutomatonTree left = null;
144
145         /**
146          * The right subtree.
147          */
148         private AutomatonTree right = null;
149
150         /**
151          * Creates a new empty automaton transition tree.
152          */
153         public AutomatonTree() {
154         }
155
156         /**
157          * Finds an automaton state from the specified transition
158          * character. This method searches this transition tree for a
159          * matching transition. The comparison can optionally be done
160          * with a lower-case conversion of the character.
161          *
162          * @param c the character to search for
163          * @param lowerCase the lower-case conversion flag
164          *
165          * @return the automaton state found, or
166          * null if no transition exists
167          */
168         public Automaton find(char c, boolean lowerCase) {
169             if (lowerCase) {
170                 c = Character.toLowerCase(c);
171             }
172             if (value == '\0' || value == c) {
173                 return state;
174             } else if (value > c) {
175                 return left.find(c, false);
176             } else {
177                 return right.find(c, false);
178             }
179         }
180
181         /**
182          * Adds a transition to this tree. If the lower-case flag is
183          * set, the character will be converted to lower-case before
184          * being added.
185          *
186          * @param c the character to transition for
187          * @param lowerCase the lower-case conversion flag
188          * @param state the state to transition to
189          */
190         public void add(char c, boolean lowerCase, Automaton state) {
191             if (lowerCase) {
192                 c = Character.toLowerCase(c);
193             }
194             if (value == '\0') {
195                 this.value = c;
196                 this.state = state;
197                 this.left = new AutomatonTree();
198                 this.right = new AutomatonTree();
199             } else if (value > c) {
200                 left.add(c, false, state);
201             } else {
202                 right.add(c, false, state);
203             }
204         }
205     }
206 }
207
Popular Tags