001: /*
002: * xtc - The eXTensible Compiler
003: * Copyright (C) 2004-2007 Robert Grimm
004: *
005: * This program is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU General Public License
007: * version 2 as published by the Free Software Foundation.
008: *
009: * This program is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
012: * GNU General Public License for more details.
013: *
014: * You should have received a copy of the GNU General Public License
015: * along with this program; if not, write to the Free Software
016: * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
017: * USA.
018: */
019: package xtc.lang;
020:
021: import java.util.HashMap;
022:
023: import xtc.tree.Annotation;
024: import xtc.tree.LineMarker;
025: import xtc.tree.Location;
026: import xtc.tree.Node;
027: import xtc.tree.Pragma;
028: import xtc.tree.SourceIdentity;
029:
030: import xtc.util.State;
031:
032: /**
033: * The global state for parsing C. This class provides a simplified
034: * symbol table that is organized as a stack of parsing contexts, with
035: * a new context being pushed onto the stack through {@link #start()}
036: * and popped again through {@link #commit()} or {@link #abort()}.
037: *
038: * @author Robert Grimm
039: * @version $Revision: 1.15 $
040: */
041: public class CParserState implements State {
042:
043: /** A parsing context. */
044: protected static class Context {
045:
046: /** The next context. */
047: public Context next;
048:
049: /**
050: * The flags for this context. The flags from LSB to MSB are:
051: * FLAG_TYPEDEF, FLAG_SCOPE, FLAG_TYPE_SPEC, FLAG_PARAMS,
052: * FLAG_MODIFIED, FLAG_STRUCTURE.
053: */
054: public int flags;
055:
056: /** The bindings for this context, if any. */
057: public final HashMap<String, Boolean> bindings;
058:
059: /** The marked annotation, if any. */
060: public Annotation mark;
061:
062: // ------------------------------------------------------------------------
063:
064: /** Create a new context. */
065: public Context() {
066: bindings = new HashMap<String, Boolean>();
067: }
068:
069: // ------------------------------------------------------------------------
070:
071: /** Clear this context. */
072: public void clear() {
073: if (isSet(FLAG_MODIFIED)) {
074: bindings.clear();
075: }
076: flags = 0;
077: mark = null;
078: }
079:
080: // ------------------------------------------------------------------------
081:
082: /**
083: * Determine whether the specified flag is set.
084: *
085: * @param flag The flag.
086: * @return <code>true</code> if the flag is set.
087: */
088: public boolean isSet(final int flag) {
089: return (0 != (flag & flags));
090: }
091:
092: /**
093: * Set the specified flag.
094: *
095: * @param flag The flag.
096: */
097: public void set(final int flag) {
098: flags |= flag;
099: }
100:
101: /**
102: * Clear the specified flag.
103: *
104: * @param flag The flag.
105: */
106: public void clear(final int flag) {
107: flags &= ~flag;
108: }
109:
110: }
111:
112: // ==========================================================================
113:
114: /** The flag for whether to print debug information to the console. */
115: protected static final boolean DEBUG = false;
116:
117: /** The initial size of the context pool. */
118: protected static final int POOL_INIT = 10;
119:
120: /** The increment of the context pool. */
121: protected static final int POOL_INCR = 5;
122:
123: /** The flag for typedefs. */
124: protected static final int FLAG_TYPEDEF = 0x01;
125:
126: /** The flag for scopes. */
127: protected static final int FLAG_SCOPE = 0x02;
128:
129: /** The flag for having parsed a type specifier. */
130: protected static final int FLAG_TYPE_SPEC = 0x04;
131:
132: /** The flag for having parsed a function parameter list. */
133: protected static final int FLAG_PARAMS = 0x08;
134:
135: /** The flag for having modified the bindings. */
136: protected static final int FLAG_MODIFIED = 0x10;
137:
138: /** The flag for structure/union declaration lists. */
139: protected static final int FLAG_STRUCTURE = 0x20;
140:
141: // ==========================================================================
142:
143: /** The pool of parsing contexts. */
144: private Context pool;
145:
146: /**
147: * The top of the context stack. The implementation assumes that
148: * this field always references at least one context, which
149: * corresponds to the global namespace.
150: */
151: protected Context top;
152:
153: /** The current nesting level. */
154: protected int nesting;
155:
156: /** The current annotation, if any. */
157: protected Annotation annotation;
158:
159: // ==========================================================================
160:
161: /** Create a C parser state object. */
162: public CParserState() {
163: fillPool(POOL_INIT);
164: top = new Context();
165: reset(null);
166: }
167:
168: // ==========================================================================
169:
170: /**
171: * Add the specified number of fresh contexts to the pool.
172: *
173: * @param n The number to add.
174: */
175: protected void fillPool(int n) {
176: for (int i = 0; i < n; i++) {
177: addToPool(new Context());
178: }
179: }
180:
181: /**
182: * Take a context from the pool, refilling the pool if necessary.
183: *
184: * @return A fresh context.
185: */
186: protected Context takeFromPool() {
187: if (null == pool) {
188: fillPool(POOL_INCR);
189: }
190:
191: Context c = pool;
192: pool = c.next;
193: c.next = null;
194: return c;
195: }
196:
197: /**
198: * Return the specified context to the pool, clearing it along the
199: * way.
200: *
201: * @param c The context to return.
202: */
203: protected void addToPool(Context c) {
204: c.next = pool;
205: c.clear();
206: pool = c;
207: }
208:
209: // ==========================================================================
210:
211: /**
212: * Push the specified context onto the context stack.
213: *
214: * @param c The context to push.
215: */
216: protected void push(Context c) {
217: c.next = top;
218: top = c;
219: }
220:
221: /**
222: * Pop a context from the context stack.
223: *
224: * @return The top-most context.
225: */
226: protected Context pop() {
227: Context c = top;
228: top = c.next;
229: c.next = null;
230: return c;
231: }
232:
233: // ==========================================================================
234:
235: public void reset(String file) {
236: if (DEBUG)
237: System.out.println("reset(" + file + ")");
238:
239: // Return all contexts besides the top-level context from the
240: // stack to the pool.
241: while (null != top.next) {
242: addToPool(pop());
243: }
244:
245: // Clear the top-level context.
246: top.clear();
247: top.set(FLAG_SCOPE);
248:
249: // Clear the nesting level.
250: nesting = 0;
251:
252: // Clear any annotations.
253: annotation = null;
254: }
255:
256: public void start() {
257: if (DEBUG) {
258: nesting++;
259: System.out.println("start(" + nesting + ")");
260: }
261:
262: push(takeFromPool());
263: }
264:
265: public void commit() {
266: if (DEBUG) {
267: if (top.isSet(FLAG_SCOPE)) {
268: System.out
269: .println("implied exitScope(" + nesting + ")");
270: }
271: System.out.println("commit(" + nesting + ")");
272: nesting--;
273: }
274:
275: addToPool(pop());
276: }
277:
278: public void abort() {
279: if (DEBUG) {
280: if (top.isSet(FLAG_SCOPE)) {
281: System.out
282: .println("implied exitScope(" + nesting + ")");
283: }
284: System.out.println("abort(" + nesting + ")");
285: nesting--;
286: }
287:
288: addToPool(pop());
289: }
290:
291: // ==========================================================================
292:
293: /** Record a typedef storage class specifier. */
294: public void typedef() {
295: if (DEBUG)
296: System.out.println("typedef()");
297: top.set(FLAG_TYPEDEF);
298: }
299:
300: /** Record a function parameter list. */
301: public void parameters() {
302: if (DEBUG)
303: System.out.println("parameters()");
304: top.set(FLAG_PARAMS);
305: }
306:
307: /** Record a function declarator. */
308: public void functionDeclarator() {
309: if (DEBUG)
310: System.out.println("functionDeclarator()");
311: top.clear(FLAG_PARAMS);
312: }
313:
314: /** Record a type specifier. */
315: public void typeSpecifier() {
316: if (DEBUG)
317: System.out.println("typeSpecifier()");
318: top.set(FLAG_TYPE_SPEC);
319: }
320:
321: /** Enter a new scope. */
322: public void pushScope() {
323: if (DEBUG)
324: System.out.println("pushScope(" + nesting + ")");
325: top.set(FLAG_SCOPE);
326: }
327:
328: /** Exit the last scope. */
329: public void popScope() {
330: if (DEBUG)
331: System.out.println("popScope(" + nesting + ")");
332: top.clear(FLAG_SCOPE);
333: }
334:
335: /** Enter a structure declaration list. */
336: public void enterStructure() {
337: if (DEBUG)
338: System.out.println("enterStructure(" + nesting + ")");
339: top.set(FLAG_STRUCTURE);
340: }
341:
342: /** Exit a structure declaration list. */
343: public void exitStructure() {
344: if (DEBUG)
345: System.out.println("exitStructure(" + nesting + ")");
346: top.clear(FLAG_STRUCTURE);
347: }
348:
349: /**
350: * Implicitly bind the specified identifier. Depending on the
351: * current parsing context, the identifier is either bound as a type
352: * or as an object/function/constant.
353: *
354: * @param id The identifier.
355: */
356: public void bind(String id) {
357: // Ignore the binding if a function parameter list has already
358: // been parsed or the binding appears inside a structure
359: // declaration list.
360: if (top.next.isSet(FLAG_PARAMS)
361: || top.next.isSet(FLAG_STRUCTURE)) {
362: if (DEBUG) {
363: System.out.println("ignoring bind(" + id + ", "
364: + top.isSet(FLAG_TYPEDEF) + ")");
365: }
366: return;
367: } else if (DEBUG) {
368: System.out.println("bind(" + id + ", "
369: + top.isSet(FLAG_TYPEDEF) + ")");
370: }
371:
372: // Get the top-most scope.
373: Context c = top;
374: while (!c.isSet(FLAG_SCOPE)) {
375: c = c.next;
376: }
377:
378: // Record the name.
379: if (c.bindings.containsKey(id)) {
380: if (DEBUG) {
381: System.out.println("ignoring rebinding of " + id);
382: }
383: } else {
384: c.bindings.put(id, top.isSet(FLAG_TYPEDEF) ? Boolean.TRUE
385: : Boolean.FALSE);
386: c.set(FLAG_MODIFIED);
387: }
388: }
389:
390: /**
391: * Explicitly bind the specified identifier.
392: *
393: * @param id The identifier.
394: * @param isType The flag for whether the identifier represents a
395: * type.
396: */
397: public void bind(String id, boolean isType) {
398: if (DEBUG) {
399: System.out.println("bind(" + id + ", " + isType + ')');
400: }
401:
402: // Get the top-most scope.
403: Context c = top;
404: while (!c.isSet(FLAG_SCOPE)) {
405: c = c.next;
406: }
407:
408: // Record the name.
409: if (c.bindings.containsKey(id)) {
410: if (DEBUG) {
411: System.out.println("ignoring rebinding of " + id);
412: }
413: } else {
414: c.bindings.put(id, isType ? Boolean.TRUE : Boolean.FALSE);
415: c.set(FLAG_MODIFIED);
416: }
417: }
418:
419: /**
420: * Determine whether the specified identifier names a type.
421: *
422: * @param id The identifier.
423: * @return <code>true</code> if the specified identifier names a type.
424: */
425: public boolean isType(String id) {
426: // If we have already parsed a type specifier, the identifier does
427: // not name a type.
428: if (top.isSet(FLAG_TYPE_SPEC)) {
429: if (DEBUG)
430: System.out.println("isType(" + id + ") -> false");
431: return false;
432: }
433:
434: // Otherwise, we consult the symbol table.
435: Context c = top;
436:
437: do {
438: while (!c.isSet(FLAG_SCOPE)) {
439: c = c.next;
440: }
441:
442: Boolean value = c.bindings.get(id);
443: if (null != value) {
444: boolean type = value.booleanValue();
445: if (DEBUG)
446: System.out.println("isType(" + id + ") -> " + type);
447: return type;
448: }
449:
450: c = c.next;
451: } while (null != c);
452:
453: if (DEBUG)
454: System.out.println("isType(" + id + ") -> false");
455: return false;
456: }
457:
458: /**
459: * Determine whether a declaration actually is a declaration. This
460: * method determines whether the sequence
461: * <pre>
462: * DeclarationSpecifiers l:InitializedDeclaratorList?
463: * </pre>
464: * can actually represent a declaration. It assumes that any type
465: * specifier encountered while parsing
466: * <code>DeclarationSpecifiers</code> has been marked through {@link
467: * #typeSpecifier()}.
468: *
469: * @param idl The result of parsing the optional initialized
470: * declarator list.
471: * @return <code>true</code> if the declaration is a declaration.
472: */
473: public boolean isValid(Node idl) {
474: return top.isSet(FLAG_TYPE_SPEC) || (null != idl);
475: }
476:
477: // ==========================================================================
478:
479: /**
480: * Record a line marker. Note that string values for the four flags
481: * are interpreted as follows: Any non-null string counts for
482: * <code>true</code>, while null counts for <code>false</code>.
483: *
484: * @see LineMarker
485: *
486: * @param file The file name (without quotes).
487: * @param line The line number.
488: * @param isStartFile The start file flag.
489: * @param isReturnToFile The return to file flag.
490: * @param isSystemHeader The system header flag.
491: * @param isExternC The extern C flag.
492: * @param location The line marker's source location.
493: */
494: public void lineMarker(String file, int line, String isStartFile,
495: String isReturnToFile, String isSystemHeader,
496: String isExternC, Location location) {
497: if (DEBUG)
498: System.out
499: .println("lineMarker(" + file + ": " + line + ")");
500:
501: int flags = 0;
502: if (null != isStartFile)
503: flags |= LineMarker.FLAG_START_FILE;
504: if (null != isReturnToFile)
505: flags |= LineMarker.FLAG_RETURN_TO_FILE;
506: if (null != isSystemHeader)
507: flags |= LineMarker.FLAG_SYSTEM_HEADER;
508: if (null != isExternC)
509: flags |= LineMarker.FLAG_EXTERN_C;
510:
511: LineMarker marker = new LineMarker(line, file, flags, null);
512: marker.setLocation(location);
513: if (null == annotation) {
514: annotation = marker;
515: } else {
516: annotation.innerMost().setNode(marker);
517: }
518: }
519:
520: /**
521: * Record a pragma.
522: *
523: * @see Pragma
524: *
525: * @param directive The actual directive.
526: * @param location The pragma's source location.
527: */
528: public void pragma(String directive, Location location) {
529: if (DEBUG)
530: System.out.println("pragma(" + directive + ")");
531:
532: Pragma pragma = new Pragma(directive, null);
533: pragma.setLocation(location);
534: if (null == annotation) {
535: annotation = pragma;
536: } else {
537: annotation.innerMost().setNode(pragma);
538: }
539: }
540:
541: /**
542: * Record an ident directive.
543: *
544: * @see SourceIdentity
545: *
546: * @param ident The actual identity marker.
547: * @param location The ident directive's source location.
548: */
549: public void ident(String ident, Location location) {
550: if (DEBUG)
551: System.out.println("ident(" + ident + ")");
552:
553: SourceIdentity identity = new SourceIdentity(ident, null);
554: identity.setLocation(location);
555: if (null == annotation) {
556: annotation = identity;
557: } else {
558: annotation.innerMost().setNode(identity);
559: }
560: }
561:
562: /**
563: * Mark the current annotation. This method must be called before
564: * recognizing the nonterminals to be annotated. Furthermore, it
565: * must be called within the context of a stateful production.
566: */
567: public void mark() {
568: if (DEBUG)
569: System.out.println("mark()");
570:
571: if (null == annotation) {
572: top.mark = null;
573: } else {
574: top.mark = annotation.innerMost();
575: }
576: }
577:
578: /**
579: * Annotate the specified node. If any annotations have been
580: * recorded and {@link #mark() marked}, the specified node is
581: * wrapped by those annotations and the outer-most annotation is
582: * returned. Otherwise, the specified node is returned.
583: *
584: * @param node The node.
585: * @return The annotated node.
586: */
587: public Node annotate(Node node) {
588: if (DEBUG)
589: System.out.println("annotate(" + node + ")");
590:
591: if (null != top.mark) {
592: // Find the mark in the next closest context, if it exists.
593: Annotation base = null;
594: Context c = top.next;
595: while (null != c) {
596: if (null != c.mark) {
597: base = c.mark;
598: break;
599: }
600: c = c.next;
601: }
602:
603: // Apply the annotations between the base and current mark to
604: // the specified node, while also preserving any new
605: // annotations.
606: Annotation a = (Annotation) top.mark.getNode();
607: top.mark.setNode(node);
608: if (null == base) {
609: node = annotation;
610: annotation = a;
611: } else {
612: node = base.getNode();
613: base.setNode(a);
614: }
615: top.mark = null;
616: }
617:
618: // Done.
619: return node;
620: }
621:
622: }
|