ParsingTables


1   /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
2    * This file is part of Beaver Parser Generator.                       *
3    * Copyright (C) 2003,2004 Alexander Demenchuk <alder@softanvil.com>.  *
4    * All rights reserved.                                                *
5    * See the file "LICENSE" for the terms and conditions for copying,    *
6    * distribution and modification of Beaver.                            *
7    * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
8   
9   package beaver;
10  
11  import java.io.ByteArrayInputStream  ;
12  import java.io.DataInputStream  ;
13  import java.io.IOException  ;
14  import java.io.InputStream  ;
15  import java.util.zip.InflaterInputStream  ;
16  
17  /**
18   * Parsing Tables
19   */
20  public final class ParsingTables
21  {
22      /** A table with all actions */
23      private final short[] actions;
24  
25      /**
26       * A table containing the lookahead for each entry in "actions" table.
27       * Used to detect "collisions".
28       */
29      final short[] lookaheads;
30  
31      /**
32       * For each state, the offset into "actions" table that is used to find action for a terminal
33       * that has been fetched from the scanner.
34       */
35      final int[] actn_offsets;
36  
37      /**
38       * For each state, the offset into "actions" table that is used to find a next parser's state
39       * using a nonterminal that has been created by a reduced production.
40       */
41      private final int[] goto_offsets;
42  
43      /** Default action for each state */
44      private final short[] default_actions;
45  
46      /**
47       * A table with encoded production information.
48       * <p/>
49       * Each slot in this table is a "structure":
50       * <pre>
51       *   short lhs_symbol_id ; // Symbol on the left-hand side of the production
52       *   short rhs_length    ; // Number of right-hand side symbols in the production
53       * </pre>
54       * where lhs_symbol_id uses high 16 bit of this structure, and rhs_length - lower 16 bits
55       */
56      final int[] rule_infos;
57  
58      /** ID of the "error" nonterminal */
59      final short error_symbol_id;
60  
61      /** Indicates whether action tables were compressed. */
62      final boolean compressed;
63      
64      /** Number of terminal symbols. */
65      final int n_term;
66  
67      public ParsingTables(Class   impl_class)
68      {
69          this(getSpecAsResourceStream(impl_class));
70      }
71      
72      /**
73       * Ensures that parser tables are loaded.
74       *
75       * @param impl_class class of the instance of the Parser
76       */
77      public ParsingTables(String   spec)
78      {
79          this(new ByteArrayInputStream  (decode(spec)));
80      }
81      
82      private ParsingTables(InputStream   in)
83      {
84          try
85          {
86              DataInputStream   data = new DataInputStream  (new InflaterInputStream  (in));
87              try
88              {
89                  int len = data.readInt();
90                  actions = new short[len];
91                  for (int i = 0; i < len; i++)
92                  {
93                      actions[i] = data.readShort();
94                  }
95                  lookaheads = new short[len];
96                  for (int i = 0; i < len; i++)
97                  {
98                      lookaheads[i] = data.readShort();
99                  }
100                 
101                 len = data.readInt();
102                 actn_offsets = new int[len];
103                 for (int i = 0; i < len; i++)
104                 {
105                     actn_offsets[i] = data.readInt();
106                 }
107                 goto_offsets = new int[len];
108                 for (int i = 0; i < len; i++)
109                 {
110                     goto_offsets[i] = data.readInt();
111                 }
112                 
113                 len = data.readInt();
114                 compressed = len != 0;
115                 if (compressed)
116                 {
117                     default_actions = new short[len];
118                     for (int i = 0; i < len; i++)
119                     {
120                         default_actions[i] = data.readShort();
121                     }
122                 }
123                 else
124                 {
125                     default_actions = null;
126                 }
127                 
128                 int min_nt_id = Integer.MAX_VALUE;
129                 len = data.readInt();
130                 rule_infos = new int[len];
131                 for (int i = 0; i < len; i++)
132                 {
133                     rule_infos[i] = data.readInt();
134                     min_nt_id = Math.min(min_nt_id, rule_infos[i] >>> 16);
135                 }
136                 n_term = min_nt_id;
137                 
138                 error_symbol_id = data.readShort();
139             }
140             finally
141             {
142                 data.close();
143             }
144         }
145         catch (IOException   e)
146         {
147             throw new IllegalStateException  ("cannot initialize parser tables: " + e.getMessage());
148         }
149     }
150     
151     /**
152      * Scans lookaheads expected in a given state for a terminal symbol.
153      * Used in error recovery when an unexpected terminal is replaced with one that is expected.
154      * 
155      * @param state in which error occured
156      * @return ID of the expected terminal symbol or -1 if there is none
157      */
158     final short findFirstTerminal(int state)
159     {
160         int offset = actn_offsets[state];
161         for (short term_id = offset < 0 ? (short) -offset : 0; term_id < n_term; term_id++)
162         {
163             int index = offset + term_id;
164             if (index >= lookaheads.length)
165                 break;
166             if (lookaheads[index] == term_id)
167                 return term_id;
168         }
169         return -1;
170     }
171 
172     /**
173      * Find the appropriate action for a parser in a given state with a specified terminal look-ahead.
174      *
175      * @param state     of a parser
176      * @param lookahead
177      * @return parser action
178      */
179     final short findParserAction(int state, short lookahead)
180     {
181         int index = actn_offsets[state];
182         if (index != UNUSED_OFFSET)
183         {
184             index += lookahead;
185             if (0 <= index && index < actions.length && lookaheads[index] == lookahead)
186             {
187                 return actions[index];
188             }
189         }
190         return compressed ? default_actions[state] : 0;
191     }
192 
193     /**
194      * Find the appropriate action for a parser in a given state with a specified nonterminal look-ahead.
195      * In this case the only possible outcomes are either a state to shift to or an accept action.
196      *
197      * @param state     of a parser
198      * @param lookahead
199      * @return parser action
200      */
201     final short findNextState(int state, short lookahead)
202     {
203         int index = goto_offsets[state];
204         if (index != UNUSED_OFFSET)
205         {
206             index += lookahead;
207             if (0 <= index && index < actions.length && lookaheads[index] == lookahead)
208             {
209                 return actions[index];
210             }
211         }
212         return compressed ? default_actions[state] : 0;
213     }
214 
215     static final int UNUSED_OFFSET = Integer.MIN_VALUE;
216     
217     static byte[] decode(String   spec)
218     {
219         char[] chars = spec.toCharArray();
220         if (chars.length % 4 != 0)
221             throw new IllegalArgumentException  ("corrupted encoding");
222         int len = chars.length / 4 * 3;
223         byte[] bytes = new byte[chars[chars.length - 1] == '=' ? chars[chars.length - 2] == '=' ? len - 2 : len - 1 : len];
224         
225         len -= 3;
226         int ci = 0, bi = 0;
227         while (bi < len)
228         {
229             int acc = decode(chars[ci++]) << 18 | decode(chars[ci++]) << 12 | decode(chars[ci++]) << 6 | decode(chars[ci++]);
230             bytes[bi++] = (byte) (acc >> 16);
231             bytes[bi++] = (byte) (acc >> 8 & 0xFF);
232             bytes[bi++] = (byte) (acc & 0xFF);
233         }
234         int acc = decode(chars[ci++]) << 18 | decode(chars[ci++]) << 12 | decode(chars[ci++]) << 6 | decode(chars[ci++]);
235         bytes[bi++] = (byte) (acc >> 16);
236         if (bi < bytes.length)
237         {
238             bytes[bi++] = (byte) (acc >> 8 & 0xFF);
239             if (bi < bytes.length)
240             {
241                 bytes[bi++] = (byte) (acc & 0xFF);
242             }
243         }
244         return bytes;
245     }
246     
247     static int decode(char c)
248     {
249         if (c <= '9')
250         {
251             if (c >= '0')
252                 return c - '0';
253             if (c == '#')
254                 return 62;
255             if (c == '$')
256                 return 63;
257         }
258         else if (c <= 'Z')
259         {
260             if (c >= 'A')
261                 return c - 'A' + 10;
262             if (c == '=')
263                 return 0;
264         }
265         else if ('a' <= c && c <= 'z')
266             return c - 'a' + 36;
267         throw new IllegalStateException  ("illegal encoding character '" + c + "'");
268     }
269     
270     static InputStream   getSpecAsResourceStream(Class   impl_class)
271     {
272         String   name = impl_class.getName();
273         name = name.substring(name.lastIndexOf('.') + 1) + ".spec";
274         InputStream   spec_stream = impl_class.getResourceAsStream(name);
275         if (spec_stream == null)
276             throw new IllegalStateException  ("parser specification not found");
277         return spec_stream;
278     }
279 }
280 
281
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags