Charty (version 0.2)
/Users/dcavar/Documents/Teaching/DGfS Herbstschule 2005/Code/Charty/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:
list of edges
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
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
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 <firstname.lastname@example.org>
|DEBUG = 0|
__author__ = 'Damir Cavar'
__version__ = '0.2'
chart = 
grammar = <PSGPars.PSG instance at 0xafee0>
grammarfile = 'PSG1.txt'
inputlength = 0