I've gone stupid(er) today.
earley-ish algorithm
I'm pretty sure my algorithm from yesterday is wrong (plus it has lots of typos, below is a slightly more typo-free version, plus a little extra work with indices to try to minimise the wrong-ness).
The parser can be wrong for two reasons: it accepts too few things and/or it accepts too many. I think the latter is true. I suspect you can fool my algorithm into accepting pairs of strings where one side of the grammar accepts the left string, and one side of the grammar accepts the right string, but the pair of strings should not be accepted together. There are some choices I need to make here:
- pore over the WASP and Joshua source code - look for references to algorithm used
- ask on the Joshua mailing list
- ask a local grown-up - this may be a great option since there are some local grown-ups who are sure to be able to give me good advice, but I'm... err... feeling shy
- decide that I don't care if my parser is too liberal (and just be sure not to advertise this as a working SCFG parser, but something works enough for me).
fancier debugger
Following the theme of doing stupid but useful things, I seem to be re-inventing the GenI debugger (because I'm trying to figure some stuff out about SCFG parsing). Rather, I've taken my SCFG-specific debugger from a couple of days ago, and moved some code around so that it's generic to anything that uses NLP.ChartParser. (By the way, If you want to teach a parsing course, I think my debugger could be useful for you (although at this stage, you're probably better off with NLTK).
The new debugger is text mode for now. You type in commands to it.
example step
--- chart 5 --- (9 items)
ChartItem {symbol = "VP", beforeDot1 = fromList ["x2"], afterDot1 = [], indices1 = (1,2), beforeDot2 = fromList [], afterDot2 = ["y2"], mIndices2 = Just (0,0)}
ChartItem {symbol = "S", beforeDot1 = fromList ["NP","VP"], afterDot1 = [], indices1 = (0,2), beforeDot2 = fromList [], afterDot2 = ["VP","NP"], mIndices2 = Just (0,0)}
ChartItem {symbol = "S", beforeDot1 = fromList ["NP","VP"], afterDot1 = [], indices1 = (0,2), beforeDot2 = fromList [], afterDot2 = ["VP","NP"], mIndices2 = Nothing}
...
--- agenda 5 --- (1 items)
ChartItem {symbol = "VP", beforeDot1 = fromList ["x2"], afterDot1 = [], indices1 = (1,2), beforeDot2 = fromList ["y2"], afterDot2 = [], mIndices2 = Just (0,1)}
Hit enter for next step or type 'help'
the command set so far
help
Display commands
----------------
help : print this help
agenda : show the full agenda
chart : show the full chart
filter P T value : P = {agenda,chart}, T={symbol}
Navigation commands
-------------------
last : jump to the very last step
quit : (self explanatory)
next INT : (self explanatory)
start over : (self explanatory)
Hit enter for next step or type 'help'
trying out a filter
filter chart symbol S
--- requested filter --- (4 items)
ChartItem {symbol = "S", beforeDot1 = fromList ["NP","VP"], afterDot1 = [], indices1 = (0,2), beforeDot2 = fromList [], afterDot2 = ["VP","NP"], mIndices2 = Just (0,0)}
ChartItem {symbol = "S", beforeDot1 = fromList ["NP","VP"], afterDot1 = [], indices1 = (0,2), beforeDot2 = fromList [], afterDot2 = ["VP","NP"], mIndices2 = Nothing}
ChartItem {symbol = "S", beforeDot1 = fromList ["NP"], afterDot1 = ["VP"], indices1 = (0,1), beforeDot2 = fromList [], afterDot2 = ["VP","NP"], mIndices2 = Nothing}
ChartItem {symbol = "S", beforeDot1 = fromList [], afterDot1 = ["NP","VP"], indices1 = (0,0), beforeDot2 = fromList [], afterDot2 = ["VP","NP"], mIndices2 = Nothing}
Hit enter for next step or type 'help'
I
could go crazy with the filter and write a fancy parser for things so that you can say things like "show me the chart items with symbol S and whose left indices are between, etc etc"... which I may end up deciding I need to do.
code more?
Maybe the key for me is to understand that I understand things through the process of coding. So if I want to do or to wrap my head around anything, I should try to frame it in terms of "what code can I write?"... I dunno if that's going to send me on a lot of wild goose chases, though, the kind of thing where I think I'm productive because I'm doing lots of stuff, but in reality, not actually accomplishing anything.
.png)
.png)
