197.parser
SPEC CPU2000 Benchmark Description File

Benchmark Name

197.parser

Benchmark Author

Danny Sleator and Dave Temperley

Benchmark Program General Category

Word processing

Benchmark Description

This file does the grungy job of chopping the user's input sentence into words, processing the special commands, and calling all the functions necessary to parse the input sentence.

The following sequence of steps is used to parse:

• Break the input line into appropriate words.
• Construct the dictionary expressions for each of the words.
• Apply expression pruning to these expressions.
• Build the disjuncts for the expressions.
• If the sentence contains a conjunction then:
  • Apply gentle power_pruning
  • Clear out further irrelevant disjuncts with conjunction-pruning.
  • Build the "and" tables and put fat disjuncts on all the words.
  • Apply pruning to the resulting disjuncts.
• Apply ruthless power pruning.
• Exhaustively search for a valid linkage.
• For each of these linkages:
  • If there is a conjunction, expand the sentence into each of the sentences it represents. and apply post-processing to each of these. All must pass, or the sentence is considered to have a violation.
  • If there is not a conjunction, then just postprocess the linkage.
  • Compute the costs of each of the linkage. (A p.p. violation essentially has infinite cost.)
• Sort all the linkages by cost.
• Display the solutions one at a time, according to the whim of the user.

Pruning is always applied before power pruning, because it saves more time in power-pruning than it uses. Power-pruning is said to be "ruthless" in that doing it before generating the and disjuncts will not work -- it will remove too much stuff. Pruning has been modified to be "gentle" -- it doesn't do as much as it might so that it avoids deleting things that are needed after and-disjunct generation. It might be effective to make a ruthless version of pruning, and install it where appropriate.

Input Description

Random text.

Output Description

Echo of the input plus analysis of correctness of grammar.

Programming Language

C

Known portability issues

None

Reference

See http://www.cs.cmu.edu/~sleator for announcements of the latest version, detailed documentation, and rules for commercial use.