---
title: "An Efficient Context-Free Parsing Algorithm for Natural Languages"
authors:
  - "Masaru Tomita"
doi: ""
url: "https://ijcai.org/proceedings/1985/149"
pdf: "https://ijcai.org/proceedings/1985/0149.pdf"
venue: "Proceedings of the Ninth International Joint Conference on Artificial Intelligence"
year: 1985
pages: "756-763"
track: "Natural Language"
keywords:
---

# An Efficient Context-Free Parsing Algorithm for Natural Languages

Masaru Tomita

*Proceedings of the Ninth International Joint Conference on Artificial Intelligence*, pages 756-763.

## Abstract

This paper introduces an efficient context-free parsing algorithm and emphasizes its practical value in natural language processing. The algorithm can be viewed as an extend ed LR parsing algorithm which embodies the concept of a " graph -structured stack." Unlike the standard LA, the algorithm is capable of handling arbitrary non-cyclic context-free grammars including ambiguous grammars, while most of the LA parsing efficiency is preserved. The algorithm seems more efficient than any existing algorithms including the Cocke-Younger-Kasami algorithm and Earley's algorithm , as far a3 practical natural language parsing is concerned , due to utilization of LA parsing tables. The algorithm is an all -path parsing algorithm; it produces all possible parse trees (a parse forest) in an efficient representation called a "shared-packed forest. " This paper also shows th at Earley's torest representation has a defect and his algorithm cannot be used in natural language processing as an all -path parsing algorithm.