See also: The running applet, documentation, source code, and the whole work package in one archive.
This program implements PT-1, a top-down parser with backtracking described in the tutorial NATURAL LANGUAGE PARSERS. A "Course in Cooking" by Prof. Dr. Peter Hellwig. It allows you to parse a sentence, with the possibility to follow the evolution of the content of the "memory" (the working table, the backtracking store, the parse tree) step by step. In short, it allows you to create a lexicon, a set of grammar rules, enter an utterance and parse it.
The program consists of four modules and visually, that is for the user, of two frames. The first frame contains interfaces for the access to the modules LEXICON, RULES and INPUT; the second frame contains an interface for the control over the module PARSER itself.
You start in the first frame by entering or choosing a sentence (if you wish, you can also change the lexicon and the grammar rules), and then you proceed to the second frame by pressing the button Check Sentence, to verify that only the words from the lexicon are used, and then pressing the button Parse.
In this module you can create, modify or delete lexicon entries. Each entry contains the information about a lexical item, its basic grammatical categories (part of speech, grammatical features).
A predefined lexicon of several words (more precisely, pairs "word - part of speech") can be found here at the start of the program. Using the buttons Add, Edit and Delete, you may modify the lexicon (changing part of speech, for example) or delete all or some of the words (one by one) and enter your own lexicon. While adding a new word, you should enter both the word and its grammatical categories (either by choosing from the predefined list or just by typing those in). If an item can have several different grammatical descriptions (for example, different parts of speech), you have to add the word several times, each time with a new grammatical description.
You can also extend grammatical description of a lexical item by adding other features (for example, person, number or gender: sleeps vi 3 sg). In this version, the parser does not distinguish between different parts of the grammatical description, so that you can as well enter sleeps vi3sg. To make use of the information about the grammatical description, use the same symbol vi3sg in the grammar rules.
This module allows you to create and modify an (ordered) set of production rules of a context-free phrase structure grammar (without left recursion). Each rule must have a form of an expression, which consists of two parts, divided by the arrow. The left hand side of the rule contains a non-terminal constituent, and the rule describes its possible decomposition into constituents (either non-terminal or terminal, e.g. words) which are shown on the right hand side of the rule.
To add a new rule enter the left part and the right part accordingly. The set of rules is always kept ordered according to the following relation: We assume that there is a start symbol (usually S), which is present on the left side of one of the rules, but not on the right sides of the rules. After all rules with the start symbol are put on the top of the list, non-terminal constituents on their right sides are processed (from left to right) and all rules with the same constituent on the left side are put below.
While ordering the rules, the program verifies their wellformedness (press the button Are rules wellformed?): this is limited to the simple verification of the fact that all constituents are either non-terminal (that is, can be found on the left hand side of some rule and hence can be decomposed further) or terminal (there are words in the lexicon with the same grammatical features). If it is not the case, you will see warning messages, but it doesn't prevent the parser from trying to use this grammar. The logical structure and completeness of the grammar are not verified. The creation of a powerful and well-formed grammar, which enables efficient parsing, is the user's responsibility.
This module allows you to enter a sentence for parsing. Instead, you can pick it up from a list of predefined sentences.
By pressing the button Check Sentence you enforce the processing of the input and creation of the input table. The program checks the presence of each word in the lexicon and assigns a position and grammatical categories to each word accordingly. Having verified the input, you can start the parsing process (the button Parse).
This module executes the syntactic analysis of the given sentence according to the "top-down parser with backtracking" prototypes. The description and evaluation of the parser can be found at http://www.cl.uni-heidelberg.de/~hellwig/tutorial.html (PT-1). The parsing algorithm described in this tutorial is realized as a cycle in which all possible states of the parsing processes are considered (from state at start to end of job) and depending of the current state the necessary procedure is called (expansion, recognition, or backtracking). After each step the current state is evaluated again until all available alternatives are examined and the whole parsing process is finished (successfully or not).
On the PARSER frame the list of the grammar rules and the input table with the sentence are shown once again, in order to facilitate the observation of the parsing process by the user. Each step of the parsing procedure is described in the WORKING TABLE, together with explanatory comments.
Under the working table the BACKTRACKING STORE is shown. Here you can see how the backtracking possibilities, stored in a stack, change from step to step.
There are two different ways to follow the parsing procedure: First, you can "parse at once" generating the working table and the backtracking store which contain and show all the steps of the parsing procedure. If the parsing is successful the obtained constituency tree can be seen by pressing the button Constructed tree(s). As the second opportunity, you can "parse step by step", using the Next Step button. In this case the changes in the working table and the stack are shown dynamically, after each step of the parsing algorithm. The button Previous Step allows you to return to the previous state (only one step back is possible).
In the process of the step-by-step parsing you are also able to see the parse tree which corresponds to the current state. In this manner the parsing procedure is visualized and you can see not only the final tree at the end of the parsing but also intermediate "false" trees generated during the process. Some of these trees lead to a dead end rather than to a complete parse tree. All successfully generated complete trees are stored and can be seen at the end by pressing the Constructed tree(s) button.