An Application of Probabilistic Grammars to Efficient Machne Translation

Main Article Content

Paweł Skórzewski


In this paper we present one of the algorithms used to parse probabilistic context-free grammars: the A* parsing algorithm, which is based on the A* graph search method. We show an example of application of the algorithm in an existing machine translation system. The existing CYK-based parser used in the Translatica system was modified by applying the A* parsing algorithm in order to examine the possibilities of improving its performance. This paper presents the results of applying the A* algorithm with different heuristic functions and their impact on the performance of the parser.


Download data is not yet available.

Article Details

Jak cytować
Skórzewski, P. (2010). An Application of Probabilistic Grammars to Efficient Machne Translation. Investigationes Linguisticae, 21, 90-98.


  1. Caraballo, S.A., Charniak, E.: New Figures of Merit for Best-First Probabilistic Chart Parsing. Computational Linguistics 24, pp. 275-298 (1998)
  2. Charniak, E., Goldwater, S., Johnson, M.: Edge-Based Best-First Chart Parsing. In Proceedings of the Sixth Workshop on Very Large Corpora, pp. 127-133 (1998)
  3. Klein, D., Manning, C.D.: A* Parsing: Fast Exact Viterbi Parse Selection. In Proceedings of the Human Language Technology Conference and the North American Association for Computational Linguistics (HLT-NAACL), pp. 119-126 (2003)
  4. Manning, C.D., Sch¨utze, H.: Foundations of Statistical Natural Language Processing. Prentice Hall, New Jersey (2000)
  5. Ratnaparkhi, A: Learning to Parse Natural Language with Maximum Entropy Models. Machine Learning 34, pp. 151-175 (1999)
  6. Roark, B.: Probabilistic Top-Down Parsing and Language Modeling. Computational Linguistics 27, pp. 249-276 (2001)
  7. Skórzewski, P.: Efektywny parsing je¸zyka naturalnego przy u˙zyciu gramatyk probabilistycznych (Efficient Natural Language Parsing Using Probabilistic Grammars). Master Thesis on Adam Mickiewicz University, Pozna´n (2010)
  8. Skórzewski, P.: Effective Natural Language Parsing With Probabilistic Grammars). In Proceedings of Computational Linguistics – Applications, pp. 175-178. Wisła (2010)