<p>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).</p>

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

<p>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).</p>

<p>The complexity is at worst $O(n^3)$ for parsing and <a href="http://repository.cmu.edu/cgi/viewcontent.cgi?article=2751&amp;context=compsci" rel="nofollow">$O(n^{2.373})$</a> (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 <a href="http://acl.ldc.upenn.edu/P/P97/P97-1002.pdf" rel="nofollow">believed to require more</a> (though the exact
complexity bound is not known), even for simple recognition.</p>

<p>I do not really know if these complexity hierarchies have been
identified precisely.</p>

<p>The <a href="https://en.wikipedia.org/wiki/Context-free_grammar#Subclasses" rel="nofollow">usual hierarchies</a> studied for context-free grammars are often more
related to the applicability of techniques that can be used to build
parsers for these grammars.</p>

<p>As the question is stated, I guess there is one language that is faster than any other to recognize. That is the <a href="https://en.wikipedia.org/wiki/The_Library_of_Babel" rel="nofollow">Babel language</a> 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.</p>

<p>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.</p>

<p>I guess the fasted interesting class of CF grammars is the class parsable in linear-time. <a href="https://en.wikipedia.org/wiki/Deterministic_context-free_grammarttps%3a" rel="nofollow">Deterministic CF grammars</a> 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.</p>

CC BY-SA 3.0
2014-03-24T17:11:50.200Z
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.
user2485710
CC BY-SA 3.0
2014-03-24T17:19:58.617Z
Then this was probably not the right site to ask, as it more theoretical computer science. Your question would probably be more appropriate in http://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.
babou
CC BY-SA 3.0
2014-03-24T17:31:33.323Z
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.
user2485710
CC BY-SA 3.0
2014-03-24T17:50:38.780Z
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.
babou
CC BY-SA 3.0
2014-03-25T09:07:43.350Z
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 ?
user2485710
CC BY-SA 3.0
2014-03-25T10:27:40.037Z
My answer is that I do not understand what are your criteria and
constraints. For one thing, you should identify in what way, if any,
the type of language you are interested in (markup?) is specific and
whether it should have an impact on the chosen technology. You can
consider that input is very long, thus requiring linearity. You can
also think that it is well parenthesized for the most part, with only
small identified fragments being syntactically complex, which could
considerably mitigate the requirement for linearity, thus allowing
more complex techniques limited to these small fragments.
babou
CC BY-SA 3.0
2014-03-25T10:43:14.410Z
My own bias goes to general CF parsers. But many systems are
probably too naive about this technology, and I have little pragmatic
experience. The question I would ask: - When designing as system
with an important language components, what criteria should I consider
for choosing a syntactic formalism, a parsing technology or a specific
parser for the syntactic part of the system? - examples are parsing
speed, ease of syntax design, evolutivity and maintenance of syntax,
extensibility, interactivity (by designer, or by users), modularity,
code size, space requirements, on-the-shelf availability
babou
CC BY-SA 3.0
2014-03-25T10:49:00.740Z
I forgot: specifics of the application domain may also give criteria, as I described for markup languagI forgot: specifics of the application domain may also give criteria,
as I described for markup languages above. Possibly also whether
things are compiled or interpreted, whether you intend to use an intermediate
form (abstract syntax).  This is only brain storming ... I am not
saying all of this is relevant, only that it might be considered to
see whther it impacts the choice of a formalism or technology.es above.
babou
CC BY-SA 3.0
2014-03-24T16:44:55.073Z
2014-03-24T16:44:55.073Z
babou
<p>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 ?</p>

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

<grammars><parsing>
Define the properties of a grammar that is the fastest to parse
user2485710
# Define the properties of a grammar that is the fastest to parse

(Asked by: username_0 on 2014-03-24)

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 ?

**Tags:** grammars, parsing

---

## 1 answers

### Answer by username_1 on 2014-03-24. Score: 2 | Accepted answer

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})$](http://repository.cmu.edu/cgi/viewcontent.cgi?article=2751&context=compsci) (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](http://acl.ldc.upenn.edu/P/P97/P97-1002.pdf) (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](https://en.wikipedia.org/wiki/Context-free_grammar#Subclasses) 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](https://en.wikipedia.org/wiki/The_Library_of_Babel) 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](https://en.wikipedia.org/wiki/Deterministic_context-free_grammarttps%3a) 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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: Then this was probably not the right site to ask, as it more theoretical computer science. Your question would probably be more appropriate in http://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.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: 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 ?  
> **username_1**: My answer is that I do not understand what are your criteria and constraints. For one thing, you should identify in what way, if any, the type of language you are interested in (markup?) is specific and whether it should have an impact on the chosen technology. You can consider that input is very long, thus requiring linearity. You can also think that it is well parenthesized for the most part, with only small identified fragments being syntactically complex, which could considerably mitigate the requirement for linearity, thus allowing more complex techniques limited to these small fragments.  
> **username_1**: My own bias goes to general CF parsers. But many systems are probably too naive about this technology, and I have little pragmatic experience. The question I would ask: - When designing as system with an important language components, what criteria should I consider for choosing a syntactic formalism, a parsing technology or a specific parser for the syntactic part of the system? - examples are parsing speed, ease of syntax design, evolutivity and maintenance of syntax, extensibility, interactivity (by designer, or by users), modularity, code size, space requirements, on-the-shelf availability  
> **username_1**: I forgot: specifics of the application domain may also give criteria, as I described for markup languagI forgot: specifics of the application domain may also give criteria, as I described for markup languages above. Possibly also whether things are compiled or interpreted, whether you intend to use an intermediate form (abstract syntax).  This is only brain storming ... I am not saying all of this is relevant, only that it might be considered to see whther it impacts the choice of a formalism or technology.es above.  

---

