If the language is implementable as mere DFA (i.e. it's a regular language), then why would one need a parsing algorithm such as Earley.

Regular languages are a subset of context-free languages, but what advantages would call for Earley over a DFA in the case of a regular language?

E.g. in this example: https://en.wikipedia.org/wiki/Earley_parser#Example

Couldn't this be as well implemented simply as a DFA (or "DFA scanner")?

  • 4
    $\begingroup$ What do you think? What reading did you do to try to answer this question yourself? The wikipedia page clearly states that Earley parsers parse context-free languages, which includes all regular languages. $\endgroup$ – David Richerby Dec 28 '15 at 17:51
  • $\begingroup$ @DavidRicherby The question concerns the "reasons" for using Earley over a DFA. Not whether Earley can replace the DFA. $\endgroup$ – mavavilj Dec 28 '15 at 17:57
  • 2
    $\begingroup$ @mavavilj, there are context free languages that can not be recognized by DFAs, and the Earley parser does handle all context free languages. $\endgroup$ – vonbrand Dec 28 '15 at 20:26
  • $\begingroup$ If you actually stated the more precise question you wanted to ask, you wouldn't get these ugly downvotes. Why not state that question in the title? $\endgroup$ – reinierpost Dec 29 '15 at 10:45

The context free languages are a strict superset of the regular languages, meaning that all regular languages are context free and there's at least one context-free language that isn't regular. As a result, any algorithm that can parse arbitrary CFLs can be used to recognize regular languages.

In the example you linked, you are absolutely right that the grammar provided describes a regular language and in principle if you were just trying to build a recognizer for it you could just use a DFA. Using Earley's algorithm has a few advantages, though. One big one is that, since the language is described as a CFG, you can extract a parse tree from the Earley parser when a string is in the language, meaning that you can recover the structure of the formula. This isn't something that DFAs can do by themselves.

As for whether Earley parsers can handle all CFLs and whether they're just extensions of DFAs, yes, Earley parsers can handle any CFL, and in some sense, yes, they're kind of extensions of DFAs. Context-free languages have an associated class of automaton called a pushdown automaton that is essentially a finite automaton hooked up to a parsing stack. Many context-free parsing algorithms, including LR parsers and Earley parsers, are essentially pushdown automata whose states control the stack.

| cite | improve this answer | |
  • $\begingroup$ You mean that Earley parser does generate the whole syntax tree, whereas a DFA doesn't, rather, it merely "reads through the transitions", but does not remember all the earlier ones? $\endgroup$ – mavavilj Dec 28 '15 at 17:36
  • $\begingroup$ @mavavilj Yes, that's right. $\endgroup$ – templatetypedef Dec 28 '15 at 17:44
  • 1
    $\begingroup$ One may note that Earley parsers can deal with every context-free grammar; many other parsing algorithms need grammars of a certain form. $\endgroup$ – Raphael Dec 29 '15 at 12:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.