The head-driven chart parser

The LexGram parser implements the fundamental rule of LexGram in the following manner. Now, substrings are represented by their string positions PhonFrom and PhonTo.

Data structures:

• goal sequent g:

  A quadruple

  PhonFrom,PhonTo,Slash|-GoalCategory

  where PhonFrom and PhonTo are string positions, Slash is an inherited slash value, and GoalCategory is a goal (category).

• constituent c:

  A quadruple

  PhonFrom,PhonTo ; Slash, Category

• head candidate h for a goal sequent g = PhonFrom,PhonTo ; Slash |- GoalCategory:

  A special type of constituent, either

  PhonPos,PhonPos1 ; EMPTY, HeadCategory

  or

  PhonPos,PhonPos ; HeadCategory, HeadCategory

  where, in the first case, HeadCategory is the category of the input word at position PhonPos or, in the second case, it is the single element of the HeadSlash. HeadSlash is the third component of the quadruple. In addition, the following conditions must hold:

  • PhonPos1 equals PhonPos + 1
  • PhonFrom $\leq$ PhonPos, PhonPos1 $\leq$ PhonTo
  • HeadSlash $\subseteq$ Slash
  • The root values of the HeadCategory and of the GoalCategory are unifiable.
• goal table t:

  a pair of a goal sequent and the constituents which have been derived for that goal sequent (possibly none).

• solution s for a goal sequent g = PhonFrom,PhonTo ; Slash |- GoalCategory:

  A septuple

  PhonFrom,PhonFrom1,PhonTo1,PhonTo,SolSlash,RestSlash|-Category

  where

  • the pairs PhonFrom,PhonFrom1, PhonTo1,PhonTo designate the unused parts of the string PhonFrom,PhonTo for deriving the solution
  • SolSlash are the slash categories which have been used for the derivation
  • RestSlash is the unused part of the inherited Slash
  • and Category is an instance of the GoalCategory

'Prove Goal Sequent':

map a goal sequent g on a goal table t

• If g is subsumed by the goal sequent g' of some existing goal table t

  and g' is not an ancestor goal of g

  then return t

• else
  • create an empty goal table t for g
  • for all head candidates h for g
    • add h to the table t
    • 'Fill Arguments' of h for g and t.

'Fill Arguments':

extend the goal table t of goal sequent g = PhonFrom,PhonTo ; Slash |- GoalCategory

with projections of the constituent h = PhonFrom1,PhonTo1 ; HeadSlash, HeadCategory:

• If the list of leaves of the HeadCategory is unifiable with the list of leaves of the GoalCategory

  then add h to t

• else
  • let g' = PhonTo1,PhonTo,ToBindSlash+RestSlash|-GoalCategory'

    where

    • GoalCategory' is the first leaf of HeadCategory
    • if the direction indicated by that leaf is right
    • ToBindSlash is the slash value of that leaf

  • 'Prove Goal Sequent' for g' with resulting goal table t'
  • for all solutions s' =

    PhonTo1,PhonTo1,PhonTo2,PhonTo,SolSlash',RestSlash'|-Category' of g' in t'

    where RestSlash' and ToBindSlash are disjoined

    • add PhonFrom1,PhonTo2 ; HeadSlash+SolSlash' , HeadCategory' to t

      where HeadCategory' is HeadCategory with the first leaf cut off

    • 'Fill Arguments' for

      h' = PhonFrom1,PhonTo2 ; HeadSlash+SolSlash', HeadCategory'

      and g, t

  (direction left analogously).

The LexGram generation algorithm works essentially in the same way. However, as resources it takes a list of essential elements of the input semantics (the 'guide') instead of the input string. For further discussion of head-driven chart parsing see the paper by van Noord [11].