public static lalr_state build_machine()

in util/src/main/java/java_cup/lalr_state.java [286:428]

• 81 lines of code
• 12 McCabe index (conditional complexity)

  public static lalr_state build_machine(production start_prod) 
    throws internal_error
    {
      lalr_state    start_state;
      lalr_item_set start_items;
      lalr_item_set new_items;
      lalr_item_set linked_items;
      lalr_item_set kernel;
      Stack <lalr_state> work_stack = new Stack <lalr_state> ();
      lalr_state    st, new_st;
      symbol_set    outgoing;
      lalr_item     itm, new_itm, existing, fix_itm;
      symbol        sym, sym2;
      Enumeration   i, s, fix;

      /* sanity check */
      if (start_prod == null)
	throw new internal_error(
 	  "Attempt to build viable prefix recognizer using a null production");

      /* build item with dot at front of start production and EOF lookahead */
      start_items = new lalr_item_set();

      itm = new lalr_item(start_prod);
      itm.lookahead().add(terminal.EOF);

      start_items.add(itm);

      /* create copy the item set to form the kernel */
      kernel = new lalr_item_set(start_items);

      /* create the closure from that item set */
      start_items.compute_closure();

      /* build a state out of that item set and put it in our work set */
      start_state = new lalr_state(start_items);
      work_stack.push(start_state);

      /* enter the state using the kernel as the key */
      _all_kernels.put(kernel, start_state);

      /* continue looking at new states until we have no more work to do */
      while (!work_stack.empty())
	{
	  /* remove a state from the work set */
	  st = (lalr_state)work_stack.pop();

	  /* gather up all the symbols that appear before dots */
	  outgoing = new symbol_set();
	  for (i = st.items().all(); i.hasMoreElements(); )
	    {
	      itm = (lalr_item)i.nextElement();

	      /* add the symbol before the dot (if any) to our collection */
	      sym = itm.symbol_after_dot();
	      if (sym != null) outgoing.add(sym);
	    }

	  /* now create a transition out for each individual symbol */
	  for (s = outgoing.all(); s.hasMoreElements(); )
	    {
	      sym = (symbol)s.nextElement();

	      /* will be keeping the set of items with propagate links */
	      linked_items = new lalr_item_set();

	      /* gather up shifted versions of all the items that have this
		 symbol before the dot */
	      new_items = new lalr_item_set();
	      for (i = st.items().all(); i.hasMoreElements();)
		{
		  itm = (lalr_item)i.nextElement();

		  /* if this is the symbol we are working on now, add to set */
		  sym2 = itm.symbol_after_dot();
		  if (sym.equals(sym2))
		    {
		      /* add to the kernel of the new state */
		      new_items.add(itm.shift());

		      /* remember that itm has propagate link to it */
		      linked_items.add(itm);
		    }
		}

	      /* use new items as state kernel */
	      kernel = new lalr_item_set(new_items);

	      /* have we seen this one already? */
	      new_st = (lalr_state)_all_kernels.get(kernel);

	      /* if we haven't, build a new state out of the item set */
	      if (new_st == null)
		{
	          /* compute closure of the kernel for the full item set */
	          new_items.compute_closure();

		  /* build the new state */
		  new_st = new lalr_state(new_items);

		  /* add the new state to our work set */
		  work_stack.push(new_st);

		  /* put it in our kernel table */
		  _all_kernels.put(kernel, new_st);
		}
	      /* otherwise relink propagation to items in existing state */
	      else 
		{
		  /* walk through the items that have links to the new state */
		  for (fix = linked_items.all(); fix.hasMoreElements(); )
		    {
		      fix_itm = (lalr_item)fix.nextElement();

		      /* look at each propagate link out of that item */
		      for (int l =0; l < fix_itm.propagate_items().size(); l++)
			{
			  /* pull out item linked to in the new state */
			  new_itm = 
			    (lalr_item)fix_itm.propagate_items().elementAt(l);

			  /* find corresponding item in the existing state */
			  existing = new_st.items().find(new_itm);

			  /* fix up the item so it points to the existing set */
			  if (existing != null)
			    fix_itm.propagate_items().setElementAt(existing ,l);
			}
		    }
		}

	      /* add a transition from current state to that state */
	      st.add_transition(sym, new_st);
	    }
	}

      /* all done building states */

      /* propagate complete lookahead sets throughout the states */
      propagate_all_lookaheads();

      return start_state;
    }