Context-Free Grammars and Recursive Transition Networks

• Recognition (is the sentence grammatical?), parsing (what is the structure of the sentence?), generation (creating structured sentences from a grammar)
• Recognition, parsing, and generation as search
• Syntax is recursive.
  • I borrowed a hammer from the guy who lives next to the grocery store where you always buy that stuff that you put in that Italian dish that you make when you invite me over for one of those dinners where you also invite the kind of people you'd expect to meet late at night in a bus station not really waiting for a bus but ...
  • For recognition or parsing, finite-state machines will not suffice; we need a stack
• 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
    

• 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" ("#").

    

    

    

• An 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.