Skip to main content
gamedev.net
🔒 Locked

RegEx - Parse Tree

Started by discman1028 8 replies 2.3k views
Original Post
discman1028
discman1028
Hi, I've been trying to write a Reg Expression to DFA converter. NFA->DFA was simple, for the operators *, |, and concatenation, but I'll be adding more, to try to support as much Perl RE syntax as possible. Parse tree -> NFA seems simple enough, but RegEx -> Parse tree is what I'm studying. I'm new to Recursive Descent, and the set of tools that is out there. Could someone help me in identifying if these would be useful for what I am trying to do? * boost -> spirit * yacc * ...? I have automata and theory of computation background, but haven't done much implementation. Note: I am still RTFM'ing, just wondering if you guys had any input. Thanks
--== discman1028 ==--
discman1028
discman1028
For reference, a friend found that ANTLR was probably the best way to generate c++ code that can create a syntax tree. I have yet to try it.

Of course, regex_parse.cpp from here:

http://www.gamedev.net/reference/programming/features/af6/

Does the same thing, but I needed something extendable.
--== discman1028 ==--
discman1028
discman1028
Ok, ANTLR has a heck of a learning curve.. so I'm still looking for a solution. I just want to go from:

(a|b)*

to a tree:

   *  / |/ \a b
--== discman1028 ==--
Sneftel
Sneftel
So you're talking about parsing RegEx syntax, right? Not parsing a grammar into a parse tree by using a RegEx?

Anyways, boost::spirit, yacc, and ANTLR are all appropriate tools for this. Of the three, I prefer yacc but I have little experience with ANTLR. Another appropriate method would be hand-coding a recursive descent parser (surprisingly easy for a syntax as simple as RegEx's).
discman1028
discman1028
Thanks Sneftel. Yes, I meant parsing RegEx syntax. Could you explain what is "parsing a grammar into a parse tree by using a RegEx"?

Though, it seems like spirit and yacc did so much more than what I needed, so I had (and am still having) trouble extracting the information on just making a tree from RegEx syntax. Not to mention, I don't know what this kind of tree is called... Parse Tree or Syntax Tree?


EDIT: Also, I don't know how simple implementing it by hand would be, since I want to support some extra extended Perl RE functionality.

[Edited by - discman1028 on April 19, 2006 3:33:07 PM]
--== discman1028 ==--
Sneftel
Sneftel
Quote:
Original post by discman1028
Thanks Sneftel. Yes, I meant parsing RegEx syntax. Could you explain what is "parsing a grammar into a parse tree by using a RegEx"?

Nothing useful. I was just making sure you didn't think that a specific RegEx defined a parseable context-free grammar. The fact that you're parsing a syntax which itself has a syntax makes the conversation a little more confusing. [wink]
Quote:
Though, it seems like spirit and yacc did so much more than what I needed, so I had (and am still having) trouble extracting the information on just making a tree from RegEx syntax. Not to mention, I don't know what this kind of tree is called... Parse Tree or Syntax Tree?
Yeah, they're all pretty heavy-duty. Parse trees and Abstract Syntax trees are slightly different; one produces the parse tree from the AST. this and this should elucidate the difference. Here's an example.
Sentence:(2+3)*5AST:         Exp         /|\         / | \        /  |  \       /   *   5    Exp    /|\    / | \   /  |  \  (  Exp  )    /|\    / | \   2  +  3Parse tree:    +   / \   *   5 / \ 2   3

Quote:
EDIT: Also, I don't know how simple implementing it by hand would be, since I want to support some extra extended Perl RE functionality.
Recursive descent parsers only really become complicated when you have a lot of SR or RR conflicts to manually deal with. extended RE should be fine.
discman1028
discman1028
Looks like Abstract Syntax Tree is what I want... so nobody at all has generated a simple tool/Applet to go from a RegEx to a tree? Rest assured, I will do so when I figure it out... :)

I've looked at Bison, yacc, ANTLR, boost::spirit, Caco/R, and man o man life should be simpler. :)
--== discman1028 ==--
Sneftel
Sneftel
Quote:
Original post by discman1028
so nobody at all has generated a simple tool/Applet to go from a RegEx to a tree?

I'm sure plenty of people have, as part of writing regex engines. Since it's such a trivial parsing task, though, and since a regex parser is useless if you don't intend to actually generate a FSA, none of them felt it significant enough to break out into a separate project.

BTW, ASTs are not useful except as a means of generating a parse tree.
discman1028
discman1028
Yeh... ok. Though I've seen more trivial applets. :)

And, I think you're picture above's backwards... the classic AST example on Wikipedia leaves out the parens (thus making it abstract).
--== discman1028 ==--
Sneftel
Sneftel
Heh, I don't believe I did that. Yeah, switch all the "AST" and "parse tree" above. *smack self*

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.