Contents

• 1  Introduction and Theoretical Background
  • 1.1  Multiple Context Free Grammars
  • 1.2  MCFG String Parsing
  • 1.3  Prefix Parsing as Intersection of (M)CFG and Finite State Automaton
  • 1.4  Probabilistic Parsing and MCFG
  • 1.5  Probabilistic Intersection of a (M)CFG and Finite State Automaton
    • 1.5.1  Inside Probability
    • 1.5.2  Renormalization by Inside Probability
  • 1.6  Entropy
• 2  Quick User Guide to mcfgcky
  • 2.1  Debugging Mode
  • 2.2  Parsing Mode
  • 2.3  Statistical Mode
• 3  Design
  • 3.1  Chart Items
  • 3.2  Inference Rules
  • 3.3  Agenda and Exhauastion Mechanism
  • 3.4  Backpointing
  • 3.5  Output
  • 3.6  Training
  • 3.7  Testing
  • 3.8  Inside
  • 3.9  Surprisal
  • 3.10  Entropy
• 4  Implementation
  • 4.1  Utilities, Basic Data Structures, and Input Modules
    • 4.1.1  Module Utilities
    • 4.1.2  Module MyQueue
    • 4.1.3  Module Seq
    • 4.1.4  Module Mcfgread
    • 4.1.5  Module Fileread
    • 4.1.6  Module Corpread
    • 4.1.7  Module Pcfgead
  • 4.2  Parsing Modules
    • 4.2.1  Module Item
    • 4.2.2  Module Grammar
    • 4.2.3  Module Point
      • 4.2.3.1  Experimental Kilbury Parsing
    • 4.2.4  Module Concat
      • 4.2.4.1  Integrity Checks
      • 4.2.4.2  Sanity Concatenation Checks
      • 4.2.4.3  Concatenation Functions
    • 4.2.5  Module Rules
      • 4.2.5.1  Chart Population Functions
      • 4.2.5.2  Inference Rules
      • 4.2.5.3  Ground Axia/Initial Chart Population
      • 4.2.5.4  Kilbury Style Inference Rules
    • 4.2.6  Module Mcfgcky
      • 4.2.6.1  Experimental Kilbury Stuff
  • 4.3  Statistical Parsing
    • 4.3.1  Module Pcfg
    • 4.3.2  Module Train
    • 4.3.3  Module Inside
    • 4.3.4  Module Test
    • 4.3.5  Module Entropy
      • 4.3.5.1  Stolcke matrix cut trick
  • 4.4  Printing and Output
    • 4.4.1  Module Decompile
    • 4.4.2  Module Output
    • 4.4.3  Module Print