Как написать CFG для парсера Shift Reduce?

Question

Я пытался написать CFG для использования в реализации NLTK анализатора Shift-Reduce.

Для простого примера, скажем, я хочу разобрать эти два предложения: "Она любит Джона" "Джон любит ее"

Грамматика была бы довольно простой - Джон может быть первым или последним словом, но "Она" может быть только первой, а "ее" может быть только последним. (Очевидно, что "она любит ее" имеет смысл, но "она любит ее" не имеет. Так что это грамматика (ST означает "Старт"):

S -> NP_ST V NP_END
NP_ST -> NP | ST
NP_END -> NP | END
NP -> 'John'
V -> 'loves'
ST -> 'She'
END -> 'her'

Звучит достаточно просто, так в чем же проблема? Что ж, в случае неоднозначности парсер SR просто выберет первый вариант (и, если он потерпит неудачу, он не будет отслеживать второй вариант).

Так что в этом случае "Джон любит ее" прекрасно работает, но "Она любит Джона" терпит неудачу - потому что "Джон" распознается как NP_ST, а не NP_END.

Parsing 'She loves John'
    [ * She loves John]
  S [ 'She' * loves John]
  R [ ST * loves John]
  R [ NPST * loves John]
  S [ NPST 'loves' * John]
  R [ NPST V * John]
  S [ NPST V 'John' * ]
  R [ NPST V NP * ]
  R [ NPST V NPST * ]

И если я переключу строки 2 и 3 в грамматике, произойдет обратное: "Она любит Джона", но "Джон любит ее" терпит неудачу, потому что "Джон" распознается как NP_END, а не NP_ST.

Как мне обойти это? Как мне написать грамматику, которая могла бы принять оба предложения?

Спасибо!