[C]Parsing

Halifax · Post by **Halifax** » Tue 07 Aug, 2007 11:41 am

Alright I have been looking into parsing and things I have found a lot of information. Mostly it appears that bottom-up parsing is harder than top-down parsing, but top-down is easier.

I was wondering what some of you people who have parsed languages before used/think what's best?

One thing I don't get about bottom-up parsing is doing it with tables. If someone could explain this to me then that would help a lot.

Post by **Dwedit** » Tue 07 Aug, 2007 1:01 pm

Find someone else's working parser then hack the crap out of it until you figure out how it works.

Halifax · Post by **Halifax** » Tue 07 Aug, 2007 2:59 pm

That was exactly what I wasn't look forward to.

Post by **tr1p1ea** » Tue 07 Aug, 2007 4:36 pm

Well, it really depends on what you are parsing. Are you writing a straight-up assembler or a compiler-of-sorts or something else?

Halifax · Post by **Halifax** » Wed 08 Aug, 2007 7:01 am

Compiler of sorts

which I would not like to annouce at this moment, but you know what it is. I have heard and confirmed that GCC uses a top-down parser is the latest 4.x versions. So it seems like top-down is good enough for a semi-complicated language such as C.

Post by **Dwedit** » Wed 08 Aug, 2007 9:16 am

The tools you need to create parsers or compilers are Flex and Bison. But I've even taken a class about parsers, and still have no clue how to use them. I think that's where "Look at someone else's Flex and Bison code" comes into play.

Timendus · Post by **Timendus** » Wed 08 Aug, 2007 1:52 pm

Usually you have a scanner that breaks the input up in tokens (which is what flex is used for) which are then passed on to the parser (which you can make with bison). The scanner will look for syntactic correctness and stuff, the parser will usually build an internal model of whatever you're parsing. When the model's complete, you can output it in another form (something you can pass on to an assembler, possibly

), give statistics about it, or whatever you were planning to do.

Halifax · Post by **Halifax** » Wed 08 Aug, 2007 2:39 pm

Alright I have heard of everything you guys have suggested. Flex, Bison, YACC, and all that stuff. Those tools output crap as the syntax becomes harder and more complex which is why GCC devs switched to a hand written parser for C in 4.x and a hand written parser for C++ in 3.x and up.

I don't want to use Lexer or Parser generators. I have got a hold on top-down parsing and wrote my first one yesterday for a dummy language and top-down simplifies parsing a lot, but Bottom-up with a table can put top-down parsing to shame I thinking.

Although I guess I will just try a recursive top-down parser if I can't learn bottom-up :/