Charty.py
This is a small incremental bottom-up chart parser for context free grammars.
 
(C) 2005 by Damir Cavar
 
This code is written and distributed under the
GNU General Public License which means that its
source code is freely-distributed and available
to the general public.
 
See http://www.gnu.org/copyleft/gpl.html for details
on the license or the the file gpl.txt that should always be
distributed with this code.
 
 
Used data structures:
 
chart:
        list of edges
 
 
edge:
        list of integers and symbols
        [start, end, dotindex, LHS, RHS]
        start:    integer, start of the edge
        end:      integer, end of the edge
        dotindex: integer, position of the dot in the RHS
        LHS:      string, left-hand side symbol
        RHS:      list of strings, symbols in right-hand side
 
 
Properties:
Incremental (left-to-right) bottom-up chart parser.
Select only potentially appropriate rules from grammar
        - length of RHS is less or equal to remaining words/symbols
 
 
Processing steps:
        Word by word:
                Initialise chart with word (add edge for word)
                Do until no further improvement:
                        Add new rules from grammar that consume inactive edges
                        Apply the fundamental rule to induce new edges
 
 
This code can be opimized. However, its main purpose is to help
students understand how simple chart parsing works. If there are any bugs,
please let me know: Damir Cavar <dcavar@indiana.edu>

Modules
		PSGPars sys

Functions
		fundamentalRule() The fundamental rule of chart parsing generates new edges by combining fitting active and inactive edges. getParse(inputlength, chart) Returns a list of all parses in bracketing notation. isActive(edge) Return 1 if edge is active, else return 0. isInactive(edge) Return 1 if edge is active, else return 0. match(aedge, iedge) Returns 1 if the active edge and the inactive edge match, otherwise 0. parse(input) Parse a list of tokens. ruleInvocation(lststart) Add all the rules of the grammar to the chart that are relavant:      Find the rule with the LHS of edge as the leftmost RHS      symbol and maximally the remaining length of the input. structToStr(edges) Returns a string representation of the parse with labled brackets.

Data
		DEBUG = 0 __author__ = 'Damir Cavar' __version__ = '0.2' chart = [] grammar = <PSGPars.PSG instance at 0xafee0> grammarfile = 'PSG1.txt' inputlength = 0

Author
		Damir Cavar