Re: Is This Expression Parsing Feasible?

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.


For example:


((...(((a0 + a1) + a2) + a3) ...) + an)




--
Martin


martin@gkc.org.uk 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 comp.compilers page.
Search the comp.compilers archives again.