Abstract
Syntactic parsing is a fundamental task in Natural Language Processing, yet it faces significant challenges due to the inherent ambiguity of natural languages like Chinese. This paper introduces an extended Generalized LR (GLR) parsing algorithm that utilizes a novel grammar formalism termed PCFG*. By integrating both rule-based constraints and statistical metrics—specifically probability and frequency—the proposed system effectively resolves shift-reduce conflicts and prunes the search space. Experimental results on the Penn Chinese Treebank show that the system achieves high precision in both shallow "base noun phrase" identification and full syntactic parsing.
Introduction
Determining the grammatical structure of sentences is essential for downstream NLP tasks. However, parsers frequently encounter "conflicts," such as deciding whether to shift a new token onto the stack or reduce existing tokens into a phrase. While Tomita’s GLR algorithm provides a robust framework for handling complex grammars, its efficiency and accuracy can degrade under the high ambiguity of natural language. Purely rule-based systems often lack the flexibility of real-world usage, while purely statistical systems may overlook rigid grammatical constraints. This research bridges this gap for Chinese by using statistical data to prune the search space and resolve parsing ambiguities.
Methodology
The PCFG* Formalism
The authors propose PCFG* (Extended Probabilistic Context-Free Grammar), which enhances standard PCFGs by assigning two distinct statistical attributes to each rule:
- Probability ($p$): The relative likelihood of a rule compared to others sharing the same left-hand side.
- Frequency ($f$): The absolute count of the rule's occurrences within the training corpus.
This dual-metric approach allows the parser to adapt its decision-making based on the specific parsing task. For instance, full syntactic parsing relies more heavily on relative probability, whereas shallow parsing tasks like base noun phrase (baseNP) identification benefit more from absolute frequency.
Extended GLR Parsing Algorithm
The standard GLR algorithm was modified to incorporate a hierarchical conflict resolution strategy:
- Reduce-First Priority: When both shift and reduce actions are available, the parser prioritizes the "reduce" action to simplify the decision path.
- Statistical Tie-Breaking: If multiple reduction rules are applicable, the parser uses PCFG* metrics (probability or frequency) to determine the optimal sequence. Interestingly, the researchers found that probability is the most reliable guide for deep parsing, while frequency is superior for shallow pattern recognition.
- Pruning Mechanism: To prevent the exponential growth of parsing branches, the system limits the number of rule candidates per branch to a maximum of 20. This "reasonable pruning" ensures computational efficiency without significantly compromising accuracy.
Experimental Evaluation
The system was trained and tested using the Penn Chinese Treebank, comprising 10,000 gold-standard sentences. The dataset was split into training and testing sets for two primary tasks: baseNP identification and full syntactic parsing.
Results
The performance metrics demonstrate the effectiveness of the hybrid approach:
| Task | Precision | Recall | Rule Count |
|---|---|---|---|
| BaseNP Identification | 87.42% | 81.4% | 400 |
| Full Syntactic Parsing | 70.56% | 67.77% | 2000 |
The results indicate that the extended GLR algorithm is particularly effective at shallow parsing (baseNP), while still providing a solid foundation for the much more complex task of full sentence decomposition.
Conclusion
The integration of PCFG* with an extended GLR algorithm provides a powerful framework for Chinese syntactic parsing. By balancing grammatical rules with statistical evidence, the system achieves a robust performance profile. Future work will focus on refining pruning strategies to avoid losing rare but valid structures and integrating baseNP results to bootstrap full parsing accuracy.
Summary updated