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?

  • $\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 '14 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$ Jun 21 '19 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.