Implement ε-rules (empty rules)

[digitalheir]

The parser currently can't handle rules of the form

X → ε            (p)

where ε is the empty string.

See section 4.7 Null Productions on page 19 of Stolcke's paper.

We have the choice of extending prediction and completion to work with ε-rules, but this is a bit complicated. Another possibility is to rewrite the grammar to eliminate these productions, described at the end of page 20, 4.7.4 Eliminating null productions.

Best to implement the simpler solution first, and implement the philosphically correct version later.

[nlpguyz]

Here is an implementation of Earley that handles Epsilon transition: https://github.com/tomerfiliba/tau/blob/master/Earley.java

Is it possible to port the feature here?

[digitalheir]

It's possible, but not as easily as in the example you give. Dealing with probabilities complicates the issue considerably. Stolcke describes how to it in his paper.

I welcome any work on it, but am not planning to implement it myself.