SecondPassAnalyzer


1   /*
2    * SecondPassAnalyzer.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) 2003-2005 Per Cederberg. All rights reserved.
20   */
21  
22  package net.percederberg.grammatica;
23  
24  import net.percederberg.grammatica.parser.Node;
25  import net.percederberg.grammatica.parser.ParseException;
26  import net.percederberg.grammatica.parser.ParserCreationException;
27  import net.percederberg.grammatica.parser.Production;
28  import net.percederberg.grammatica.parser.ProductionPattern;
29  import net.percederberg.grammatica.parser.ProductionPatternAlternative;
30  import net.percederberg.grammatica.parser.ProductionPatternElement;
31  import net.percederberg.grammatica.parser.Token;
32  import net.percederberg.grammatica.parser.TokenPattern;
33  
34  /**
35   * A second pass grammar analyzer. This class processes the grammar
36   * parse tree and adds all production pattern rules to the patterns.
37   * All required syntetic production patterns will also be added to
38   * the grammar.
39   *
40   * @author   Per Cederberg, <per at percederberg dot net>
41   * @version  1.0
42   */
43  class SecondPassAnalyzer extends GrammarAnalyzer {
44  
45      /**
46       * The grammar where tokens and patterns are stored.
47       */
48      private Grammar grammar;
49  
50      /**
51       * The current production pattern. This is set when processing the
52       * production declaration, and is used when creating syntetic
53       * productions.
54       */
55      private ProductionPattern currentProduction = null;
56  
57      /**
58       * The next free syntetic production id.
59       */
60      private int nextSynteticId = 3001;
61  
62      /**
63       * Creates a new grammar analyser.
64       *
65       * @param grammar        the grammar where objects are added
66       */
67      public SecondPassAnalyzer(Grammar grammar) {
68          this.grammar = grammar;
69      }
70  
71      /**
72       * Sets the node value to the token or production pattern. If no
73       * matching pattern was found, an exception is thrown.
74       *
75       * @param node           the token node
76       *
77       * @return the token node
78       *
79       * @throws ParseException if the node analysis discovered errors
80       */
81      protected Node exitIdentifier(Token node) throws ParseException {
82          String               name = node.getImage();
83          TokenPattern       token = grammar.getTokenPatternByName(name);
84          ProductionPattern  prod = grammar.getProductionPatternByName(name);
85  
86          if (token != null) {
87              node.addValue(token);
88          } else if (prod != null) {
89              node.addValue(prod);
90          } else {
91              throw new ParseException(
92                  ParseException.ANALYSIS_ERROR,
93                  "unrecognized identifier '" + name + "'",
94                  node.getStartLine(),
95                  node.getStartColumn());
96          }
97          return node;
98      }
99  
100     /**
101      * Sets the node value to the token pattern. If no matching
102      * pattern was found, an exception is thrown.
103      *
104      * @param node           the token node
105      *
106      * @return the token node
107      *
108      * @throws ParseException if the node analysis discovered errors
109      */
110     protected Node exitQuotedString(Token node) throws ParseException {
111         String          str;
112         TokenPattern  token;
113 
114         str = node.getImage();
115         str = str.substring(1, str.length() - 1);
116         token = grammar.getTokenPatternByImage(str);
117         if (token != null) {
118             node.addValue(token);
119         } else {
120             throw new ParseException(
121                 ParseException.ANALYSIS_ERROR,
122                 "unrecognized token \"" + str + "\"",
123                 node.getStartLine(),
124                 node.getStartColumn());
125         }
126         return node;
127     }
128 
129     /**
130      * Removes the parse tree by returning null.
131      *
132      * @param node           the production node
133      *
134      * @return the new production node
135      */
136     protected Node exitGrammar(Production node) {
137         return null;
138     }
139 
140     /**
141      * Removes the production part from the parse tree by returning
142      * null.
143      *
144      * @param node           the production node
145      *
146      * @return the new production node
147      */
148     protected Node exitProductionPart(Production node) {
149         return null;
150     }
151 
152     /**
153      * Sets the production name variable when encountering the
154      * identifier child. This variable is used when creating new
155      * subproductions.
156      *
157      * @param node           the production node
158      * @param child          the child to add
159      *
160      * @throws ParseException if the node analysis discovered errors
161      */
162     protected void childProductionDeclaration(Production node, Node child)
163         throws ParseException {
164 
165         super.childProductionDeclaration(node, child);
166         if (child.getId() == GrammarConstants.IDENTIFIER) {
167             currentProduction = (ProductionPattern) child.getValue(0);
168         }
169     }
170 
171     /**
172      * Adds all the pattern rules to the production pattern. This
173      * method also removes the production declaration from the parse
174      * tree by returning null.
175      *
176      * @param node           the production node
177      *
178      * @return the new production node
179      *
180      * @throws ParseException if the node analysis discovered errors
181      */
182     protected Node exitProductionDeclaration(Production node)
183         throws ParseException {
184 
185         ProductionPattern             pattern;
186         ProductionPatternAlternative  alt;
187         Node                          child;
188 
189         pattern = (ProductionPattern) getValue(getChildAt(node, 0), 0);
190         child = getChildAt(node, 2);
191         for (int i = 0; i < child.getValueCount(); i++) {
192             alt = (ProductionPatternAlternative) getValue(child, i);
193             try {
194                 pattern.addAlternative(alt);
195             } catch (ParserCreationException e) {
196                 throw new ParseException(
197                     ParseException.ANALYSIS_ERROR,
198                     e.getMessage(),
199                     node.getStartLine(),
200                     node.getStartColumn());
201             }
202         }
203         return null;
204     }
205 
206     /**
207      * Sets the node values to the pattern rules.
208      *
209      * @param node           the production node
210      *
211      * @return the new production node
212      *
213      * @throws ParseException if the node analysis discovered errors
214      */
215     protected Node exitProduction(Production node) throws ParseException {
216         ProductionPatternAlternative  alt;
217         ProductionPatternElement      elem;
218         Node                          child;
219 
220         alt = new ProductionPatternAlternative();
221         node.addValue(alt);
222         for (int i = 0; i < node.getChildCount(); i++) {
223             child = getChildAt(node, i);
224             if (child.getId() == GrammarConstants.PRODUCTION_ATOM) {
225                 for (int j = 0; j < child.getValueCount(); j++) {
226                     elem = (ProductionPatternElement) getValue(child, j);
227                     alt.addElement(elem);
228                 }
229             } else if (child.getId() == GrammarConstants.PRODUCTION) {
230                 node.addValues(child.getAllValues());
231             }
232         }
233 
234         return node;
235     }
236 
237     /**
238      * Sets the node value to the production pattern element.
239      *
240      * @param node           the production node
241      *
242      * @return the new production node
243      *
244      * @throws ParseException if the node analysis discovered errors
245      */
246     protected Node exitProductionAtom(Production node)
247         throws ParseException {
248 
249         Node     child;
250         boolean  token = false;
251         int      id = 0;
252         int      min = 1;
253         int      max = 1;
254         Object     obj;
255 
256         // Handle the alternatives
257         child = getChildAt(node, 0);
258         switch (child.getId()) {
259         case GrammarConstants.IDENTIFIER:
260             obj = getValue(child, 0);
261             if (obj instanceof TokenPattern) {
262                 token = true;
263                 id = ((TokenPattern) obj).getId();
264             } else {
265                 token = false;
266                 id = ((ProductionPattern) obj).getId();
267             }
268             break;
269         case GrammarConstants.QUOTED_STRING:
270             token = true;
271             id = ((TokenPattern) getValue(child, 0)).getId();
272             break;
273         case GrammarConstants.LEFT_PAREN:
274         case GrammarConstants.LEFT_BRACE:
275         case GrammarConstants.LEFT_BRACKET:
276             ProductionPatternElement  elem;
277 
278             if (child.getId() == GrammarConstants.LEFT_BRACE) {
279                 min = 0;
280                 max = -1;
281             } else if (child.getId() == GrammarConstants.LEFT_BRACKET) {
282                 min = 0;
283                 max = 1;
284             }
285             elem = getProductionElement(getChildAt(node, 1));
286             token = elem.isToken();
287             id = elem.getId();
288             break;
289         }
290 
291         // Handle optional '?', '*' or '+'
292         child = getChildAt(node, node.getChildCount() - 1);
293         if (child.getId() == GrammarConstants.QUESTION_MARK) {
294             min = 0;
295             max = 1;
296         } else if (child.getId() == GrammarConstants.ASTERISK) {
297             min = 0;
298             max = -1;
299         } else if (child.getId() == GrammarConstants.PLUS_SIGN) {
300             min = 1;
301             max = -1;
302         }
303 
304         // Create production pattern element
305         node.addValue(new ProductionPatternElement(token, id, min, max));
306         return node;
307     }
308 
309     /**
310      * Returns the production pattern element for a production node.
311      * The production node only contains a set of production rules, so
312      * this method normally creates a syntetic production and adds all
313      * the rules to it. If only a single rule was present in the rule
314      * set, and if it contained only an single mandatory element, that
315      * element will be returned instead.
316      *
317      * @param node           the production parse tree node
318      *
319      * @return the production pattern element
320      *
321      * @throws ParseException if the node analysis discovered errors
322      */
323     private ProductionPatternElement getProductionElement(Node node)
324         throws ParseException {
325 
326         ProductionPattern             prod;
327         ProductionPatternAlternative  alt;
328         String                          str;
329 
330         alt = (ProductionPatternAlternative) getValue(node, 0);
331         if (node.getValueCount() == 1 && isSimple(alt)) {
332             return alt.getElement(0);
333         } else {
334             str = currentProduction.getName() + "(" +
335                   (nextSynteticId - 3000) + ")";
336             prod = new ProductionPattern(nextSynteticId, str);
337             prod.setSynthetic(true);
338             for (int i = 0; i < node.getValueCount(); i++) {
339                 alt = (ProductionPatternAlternative) getValue(node, i);
340                 try {
341                     prod.addAlternative(alt);
342                 } catch (ParserCreationException e) {
343                     throw new ParseException(
344                         ParseException.ANALYSIS_ERROR,
345                         e.getMessage(),
346                         node.getStartLine(),
347                         node.getStartColumn());
348                 }
349             }
350             grammar.addProduction(prod,
351                                   node.getStartLine(),
352                                   node.getEndLine());
353             return new ProductionPatternElement(false,
354                                                 nextSynteticId++,
355                                                 1,
356                                                 1);
357         }
358     }
359 
360     /**
361      * Checks if a production pattern alternative contains a single
362      * mandatory element.
363      *
364      * @param alt            the production pattern alternative
365      *
366      * @return true if the alternative is simple, or
367      *         false otherwise
368      */
369     private boolean isSimple(ProductionPatternAlternative alt) {
370         return alt.getElementCount() == 1
371             && alt.getMinElementCount() == 1
372             && alt.getMaxElementCount() == 1;
373     }
374 }
375
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags