|Is This Expression Parsing Feasible? Milburn.Young@gmail.com (2007-06-27)|
|Re: Is This Expression Parsing Feasible? email@example.com (Martin Ward) (2007-06-28)|
|Re: Is This Expression Parsing Feasible? firstname.lastname@example.org (2007-06-28)|
|Re: Is This Expression Parsing Feasible? email@example.com (Milburn Young) (2007-06-28)|
|Re: Is This Expression Parsing Feasible? firstname.lastname@example.org (Jeff Kenton) (2007-06-29)|
|Re: Is This Expression Parsing Feasible? email@example.com (Jeff Kenton) (2007-06-30)|
|From:||Martin Ward <firstname.lastname@example.org>|
|Date:||Thu, 28 Jun 2007 09:37:53 +0100|
|Posted-Date:||30 Jun 2007 09:48:02 EDT|
On Wednesday 27 Jun 2007 19:37, Milburn.Young@gmail.com wrote:
> The parser would scan through the entire list of tokens (left
> to right) noting the token(s) with the highest precedence and making
> sub-trees out of those tokens (on the subsequent pass) and the tokens
> immediately to the left and right of those tokens. This would be done
> until there are no tokens not a part of the expression tree. I
> believe the complexity of this algorithm would be O(p*n), where 'p' is
> the number of precedences and 'n' is the number of tokens.
What about parentheses in the expression?
I assume that your parser would have to scan sub-expressions
with no parentheses first, replace these by subtrees,
then start again scanning for the highest precidence tokens.
So the complexity would be O(p*n^2) since the depth
of parentheses nesting is proportional to n in the worst case.
((...(((a0 + a1) + a2) + a3) ...) + an)
email@example.com http://www.cse.dmu.ac.uk/~mward/ Erdos number: 4
G.K.Chesterton web site: http://www.cse.dmu.ac.uk/~mward/gkc/
Return to the
Search the comp.compilers archives again.