How do I implement parsing?

Question

I am designing a compiler in C. I want to know which technique I should use, top-down or bottom up? I have only implemented operator precedence using bottom up. I have applied the following rules:

E:=E+E
E:=E-E
E:=E/E
E:=E*E
E:=E^E

I want to know that am I going the right away? If I want to include if-else, loops, arrays, functions, do I need to implement parsing? If yes, how do I implement it? Any one can I have only implemented token collection and operator precedence. What is the next steps?

"i want to know which technique should i use,top-down or bottom up" This depends on your grammar. What language are you implementing a compiler for? Are you writing the parser from scratch, or using a parser-generator (in which case, that will determine the approach)? — The Archetypal Paul, Nov 08 '10 at 18:04
maybe not the best question ever, but i like what i learned from reading the answers — Andrey, Nov 08 '10 at 18:08
The master question for general compiler technique is [Learning to write a compiler](http://stackoverflow.com/q/1669/2509). There you will find many introductory resources. You might look at the Crenshaw tutorial. — dmckee --- ex-moderator kitten, Nov 08 '10 at 18:09
Crenshaw tutorial link in the topvoted answer gives broken link for me :( due to a stray ]. Try this http://compilers.iecc.com/crenshaw/ — The Archetypal Paul, Nov 08 '10 at 18:24

Jack · Answer 1 · 2010-11-08T18:26:59.087

Lex & Yacc is your answer. Or Flex and Bison which are branched version of original tools.

They are free, they are the real standard for writing lexers and parsers in C and used all around everywhere.

In addition O'Reilly has released a small pearl of 300 pages: Flex & Bison. I bought it and it really explains you how to write a good parser for a programming language and handle all the subtle things (error recovery, conflicts, scopes and so on). It will answer also your questions about how you are parsing expressions: your approach is right with a top-down parser but you'll discover that is not enough to handle operator precedences.

Of course, for hobby, you could write your own lexer and parser but it would be just an academic effort that is nice to understand how FSM and parser work but with no so much fun :)

If you are, instead, interested in programming language design or complex implementations I suggest this book: Programming Language Pragmatics that is not so famous because of the Dragon Book but it really explains why and how various characteristics can and should be implemented in a compiler. The Dragon Book is a bible too, and it will cover at a real low level how to write a parser.. but it would be sort of boring, I warn you..

with out using any tools, can you tell me how do i implement it.i had tried to implemented it by yacc.But when i copiler y.tab.c file,i faced a lot of error.what should i do? — sanjoy saha, Nov 08 '10 at 18:19
because Yacc needs a basic knowledge of its syntax before being used correctly. The time you waste now in understanding it will be saved later when you'll write rules fast as lighting.. if you are gonna write a parser by hand prepare yourself to spend a lot of time.. — Jack, Nov 08 '10 at 18:21
@Jack's advice is sound. I'd also recommend a solid understanding LALR(1) parsing before committing finger to keyboard and designing any large grammars, otherwise it's easy to fall into a number of pitfalls (conflicts) that are very hard to resolve without starting again. — Flexo, Nov 08 '10 at 18:26

score 1 · Answer 2 · answered Nov 08 '10 at 18:04

1

The best way to implement a good parser in C is using flex & yacc

answered Nov 08 '10 at 18:04

Maurizio Cucchiara

895
6
11

with out using any tools, can you tell me how do i implement it. – sanjoy saha Nov 08 '10 at 18:16
2

You need to read up on parsers. That's a much bigger topic than can be covered in a SO answer. Follow some of the references already given to you – The Archetypal Paul Nov 08 '10 at 18:18

score 1 · Answer 3 · answered Nov 08 '10 at 18:06

1

Your question is quite vague and hard to answer without a more specific, detailed question. The "Dragon book" is an excellent reference though for someone seeking to implement a compiler from scratch, or as others have pointed out Lex and Yacc.

answered Nov 08 '10 at 18:06

Flexo

87,323
22
191
272

6

The Dragon book, while excellent, is also pretty daunting. I wouldn't recommend it as the first introduction to compilers... – The Archetypal Paul Nov 08 '10 at 18:18

score 0 · Answer 4 · answered Nov 08 '10 at 21:25

If you intend to implement the parser by hand, you will want to do a recursive descent parser. The code directly reflects the grammar, so it's fairly easy to figure out and understand. It places some restrictions on your grammar (you can't have any left-recursive nonterminals), but you can work around those problems.

However, it depends on the complexity of the grammar; hand-hacking a parser for anything much more complicated than basic arithmetic expressions gets very tedious very quickly. If you're trying to implement anything that looks like a real programming language, use a parser generator like yacc or bison.

I want to implement parsing using operator precedence.can u please help me ? I have implemented +,-,*,/.............I want to know how would i implement rest of the portion with out using any grammar because of it is my college project and yacc,bison is not allow here. — sanjoy saha, Nov 12 '10 at 12:50

How do I implement parsing?

4 Answers4