Parsing

It depends entirely on what you're doing.

If you're writing a compiler, it's typical to use a tree structure. Usually you'd generate an Abstract Syntax Tree (AST) which is defined by a simple (usually ambiguous) grammar.

For instance, for arithmetic expressions, a typical parsing grammer is:

E ::= E "*" F
    | E "/" F
    | F

F ::= F "+" T
    | F "-" T
    | T
   
T ::= constant
    | variable
    | "(" E ")"
   

That grammar properly captures order of operations and associativity for arithmetic. (I think, anyway.. I may have accidently got the associativity backwards). !!!ACK, THIS IS WRONG!!! For a correct grammar, see my post below.

However, it's far more complicated a grammar than you actually need to represent the expression in the tree. For one, it uses three non-terminals. For another, there's no need for parenthesis in a tree form. So you'd typically have the parser generate an AST. For something like this, the abstract syntax would be something like:

E ::= variable
    | constant
    | E "+" E
    | E "-" E
    | E "*" E
    | E "/" E
   

You'll notice that this grammar is highly ambiguous. However, if you already know the proper parse tree, it's sufficient, and much simpler to work with.

That's the kind of thing you'd do if you're making some kind of parser for code. If you're parsing a data file, it's typical to just have the parser return a data structure, or fill an external data structure, and never build a tree repesenting the structure of what was parsed.

If you're just interpreting a simple expression-based system, like a simple calculator, it's common to just do the calculations on-the-fly in the parser, and just have it return the result.

That's probably most of the options available.. But it's always possible to find some new approach, too.

(Edit: Noticed horrible mistake in the parsing grammar, and corrected in a post below)

[edited by - cwraith on September 6, 2003 1:47:10 AM]

Thanks for your comment.
I am writing a compiler, and from what I can tell, if I have your first grammar:

E ::= E "*" F    
    | E "/" F    
    | F
F ::= F "+" T    
    | F "-" T    
    | T   
T ::= constant    
    | variable    
    | "(" E ")"
 

Then the parse tree for "2 - x * 3" would be very similar to this:

E-> 
   F->
      F->
         T->
            2
         -
         T->
            E->
               F->
                  T->
                     x
               *
               F->
                  T->
                     3
 

Am I lost? Or is this correct? I guess I can try to figure out how to use this..


Later,
Lord Hen

Err.. i screwed that up badly. While I got associativity correct, I got order of ops wrong. Bad, bad, bad... I should know better.

The correct grammar would be:

E ::= E "+" F
    | E "-" F
    | F

F ::= F "*" T
    | F "/" T
    | T
   
T ::= constant
    | variable
    | "(" E ")"
 

So, then... Let''s see if I can build a parse tree for that in ASCII art.

2 - x * 3 parses as:

     E
  /  |  \
E    -    F
|        /|\
F       F * T
|       |   |
T       T   3
|       |
2       x
 

You''ll notice that the parse tree is somewhat complicated. It contains a bunch of steps, which, while they cause it to parse correctly, just muck up the structure of the tree. Hence, compilers use ASTs like I described before. So, a parser would generate and return a tree looking more like this:

    E
  / | \
2   -   E
       /|\
      x * 3
 

That is clearly a much simpler tree, and much easier for an intermediate code generator to traverse.

quote:

---

Original post by Anonymous Poster
Also, Hen, somehow you had the wrong grammar but came up with the correct parse tree.

---

Ahahahaha...thats funny


Ok, I just read this post and someone mentioned that a parser should use a stack to generate the AST...

I believe this can be done easily with my current code, as I have a function for each non-terminal in my grammar. Im not sure when(or, for that matter, WHAT) to push something on to the stack, and when to pop off the stack, in order to get a stack that can generate the AST. Can someone help describe this to me? Or, if someone can describe a better way to do this, thats great too.


Later,
Lord Hen