Is this a some kind of regular grammar?

Hi!


I have a question about a hypothetical grammar construction. The usual
way of parsing involves the usage of a lexer combined with some type
of parser that understands a grammar. One of the most common grammar
type for the parser is LALR(1) because of its speed. There are also
implementation of LL(k) but with high k's this can result in long
processing time.


One of my problems is that sometimes it is impossible for me to
distinguish a token at the lexer stage, because multiple regular
expression can match the same token depending on the context. What I
need is an integrated solution which combines the lexer and the parser
at the same time.


Let's take the LALR(1) grammar for example, what would happen if I
were to "expand" the grammar by replacing the terminal elements (of
the LALR(1) grammar) with a grammatical representation of the regular
expression(s) I used in the lexer to represent this perticular
terminal?


Of course the resulting grammar would not be LALR(1), but is there a
way to build an algorithm that can parse this type of grammar without
going to a full blown N^3? Surely this grammar must fit somewhere
between N^3 and N (for LALR(1).


One thing for sure is that it would be possible to transform the
grammar so that it is possible to verify if an instance of the grammar
matches. Just like you can transform a NFA into a DFA by loosing the
power to say what matched what in the original regular expresssion.
Unfortunately, with the above grammar construction, we would loose the
notion of parse tree in the process (i.e. it would be impossible to
say, ok the document matched now can you show me the detailed
parsing?).


Does anyone know if there are books or articles which deal with these
types of constructions? I believe I heard a name for such a construct
but I am unable to remember what it is...


Thanks!
Daniel Shane

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