Re: Parsing implicit operators with recursive descent?

"Armel" <armelasselin@hotmail.com>
Sat, 7 Feb 2009 18:03:13 +0100

          From comp.compilers

Related articles
Parsing implicit operators with recursive descent? johann@myrkraverk.com (Johann 'Myrkraverk' Oskarsson) (2009-02-06)
Re: Parsing implicit operators with recursive descent? mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2009-02-07)
Re: Parsing implicit operators with recursive descent? armelasselin@hotmail.com (Armel) (2009-02-07)
Re: Parsing implicit operators with recursive descent? torbenm@pc-003.diku.dk (2009-02-09)
Re: Parsing implicit operators with recursive descent? barry.j.kelly@gmail.com (Barry Kelly) (2009-02-12)
Re: Parsing implicit operators with recursive descent? johann@myrkraverk.com (Johann 'Myrkraverk' Oskarsson) (2010-01-30)
Re: Parsing implicit operators with recursive descent? kkylheku@gmail.com (Kaz Kylheku) (2010-02-01)
| List of all articles for this month |

From: "Armel" <armelasselin@hotmail.com>
Newsgroups: comp.compilers
Date: Sat, 7 Feb 2009 18:03:13 +0100
Organization: les newsgroups par Orange
References: 09-02-013
Keywords: parse, LL(1)
Posted-Date: 07 Feb 2009 12:56:52 EST

> Is it possible to parse implicit operators, like the regular
> expression concatenation operator, with a recursive descent parser?
of course, why would not it be possible?


simple rules such as:
RE = terminal | terminal RE
while make you trees for 'aab' such as


(a . (a . (b)))


where parentheses make a single RE match, '.' is the implicit operator and
each a or b represent a match from 'terminal'.


the 'tree' will probably more look like a list though, it can be important
to note as tree handling in such degenerated case can lead to O(n^2)
treatments while balanced trees may behave in O(n log n)


it _may_ be a reason for the preprocessing (i.e. placing wisely the implicit
operators by pre-balancing their insertions). at least it was the case for
one of the RE engine I did.


(did you have a look at boost::regexp?)


Armel



Post a followup to this message

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