Is This Expression Parsing Feasible?

Milburn.Young@gmail.com
Wed, 27 Jun 2007 11:37:45 -0700

          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: Milburn.Young@gmail.com
Newsgroups: comp.compilers
Date: Wed, 27 Jun 2007 11:37:45 -0700
Organization: Compilers Central
Keywords: parse, question

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.