A Variant of Earley Parsing

Details A Variant of Earley Parsing A Variant of Earley Parsing

1998-08-31

arxiv.org/abs/cmp-lg/9808017v1

AI*IA 97: Advances in Artificial Intelligence, 5th Congress of the Italian Association for Artificial Intelligence, LNAI 1321,

Computer Science

Computation and Language

12 pages, 1 Postscript figure, uses psfig.tex and llncs.sty

Scientific paper

The Earley algorithm is a widely used parsing method in natural language processing applications. We introduce a variant of Earley parsing that is based on a ``delayed'' recognition of constituents. This allows us to start the recognition of a constituent only in cases in which all of its subconstituents have been found within the input string. This is particularly advantageous in several cases in which partial analysis of a constituent cannot be completed and in general in all cases of productions sharing some suffix of their right-hand sides (even for different left-hand side nonterminals). Although the two algorithms result in the same asymptotic time and space complexity, from a practical perspective our algorithm improves the time and space requirements of the original method, as shown by reported experimental results.

Affiliated with

Also associated with

No associations

Rating

A Variant of Earley Parsing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Variant of Earley Parsing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Variant of Earley Parsing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-503072