KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > beaver > comp > State


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.comp;
10
11 import java.util.HashMap JavaDoc;
12 import java.util.Map JavaDoc;
13
14 import beaver.spec.GrammarSymbol;
15
16 /**
17  * This class represents LALR state.
18  * A state consists of an LALR configuration set and a set of transitions to other states.
19  */
20 class State
21 {
22     static class Factory
23     {
24         private State last_state;
25         private int num_states;
26         private Map JavaDoc states;
27         private Configuration.Set.Factory conf_set_factory;
28
29         Factory(Configuration.Set.Factory conf_set_factory)
30         {
31             states = new HashMap JavaDoc(89);
32             this.conf_set_factory = conf_set_factory;
33         }
34
35         State getState(Configuration.Set core)
36         {
37             State state = (State) states.get(core);
38             if (state == null)
39             {
40                 core.buildClosure();
41                 states.put(core, state = new State(++num_states, core));
42                 if (last_state == null)
43                     last_state = state;
44                 else
45                     last_state = last_state.next = state;
46                 buildShiftsFrom(state);
47             }
48             else
49             {
50                 state.conf_set.appendReversePropagation(core);
51             }
52             return state;
53         }
54
55         private void buildShiftsFrom(State state)
56         {
57             state.conf_set.resetContributionFlags();
58
59             for (Configuration conf = state.conf_set.first_conf; conf != null; conf = conf.next)
60             {
61                 if (conf.has_contributed || conf.isDotAfterLastSymbol())
62                     continue;
63
64                 conf_set_factory.reset();
65
66                 GrammarSymbol marked_symbol = conf.getSymbolAfterDot();
67
68                 // For every configuration in the "from" state which also has the "marked_symbol"
69 // after the "dot" add the same configuration to the core set under construction
70 // but with the mark ("dot") shifted one symbol to the right.
71 for (Configuration nconf = conf; nconf != null; nconf = nconf.next)
72                 {
73                     if (nconf.has_contributed || nconf.isDotAfterLastSymbol() || nconf.getSymbolAfterDot() != marked_symbol)
74                         continue;
75
76                     Configuration new_core_conf = conf_set_factory.addConfiguration(nconf.rule, nconf.dot + 1);
77                     new_core_conf.addReversePropagation(nconf);
78
79                     nconf.has_contributed = true;
80                 }
81                 State new_state = getState(conf_set_factory.getCore());
82
83                 // The state "new_state" is reached from the state "state" by a shift action
84 // on the symbol "marked_symbol"
85 state.actions.add(new Action.Shift(marked_symbol, new_state));
86             }
87         }
88     }
89
90     State next;
91
92     int id;
93     Configuration.Set conf_set;
94     Action.List actions;
95     
96     Action.List terminal_lookahead_actions;
97     Action.List nonterminal_lookahead_actions;
98     Action default_action;
99
100     State(int num, Configuration.Set core)
101     {
102         id = num;
103         conf_set = core;
104         actions = new Action.List(this);
105         terminal_lookahead_actions = new Action.List(this);
106         nonterminal_lookahead_actions = new Action.List(this);
107     }
108     
109     boolean findLookaheads()
110     {
111         boolean more_found = false;
112         for (Configuration conf = conf_set.first_conf; conf != null; conf = conf.next)
113         {
114             if (!conf.has_contributed)
115             {
116                 if (conf.findLookaheads())
117                 {
118                     more_found = true;
119                 }
120                 conf.has_contributed = true;
121             }
122         }
123         return more_found;
124     }
125     
126     void splitActions()
127     {
128         default_action = actions.split(terminal_lookahead_actions, nonterminal_lookahead_actions);
129     }
130 }
131
Popular Tags