RTN Parsing

• Parsing as search

• A context-free grammar for a fragment of English
  • Phrasal categories and lexical categories

    S -> NP VP
    NP -> PN
    NP -> (DET) ADJ* N
    NP -> NP CONJ NP
    VP -> VP PP
    VP -> IV
    VP -> TV NP
    VP -> LV ADJ
    VP -> CV that S
    IV -> IV CONJ IV
    PP -> P NP
    PN -> Toad
    IV -> pushed
    IV -> pulled
    P -> on
    DET -> the
    N -> rake
    CONJ -> and
    

• Corresponding recursive transition networks
  • All rules with the same left-hand side are associated with a single network.
  • Within each network, labels on transitions are phrasal categories, lexical categories, or "jump" ("#").

    

    

    

• A (top-down) RTN parser
  • A state consists of <network/node, sentence-left, waiting-nodes, parse>
  • Three actions
    • Label is phrasal category: push current node on waiting stack, create new constituent for new category
    • Label is lexical category; match word, add category and word to current constituent
    • Constituent is complete: pop waiting node from stack, incorporate constituent in higher-level constituent
  • Algorithm
    • Form a one-element queue containing only the initial state: <S/0, sentence, (), ((S))> (S/0 is the first node in the S network).
    • Until the first state in the queue is a goal node (node is a final node of network, sentence-left and waiting-nodes are empty) or the queue is empty (only way to terminate if exhaustive)
      • Remove the first state from the queue; create new states by extending the first state to all the neighbors of the state.
        For each transition out of node,
        • If the label on the transition is a lexical category and the first word in sentence-left matches the category, return a new state.
        • Else if the label on the transition is jump, return a new state (without consuming any words).
        • Else if the label on the transition is a phrasal category, return a new state (push).
        • Else if node is a final node in network and waiting-nodes is not empty, return a new state (pop).
      • Add the new paths, if any, to the queue.
    • If any goal state is found, return the parse (all parses if the search is exhaustive); otherwise, announce failure.

• An example
  • Toad raked the leaves into a pile.

    PARSE                                        SENTENCE       STACK
    
    ((s))                                        TRTLIAP        ()
    
    ((np) (s))                                   TRTLIAP        (S/2)
    
    (((pn toad) np) (s))                          RTLIAP        (S/2)
    
    (((np (pn toad)) s))                          RTLIAP        ()
    
    ((vp) ((np (pn toad)) s))                     RTLIAP        (S/3)
    
    (((tv raked) vp) ((np ...)))                   TLIAP        (S/3)
    
    ((np) ((tv raked) vp)                          TLIAP        (VP/5 S/3)
     ((np (pn toad)) s))
    
    ...                                                         (VP/5 S/3)
    
    (((np (det the) (n leaves)) (tv raked) vp)       IAP        (S/3)
     ((np (pn toad)) s))
    
    ...                                                         (VP/5 S/3)
    
    ((vp (tv raked) (np (det the) (n leaves))                   (S/3)
         (pp (p into) (np (det a) (n pile))))
     ((np (pn toad)) s))
    
    ((s (np (pn toad))                                          ()
        (vp (tv raked) (np (det the) (n leaves))
            (pp (p into) (np (det a) (n pile))))))
    

[L645 Syllabus]