Thu, 28 Jun 2007 09:37:53 +0100

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) |

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 |

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.