4
$\begingroup$

As described in this paper, you can use an pre-computed automaton to speed up an Earley parse. I'm not interested in the rigorous proof of this, but just how the basic algorithm works so that I can implement it. Understanding this paper on my own would take a long long time, and I don't think it's justified for this algorithm because it seems simple enough, but the paper is accademic and is required to be over my head, so they didn't write it for a reader like me.

For instance, what does a transition labeled with a variable in the automaton mean? How does this thing work?

$\endgroup$
2
  • $\begingroup$ This paper is technically complicated, while the problem it addresses is quite simple. Why do you want to have things explained in the framework of this paper, rather than read a simpler account of how to build such parsers. If you state your purpose ... why you want to implement it for, I may be able to better answer you. Did you look at reference 19 for example. It shows how to do "Earley-like" parsing with any kind of non-deterministic pushdown automation. It has to be expressed with the given primitives operations, but that is easy. $\endgroup$
    – babou
    Sep 29, 2014 at 21:08
  • $\begingroup$ You need to know what an automaton is before anyone can answer your question: en.wikipedia.org/wiki/Finite-state_machine. $\endgroup$
    – Robert Jacobson
    Jun 21, 2019 at 19:01

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.