ASDParser algorithm details - Part 4: Backtracking the parse

Copyright 2008  James A. Mason  

Because the advance function of ASDParser pushes the local state of the parse onto the stack, backstack, whenever there is a local ambiguity (i.e., more than one choice for advancing the parse), and because of the way the data structure that represents the phrase structure is built (See Part  2.),  it is a fairly simple matter to backtrack the parse to the most recent state of local ambiguity when it encounters a dead-end (i.e., an empty list of choices) in advancing the parse.  The only complication arises because permanent final advances may have been made in some cases since that most recent state of local ambiguity was encountered.  Specifically,  if a permanent advance has been made since a state of local ambiguity occurred, then when a backup is made to that state, the set of remaining choices for advancing the parse from that state may no longer be entirely appropriate.  For example, consider the grammar shown in Figure 1.

    [ example grammar illustrating choices after backup ]

                                      Figure 1

If the string "a b" is parsed with this grammar with S, T, U, and V as expected phrase types, and if the parser is asked to make permanent replacements of uniquely-parsed subphrases (as discussed in Part 2) then the parser finds a first successful parse with the phrase structure

*->nil nil
   T nil
      a 1
      $$ 1
      Y 1
         b 1
      $$ 3

(The phrase structure shown was produced by the ASDTester utility program -- see the software web page.  ASDTester shows the phrase structure flipped on its side, with the top level at the left, with lower levels shown by indenting to the right, and with the character sequence *-> acting as an arrow pointing to the current node, which in this case is the header node.)  If the parser is then asked to advance again, to try for additional successful parses of the phrase, it first backtracks to the previous local state

   nil nil
*->a 1
   Y 1
      b 1

which has been modified by the permanent replacement of the uniquely parsed subphrase "b" by its phrase type "Y". 

At this point the old list of untried choices that is retrieved from the backstack is no longer appropriate, because it includes an advance of type INITIAL to node [ b 1 ], but the word "b" no longer appears at the top level of the phrase structure; it has been replaced by "Y".  So a new list of choices must be computed.  It should include any appropriate NONDUMMY advances and INITIAL advances which might make use of the new next word ("Y" in the example) at the top level of the phrase structure.  It should also include any advances of type DUMMY that have not been tried yet ([ $$ 2 ] in the example), but it should not include advances of type DUMMY that have already been tried ([ $$ 1 ] in the example).

The logic in the foregoing paragraph is applicable if the permanent subphrase replacement occurred following a dummy node ([ $$ 1 ] in the example) that was inserted in the phrase structure and that has disappeared as a result of the backtrack.  If, in contrast to that, the permanent subphrase replacement occurred immediately after the node to which the backtrack has been made, then NONDUMMY advances and INITIAL advances should not be included in the new list of choices, because they will already have been included in the list of choices that was computed as an immediate result of the FINAL advance that produced the permanent subphrase replacement.  (See the advanceFinal subalgorithm in Part 2.)

Here is the source code for the function in ASDParser that performs backtracking and that includes the foregoing logic.  Notice how backup determines whether or not a permanent advance of type FINAL occurred at the next node in the phrase structure after the one to which the parse has backtracked:  If a permanent advance of type FINAL occurred in the advanceFinal function discussed in Part 2, then (and only then) the subphrase pointer of the next node in the phrase structure will have changed from the value that it had before that advance of type FINAL, which value was saved on the the backstack by the advance function (discussed in Part 3) and has been retrieved by backup from the backstack as state.nextNodeSubphrase.

   /**
      Attempts to backtrack the parse state to the most recent
      place where a local ambiguity occurred -- that is, where
      there was more than one choice for advancing.
      @return true if backtrack is successful, false if there
      was no step in the parse to which to backtrack
    */
   public boolean backup()
   {  if (backstack.empty()) return false;
      state = (ASDParseState)backstack.pop();
      if (state.currentNode.nextNode() != null)
         // There is a next node in the phrase structure.
         if (state.currentNode.nextNode().subphrase()
                != state.nextNodeSubphrase)
            // A unique, permanent subphrase parse occurred
            // at the next node.
            if (state.advanceCase == DUMMY)
               // The permanent advance occurred after an
               // intermediate dummy node.  So compute a new
               // list of choices, including any REMAINING
               // dummy choices, for advancing from the
               // current node:
            {  ArrayList dummyNodes = new ArrayList(10);
               ASDParseChoice choice;
               for (int j = 0; j < state.currentChoices.size();
                        ++j)
               {  choice = (ASDParseChoice)state.currentChoices.get(j);
                  if (choice.advanceType == DUMMY)
                     dummyNodes.add(choice.nextNode);
               }
               // dummyNodes is a list of the dummy nodes
               // among the remaining choices.
               state.currentChoices = choices(true, dummyNodes);
            }
            else
               // The permanent advance occurred immediately after
               // the current node.  So non-dummy choices for
               // advancing from the current node have already been
               // tried.  Keep only the remaining dummy alternatives
               // (if any) for advancing from it:
            {  ASDParseChoice choice;
               for (int j = state.currentChoices.size()-1;
                        j >= 0; --j)
               {  choice = (ASDParseChoice)state.currentChoices.get(j);
                  if (choice.advanceType != DUMMY)
                     state.currentChoices.remove(j);
               }
            }
      ++currentParseStepNumber;
      return true;
   } // end backup


ASD Parser algorithm details - Contents

ASD notes and documentation

ASD home page

last modified 2010 Aug 21