A graphical tool for exploring chart parsing.
Chart parsing is a flexible parsing algorithm that uses a data structure called a “chart” to record hypotheses about syntactic constituents. Each hypothesis is represented by a single “edge” on the chart. A set of “chart rules” determine when new edges can be added to the chart. This set of rules controls the overall behavior of the parser (e.g. whether it parses top-down or bottom-up).
The chart parsing tool demonstrates the process of parsing a single sentence, with a given grammar and lexicon. Its display is divided into three sections: the bottom section displays the chart; the middle section displays the sentence; and the top section displays the partial syntax tree corresponding to the selected edge. Buttons along the bottom of the window are used to control the execution of the algorithm.
The chart parsing tool allows for flexible control of the parsing algorithm. At each step of the algorithm, you can select which rule or strategy you wish to apply. This allows you to experiment with mixing different strategies (e.g. top-down and bottom-up). You can exercise fine-grained control over the algorithm by selecting which edge you wish to apply a rule to.
A graphical tool for exploring the regular expression based chunk
Finding (and Replacing) Nemo
Instant Regular Expressions Created by Aristide Grange
A graphical tool for exploring the recursive descent parser.
The recursive descent parser maintains a tree, which records the structure of the portion of the text that has been parsed. It uses CFG productions to expand the fringe of the tree, and matches its leaves against the text. Initially, the tree contains the start symbol (“S”). It is shown in the main canvas, to the right of the list of available expansions.
The parser builds up a tree structure for the text using three operations:
- “expand” uses a CFG production to add children to a node on the fringe of the tree.
- “match” compares a leaf in the tree to a text token.
- “backtrack” returns the tree to its state before the most recent expand or match operation.
The parser maintains a list of tree locations called a “frontier” to remember which nodes have not yet been expanded and which leaves have not yet been matched against the text. The leftmost frontier node is shown in green, and the other frontier nodes are shown in blue. The parser always performs expand and match operations on the leftmost element of the frontier.
You can control the parser’s operation by using the “expand,” “match,” and “backtrack” buttons; or you can use the “step” button to let the parser automatically decide which operation to apply. The parser uses the following rules to decide which operation to apply:
- If the leftmost frontier element is a token, try matching it.
- If the leftmost frontier element is a node, try expanding it with the first untried expansion.
- Otherwise, backtrack.
The “expand” button applies the untried expansion whose CFG production is listed earliest in the grammar. To manually choose which expansion to apply, click on a CFG production from the list of available expansions, on the left side of the main window.
The “autostep” button will let the parser continue applying applications to the tree until it reaches a complete parse. You can cancel an autostep in progress at any time by clicking on the “autostep” button again.
- Keyboard Shortcuts::
- [Space] Perform the next expand, match, or backtrack operation [a] Step through operations until the next complete parse [e] Perform an expand operation [m] Perform a match operation [b] Perform a backtrack operation [Delete] Reset the parser [g] Show/hide available expansions list [h] Help [Ctrl-p] Print [q] Quit
Create a recursive descent parser demo, using a simple grammar and text.
A graphical tool for exploring the shift-reduce parser.
The shift-reduce parser maintains a stack, which records the structure of the portion of the text that has been parsed. The stack is initially empty. Its contents are shown on the left side of the main canvas.
On the right side of the main canvas is the remaining text. This is the portion of the text which has not yet been considered by the parser.
The parser builds up a tree structure for the text using two operations:
- “shift” moves the first token from the remaining text to the top of the stack. In the demo, the top of the stack is its right-hand side.
- “reduce” uses a grammar production to combine the rightmost stack elements into a single tree token.
You can control the parser’s operation by using the “shift” and “reduce” buttons; or you can use the “step” button to let the parser automatically decide which operation to apply. The parser uses the following rules to decide which operation to apply:
- Only shift if no reductions are available.
- If multiple reductions are available, then apply the reduction whose CFG production is listed earliest in the grammar.
The “reduce” button applies the reduction whose CFG production is listed earliest in the grammar. There are two ways to manually choose which reduction to apply:
- Click on a CFG production from the list of available reductions, on the left side of the main window. The reduction based on that production will be applied to the top of the stack.
- Click on one of the stack elements. A popup window will appear, containing all available reductions. Select one, and it will be applied to the top of the stack.
Note that reductions can only be applied to the top of the stack.
- Keyboard Shortcuts::
- [Space] Perform the next shift or reduce operation [s] Perform a shift operation [r] Perform a reduction operation [Ctrl-z] Undo most recent operation [Delete] Reset the parser [g] Show/hide available production list [Ctrl-a] Toggle animations [h] Help [Ctrl-p] Print [q] Quit
Create a shift reduce parser app, using a simple grammar and text.
BrowServer is a server for browsing the NLTK Wordnet database It first launches a browser client to be used for browsing and then starts serving the requests of that and maybe other clients
browserver.py -h browserver.py [-s] [-p <port>]
-h or --help Display this help message. -l <file> or --log-file <file> Logs messages to the given file, If this option is not specified messages are silently dropped. -p <port> or --port <port> Run the web server on this TCP port, defaults to 8000. -s or --server-mode Do not start a web browser, and do not allow a user to shotdown the server through the web interface.
Interactive NLTK Applications:
chartparser: Chart Parser chunkparser: Regular-Expression Chunk Parser collocations: Find collocations in text concordance: Part-of-speech concordancer nemo: Finding (and Replacing) Nemo regular expression tool rdparser: Recursive Descent Parser srparser: Shift-Reduce Parser wordnet: WordNet Browser