Shift-Reduce Parsing
Learn the mechanics of transition-based parsing algorithms used in state-of-the-art dependency parsers.
Transition-Based Parsing (Shift-Reduce)
How does an algorithm actually construct a Dependency tree in code? The most famous algorithm is the Shift-Reduce Parser. It reads words one by one and uses a stack data structure to draw grammatical arrows incrementally as it processes the sentence left-to-right.
This algorithm runs in highly efficient O(N) time complexity, the primary reason spaCy uses it for its lightning-fast dependency parser.
The Three Core Data Structures
- The Buffer: A queue containing all the words waiting to be read.
- The Stack: LIFO structure holding words currently being processed.
- The Output Memory: A list of the dependency linkages `(Head → Dependent)` mapped out so far.
The 3 Possible Actions
1. SHIFT
Move the first word from the Buffer onto the top of the Stack.
2. LEFT-ARC
Draw an arrow from the 2nd token on the stack to the 1st token on stack. Then Pop the 1st token.
3. RIGHT-ARC
Draw an arrow from the 1st token on the stack to the 2nd token on stack. Then Pop the 2nd token.
Example Walkthrough: "I saw John"
| Step | Action Taken | Stack (Top is right) | Buffer (Next is left) | Link Created |
|---|---|---|---|---|
| 0 | Initialize | [ROOT] | ["I", "saw", "John"] | None |
| 1 | SHIFT | [ROOT, "I"] | ["saw", "John"] | None |
| 2 | SHIFT | [ROOT, "I", "saw"] | ["John"] | None |
| 3 | LEFT-ARC | [ROOT, "saw"] | ["John"] | saw → I (nsubj) |
| 4 | SHIFT | [ROOT, "saw", "John"] | [] | None |
| 5 | RIGHT-ARC | [ROOT, "saw"] | [] | saw → John (dobj) |
| 6 | RIGHT-ARC | [ROOT] | [] | ROOT → saw (root) |
Note: Originally, parsers used heuristic rules to decide which action to take. Modern parsers train a Neural Network classification model to look at the stack at any given frame and mathematically classify whether it should output Shift, Left, or Right!