Re: Is This Expression Parsing Feasible?

Martin Ward <martin@gkc.org.uk>
Thu, 28 Jun 2007 09:37:53 +0100

          From comp.compilers

Related articles
Is This Expression Parsing Feasible? Milburn.Young@gmail.com (2007-06-27)
Re: Is This Expression Parsing Feasible? martin@gkc.org.uk (Martin Ward) (2007-06-28)
Re: Is This Expression Parsing Feasible? torbenm@app-3.diku.dk (2007-06-28)
Re: Is This Expression Parsing Feasible? milburn.young@gmail.com (Milburn Young) (2007-06-28)
Re: Is This Expression Parsing Feasible? jeffrey.kenton@comcast.net (Jeff Kenton) (2007-06-29)
Re: Is This Expression Parsing Feasible? jeffrey.kenton@comcast.net (Jeff Kenton) (2007-06-30)
| List of all articles for this month |

From: Martin Ward <martin@gkc.org.uk>
Newsgroups: comp.compilers
Date: Thu, 28 Jun 2007 09:37:53 +0100
Organization: Compilers Central
References: 07-06-066
Keywords: parse
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.


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/



Post a followup to this message

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