Re: Grammar to automation translation at runtime (NOT at compile time)?

> I can load a XML schema (can be compared to grammar) and validate a
> XML document dynamically. I understand this is possible in XML
> because of the standardization of syntax (since XML is a meta
> language) and parser reuse at meta language/language level for XML
> based languages. This important syntactic standradization makes
> dynamic XML validation (in the sense of a language conforming to a
> grammar) possible. I could be wrong if XML schemas are refused to
> be considered as a grammar but then there are many XML validation
> technologies are available.




Well, although neatly disguised you can only define regular languages
with XML DTDs or schemas. Construction of Finite State Automatons from
regular grammars is thoroughly understood and very efficient
algorithms exist for it.




> Therefore, my question is if there is any thought/effort to make the
> grammar to automation (a computational service) make available at run
> time? I am interested in CFG based generators (current impls are
> JavaCC, ANTLR).


I think the main problem is speed. The best known algorithm to contruct
a parser for a random CFG has polynomial time complexity. The trick
ANTLR, YACC, etc. use is to restrict the set of allowed grammars from CF
to LL(k) resp. LALR(1). Although construction of those parsers is not
linear in general, actually parsing with them is.


Oliver

Return to the comp.compilers page.
Search the comp.compilers archives again.