It's possible to define the properties of a grammar that is fast to parse as it is indeed possible to classify algorithm based on their complexity ?

In other words it's possible to evaluate and define grammars based on their "computational" properties/behaviour ?


1 Answer 1


Your question is unclear. When you write "parse", do you actually mean to produce a parse structure (one, or all possible ones). How do you define it ? For example, some grammars have a parse tree that differs from the derivation tree. Or did you mean that the language must be fasted to recognize? Regular grammars give you languages that are recognized in linear time. What qualifies as a grammar? Actually, if you are just interested in recognition, you are looking for properties of languages rather than properties of grammar (though they can be related).

You can certainly build hierarchies of grammars according to complexity criteria if you clarify the above.

For example in the case of Context-Free grammar, the is nearly a well defined concept of parsing (up to specifying whether you want one parse tree or all possible parse trees).

The complexity is at worst $O(n^3)$ for parsing and $O(n^{2.373})$ (due to valiant, with a looser bound at the time) for recognition (wich is only asymptotic, and not the fastest in any realistic situation). There are CF grammar that will parse in linear time (notably deterministic grammars), others will parse in $O(n^2)$ time, and others are believed to require more (though the exact complexity bound is not known), even for simple recognition.

I do not really know if these complexity hierarchies have been identified precisely.

The usual hierarchies studied for context-free grammars are often more related to the applicability of techniques that can be used to build parsers for these grammars.

As the question is stated, I guess there is one language that is faster than any other to recognize. That is the Babel language invented (nearly) by Jorge Luis Borges and containing all possible string (Borges was unfortunately limited to a finite size due to paper shortage, which would invalidate what I am saying). With all strings of any size, recognition is easy. You start in an accepting state and terminate in 0 steps. The empty language is recognized as fast. I believe these are the only ones recognized in 0 steps (for a given alphabet). This establishes that, if the alphabet is fixed, the class of languages recognizable in 0 time is closed under complementation.

This is of course in jest, but you can see from it that one can define languagesn and corresponding grammars, that can be recognized in constant time, by putting constraints only on a finite prefix of strings. They are not much more interesting. The problem is in the statement of the question.

I guess the fasted interesting class of CF grammars is the class parsable in linear-time. Deterministic CF grammars are clearly member of that class, so that is a sufficient property. However many non-deterministic languages, having no deterministic grammars, can also be parsed in linear time.

  • $\begingroup$ at the moment I'm asking this because I'm interested in markup languages, something like TeX/LaTeX, markdown, html, and so on. I assume that this qualifies my case for using context-free grammar, my point is to outline pitfalls and avoid a bad design of the language itself. $\endgroup$ Mar 24, 2014 at 17:11
  • $\begingroup$ Then this was probably not the right site to ask, as it more theoretical computer science. Your question would probably be more appropriate in cs.stackexchange.com . What you probably want is standard CF parsing, most likely deterministic parsers in the LR/LL families. There are lots of ready-made such parsers available on the net, and probably one at least in the programming language you want to use (whatever it is). Stressing parser speed may not have been a good idea in this context. $\endgroup$
    – babou
    Mar 24, 2014 at 17:19
  • $\begingroup$ I know a couple of options on how to get a working parser, my focus is more theoretical in the sense that I would like to design a language that is easy to handle for my parser. $\endgroup$ Mar 24, 2014 at 17:31
  • $\begingroup$ That is quite a different issue. In the way the answer is clear-cut: there are syntaxes it can handle, and others it cannot. If you already chose the parser, all you can do is adapt, at least for linear time parsers. For more general parser, that can handle all CF languages, the choice of the grammar may have an effect on speed, and possibly on other issues (ambiguity). You may also want to worry about error detection and recovery facilities.- - - - But this discussion would not qualify as theoretical here. $\endgroup$
    – babou
    Mar 24, 2014 at 17:50
  • $\begingroup$ so your answer is "just start with it and correct problems as you go" ? My point is not to use the parser generators that I know, I don't want to rush to that, I'm still interested in what makes a language easy to parse and easy to handle. Plus parser generators are always piece of software and when dealing with them I could find bugs or weirdos that are not really about my language, so having a theoretical basis always helps in my opinion. How do you suggest to re-phrase this question ? $\endgroup$ Mar 25, 2014 at 9:07

Your Answer

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

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