parsing in C

[junky_fellow]

Can someone suggest some good links for the "beginners"
about how expressions are parsed in C ?

thanx..

 

[Alex Fraser]

Can someone suggest some good links for the "beginners"
about how expressions are parsed in C ?

What sort of thing do you want to know? Operator precedence? Something else?

Alex

 

[lallous]

Can someone suggest some good links for the "beginners"
about how expressions are parsed in C ?

thanx..

Hello,

If you're looking to parse artihmetical expressions just read about "RPN -
Reverse Polish Notation", it is a good method and simple to implement.

HTH,
Elias

 

[Chris Barts]

What sort of thing do you want to know? Operator precedence? Something else?

Or he might want an example of how to write his own parser in C. The
question is just that vague.

In any case, an ANSI C yacc grammar is available online for free:
http://www.lysator.liu.se/c/ANSI-C-grammar-y.html
This grammar should tell you all you need to know about how to parse a C
translation unit. If you don't know yacc or BNF, this website may be of
use:
http://www.garshol.priv.no/download/text/bnf.html

 

[Dan Pop]

Can someone suggest some good links for the "beginners"
about how expressions are parsed in C ?

Anything wrong with K&R2?

Dan

 

[Dan Pop]

If you're looking to parse artihmetical expressions just read about "RPN -
Reverse Polish Notation", it is a good method and simple to implement.

But it's not use by the C language. According to my reading of the
original question, the OP wanted to know how C expressions are parsed,
not how to parse expressions with C code.

Dan

 

[Dan Pop]

Or he might want an example of how to write his own parser in C.

Not exactly the ideal project for a beginner...

The question is just that vague.

In any case, an ANSI C yacc grammar is available online for free:
http://www.lysator.liu.se/c/ANSI-C-grammar-y.html
This grammar should tell you all you need to know about how to parse a C
translation unit. If you don't know yacc or BNF, this website may be of
use:
http://www.garshol.priv.no/download/text/bnf.html

I can hardly imagine a *beginner* interested in an ANSI C yacc grammar
specification...

Dan

 

[Malcolm]

Can someone suggest some good links for the "beginners"
about how expressions are parsed in C ?

Do you want to write an expression parser in C, or write a parser in any
language, not necessarily C, to parse a C expression?

To achieve either objective, normally the thing to do is to write a function
called eval().

double eval(const char *expr, int *err)

This takes an arithmetical expression, like "(1+2) * 3" as input, and gives
the result as output. If the expression is illegal, eg "(1 + 2) * 3 +" then
it sets err to register that an error has occured.

The trick is to parse the contents of the parentheses recursively. The other
trick is to have a character of "lookahead", so you can see what you will be
expected to parse. If, afer having parsed an "expression" introduced with
"(", you don't find a ")" in your lookahead, you know the partentheses don't
match and can flag an error.

I have a function which does this, and can give you if you want to look at
it.

 

[macluvitch]

there is a good variety of links across the web that talk about the
subject.

for exeample the famous master peace of Jack Crenshaw "Let's build a
compiler is good one that every beginner should go through to have a good
basic on expression evaluation (it talk in general about compiler
writing).

well in a nutshell to parse an algebrian expression there is at most two
famous ways to proceed with :

polish notation (know also as Infix notation)
and its variant reverse polish notation (postifix)
recursive descent.

all these methods have the same complexity (O big o)
so anyone among them will do the job efficiently.

I will not give you any link cuz if you try simply with google you will be
sure amazed
or the compiler ng will be a good initial point to start from.


Sincerely macluvitch

 

[Chris Barts]

there is a good variety of links across the web that talk about the
subject.

for exeample the famous master peace of Jack Crenshaw "Let's build a
compiler is good one that every beginner should go through to have a good
basic on expression evaluation (it talk in general about compiler
writing).

I agree that Jack Crenshaw's work is a good way to learn how to build
simple recursive-descent parsers, but it suffers from the fact that he
didn't use any parser-generators like yacc. I can understand that as a
pedagogical technique, but in the real world parser-generators can save
you worlds of hassle.

well in a nutshell to parse an algebrian expression there is at most two
famous ways to proceed with :

polish notation (know also as Infix notation)

Polish notation is prefix notation. A variant is used in Lisp.

Lisp looks like this: (* 7 (- 12 3))

(Strictly speaking, the parentheses aren't needed if you make some changes
to the language. Lisp always has them, however.)

and its variant reverse polish notation (postifix)

Reverse-polish notation is most commonly used with stack-based languages,
like Forth (and, interestingly, PostScript).

Forth looks like this: 7 12 3 - *

recursive descent.

I don't know that you strictly need a recursive-descent parser for postfix
notation, but I'm not an expert.

 

[Coos Haak]

Op Fri, 10 Sep 2004 15:45:16 -0600 schreef Chris Barts:

I agree that Jack Crenshaw's work is a good way to learn how to build
simple recursive-descent parsers, but it suffers from the fact that he
didn't use any parser-generators like yacc. I can understand that as a
pedagogical technique, but in the real world parser-generators can save
you worlds of hassle.


Polish notation is prefix notation. A variant is used in Lisp.

Lisp looks like this: (* 7 (- 12 3))

(Strictly speaking, the parentheses aren't needed if you make some changes
to the language. Lisp always has them, however.)


Reverse-polish notation is most commonly used with stack-based languages,
like Forth (and, interestingly, PostScript).

Forth looks like this: 7 12 3 - *


I don't know that you strictly need a recursive-descent parser for postfix
notation, but I'm not an expert.

<OT>
I am ;-(
Forth does not have c.q. need an expression parser, let alone
a recursive descent one. Al it has to do is read white space
delimited tokens (numbers and operators) and place the results
on the stack.
It's relatively easy to write an infix parser in this language,
but it is not of much help. </OT>You might use C instead.

 

[macluvitch]

really I don't understand why beginners begin directly by learning yacc or
lex without having even a small theorie on how does they work. I can't
denied that they are say a bit easy to understand as to use but beleive me
that without trying before with a hand coded lexical analyzer or parser
you will usually get confused.
In addition a hand coded lexical analayzer it still runs quicker than a
generated one !
so please before trying to learn yacc and lex try first with a hand coded
one.

Sincerely mac

 

[junky_fellow]

there is a good variety of links across the web that talk about the
subject.

for exeample the famous master peace of Jack Crenshaw "Let's build a
compiler is good one that every beginner should go through to have a good
basic on expression evaluation (it talk in general about compiler
writing).

thanx for suggesting the nice link. I would even like to mention the
exact link here "http://compilers.iecc.com/crenshaw/".