I'm trying to figure out how the parser algorithm of Harkema 2000 works. It is a bottom-up parser that uses an agenda-driven, chart-based deduction procedure, but what is not clear to me is in what order the items are added to the chart, or, in any case, how the parser deals with discontinuous constituents, which is a distinct aspect in comparison to other bottom-up parsers as the shift-reduce parser or the CYK.

Here is an example of a parse of 1234 given a grammar with movement features (+k,-k):

s:  (0,1,_8648):=b a -p
s:  (1,2,_8648):=d +p c
s:  (2,3,_8638):b -q
s:  (3,4,_8648):=a +q d
c:  (0,1,_8676):a -p   (2,3,_8680):-q
c:  (3,4,_8716):+q d   (0,1,_8720):-p   (2,3,_8720):-q
c:  (2,4,_8670):d   (0,1,_8674):-p
c:  (1,4,_8674):+p c   (0,1,_8678):-p
c:  (0,4,_8626):c

In line 5, the constituents (0,1) and (2,3) merge, even though they are not adjacent. As far as I know, this couldn't have happened in a classic shift-reduce parser or something similar.

Here is an implementation of this parser, but in Prolog, a language that I don't know very well.

Thank you in advance.

1 Answer 1


I’ll try to help. This is advanced for me; so my answer contains some questions which I can update.

Minimalist grammars:

  • The paper contains a recognizer for a minimalist grammar, not a parser.

  • A minimalist grammar is:

  • V: vocabulary (words, terminal symbols)

  • Cat: categories? (non-terminal symbols)

  • Lex: “lexical expressions”? (multi-word expressions?)

  • F: functions (rules, like transformation rules)

Each consists of features.

  • Vocabulary consists of:

  • a set of phonetic features P

  • a set of semantic features I

  • Lexical phrases is built from V and Cat.

  • Categories has 4 features:

  • base & select: a syntactic category and its selection feature

  • licensors & licensees (for each licensor there will be a licensee, denoted +y, -y)

  • The features in base and select play a role in merge operations. The features in licensors and licensees regulate movement.

  • A minimalist tree T is a set of nodes N and a function called Label

  • And three relations on N:

  • dominance

  • precedence

  • projection

  • They are reflexive and transitive.

  • Every pair of nodes has a projection hierarchy relationship - x > y

  • Label assigns a feature to a leaf of a tree

  • Label labels nodes with what they are

  • Label selects the base, licensor, and licensee

  • There is some relationship between being a head and something dominating something else, that I don’t understand yet

The recognizer:

  • ** The definition of the recognizer includes:**

  • a specification of a grammatical deductive system

  • a specification of a deduction procedure.

  • The formulae of the deductive system are commonly called items

  • They claims about grammatical properties of strings

  • Under a given interpretation, these claims are either true or false.

For a given input string, the axioms are a set of items that are taken to represent true grammatical claims.

  • Goal items represent the claim that the input string is in the grammar.

  • the objective is to recognize a string by evaluating the truth of the goal items

The deductive system has a set of inference rules for deriving new items from old ones

  • The deduction procedure is a procedure for finding all items that are true, for a given grammar and an input string.

  • Thus, the recognizer can work with any minimalist grammar you supply it.

  • The chart is to hold unique items, to avoid applying the same rule of inference to the same items again.

  • The agenda is for temporarily keeping items whose consequences under the inference rules have not yet been generated.

The algorithm:

  1. Initialize the chart (set of items).

  2. Initialize the agenda (set of axioms).

  3. Remove an item from the agenda. If the item is not in the chart, add it. Generate all items that can be derived by one application of a rule of inference. Add these generated items to the agenda.

  4. Repeat #3 until you obtain a goal item.

So, the algorithm looks pretty simple:

You have some axioms, and you apply the axioms to generate strings, until you generate the string you are seeking, in which case you know the axioms can generate that string, and that the string is a part of the language defined by the axioms.

This is pretty hard 😅 though maybe I’m tired today.

To be continued.

  • 1
    You are just copy-pasting the paper, you are not addressing the question at all. Jul 3, 2023 at 1:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.