Wed, 27 Jun 2007 11:37:45 -0700

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: | Milburn.Young@gmail.com |

Newsgroups: | comp.compilers |

Date: | Wed, 27 Jun 2007 11:37:45 -0700 |

Organization: | Compilers Central |

Keywords: | parse, question |

Posted-Date: | 27 Jun 2007 16:36:19 EDT |

I'm new to expression parsing (but not programming) and have an

algorithm in mind that I would like critiqued by the community. To

make an expression tree from an expression ending in a terminator

(e.g. ';' or '\0'), the lexer returns a random access collection of

tokens. 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. Given that

'p' is a constant within a grammar (probably less than 20), the

complexity should reduce to O(n). My questions are 1) What is the

type of parsing called (if anything)? 2) Is there any reason this

technique would not be feasible?

Here is an example of parsing, where tokens are enclosed in square

brackets, expression nodes are enclosed in curly braces, and the

operator tokens with the highest precedence are marked with an V...

Pre-scan:

[a] [/] [b] [*] [c] [-] [d]

Scan 1:

V V

[a] [/] [b] [*] [c] [-] [d]

Scan 2:

Root

{*} V

{/} {c} [-] [d]

{a} {b}

Scan 3:

Root

{-}

{*} {d}

{/} {c}

{a} {b}

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.