A simple parser

[jacob navia]

Hi guys

I have written this small parser to print out the functions defined in a
C file. This is an example of parsing in C, that I want to add to my
tutorial. Comments (and bug reports) are welcome.

-------------------------------------------------------------cut here

/* A simple scanner that will take a file of C source code and
print the names of all functions therein, in the following format:
"Function XXXX found line dddd .... ddddd"
Algorithm. It scans for a terminating parentheses and an immediately
following opening brace. Comments can appear between the closing
paren and the opening braces, but no other characters besides white
space. Functions must have the correct prototype, K & R syntax
is not supported.
*/
#include <stdio.h>
#define MAXID 1024 // Longest Identifier we support. Sorry
// Java guys...
static char IdBuffer[MAXID]; // Buffer for remembering the function name
static int line = 1; // We start at line 1

// This function reads a character and if
// it is \n it bumps the line counter
static int Fgetc(FILE *f)
{
int c = fgetc(f);
if (c == '\n')
line++;
return c;
}

// Return 1 if the character is a legal C identifier
// character, zero if not. The parameter "start"
// means if an identifier START character
// (numbers) is desired.
static int IsIdentifier(in t c,int start)
{
if (c >= 'a' && c <= 'z')
return 1;
if (c >= 'A' && c <= 'Z')
return 1;
if (start == 0 && c >= '0' && c <= '9')
return 1;
if (c == '_')
return 1;
return 0;
}

// Just prints the function name
static int PrintFunction(F ILE *f)
{
printf("Functio n %s found line %d ...",IdBuffer,l ine);
return Fgetc(f);
}

// Reads a global identifier into our name buffer
static int ReadId(char c,FILE *f)
{
int i = 1;
IdBuffer[0] = c;
while (i < MAXID-1) {
c = Fgetc(f);
if (c != EOF) {
if (IsIdentifier(c ,0))
IdBuffer[i++] = c;
else break;
}
else break;
}
IdBuffer[i] = 0;
return c;
}
static int ParseString(FIL E *f) // Skips strings
{
int c = Fgetc(f);
while (c != EOF && c != '"') {
if (c == '\\')
c = Fgetc(f);
if (c != EOF)
c = Fgetc(f);
}
if (c == '"')
c = Fgetc(f);
return c;
}

static int ParseComment(FI LE *f) // Skips comments
{
int c = Fgetc(f);
restart:
while (c != '*') {
c = Fgetc(f);
if (c == EOF)
return EOF;
}
c = Fgetc(f);
if (c == '/')
return Fgetc(f);
else goto restart;
}
static int ParseCppComment (FILE *f) // Skips // comments
{
int c = Fgetc(f);
while (c != EOF && c != '\n') {
if (c == '\\')
c = Fgetc(f);
if (c != EOF)
c = Fgetc(f);
}
if (c == '\n')
c = Fgetc(f);
return c;
}

// Skips white space and comments
static int SkipWhiteSpace( int c,FILE *f) {
if (c ' ')
return c;
while (c <= ' ') {
c = Fgetc(f);
if (c == '/') {
c = Fgetc(f);
if (c == '*')
c = ParseComment(f) ;
else if (c == '/')
c = ParseCppComment (f);
}
}
return c;
}

// Skips chars between simple quotes
static int ParseQuotedChar (FILE *f)
{
int c = Fgetc(f);
while (c != EOF && c != '\'') {
if (c == '\\')
c = Fgetc(f);
if (c != EOF)
c = Fgetc(f);
}
if (c == '\'')
c = Fgetc(f);
return c;
}
int main(int argc,char *argv[])
{
if (argc == 1) {
printf("Usage: %s <file.c>\n",arg v[0]);
return 1;
}
FILE *f = fopen(argv[1],"r");
if (f == NULL) {
printf("Can't find %s\n",argv[1]);
return 2;
}
int c = Fgetc(f);
int level = 0;
int parenlevel = 0;
int inFunction = 0;
while (c != EOF) {
// Note that each of the switches must advance the
// character read so that we avoid an infinite loop.
switch (c) {
case '"':
c = ParseString(f);
break;
case '/':
c = Fgetc(f);
if (c == '*')
c = ParseComment(f) ;
else if (c == '/')
c = ParseCppComment (f);
break;
case '\'':
c = ParseQuotedChar (f);
break;
case '{':
level++;
c = Fgetc(f);
break;
case '}':
if (level == 1 && inFunction) {
printf(" %d\n",line);
inFunction = 0;
}
if (level 0)
level--;
c = Fgetc(f);
break;
case '(':
parenlevel++;
c = Fgetc(f);
break;
case ')':
if (parenlevel 0)
parenlevel--;
c = Fgetc(f);
if ((parenlevel|le vel) == 0) {
c = SkipWhiteSpace( c,f);
if (c == '{') {
level++;
inFunction = 1;
c = PrintFunction(f );
}
}
break;
default:
if ((level | parenlevel) == 0 &&
IsIdentifier(c, 1))
c = ReadId(c,f);
else c = Fgetc(f);
}
}
fclose(f);
return 0;
}

[Ancient_Hacker]

jacob navia wrote:

>It scans for a terminating parentheses and an immediately
following opening brace.

Um, can't if() and while() statements have that sequence?
A better strategy might be to count curly brackets. If the nesting
level of curlys is zero, then you're at the top level. Anything that
has parens is probably a function declaration.

Of course there's the problem of macros,which I'm sure you don't want
to handle yourself. Maybe run cpp and pipe its output to your program?

[CBFalconer]

jacob navia wrote:

>
I have written this small parser to print out the functions
defined in a C file. This is an example of parsing in C, that I
want to add to my tutorial. Comments (and bug reports) are welcome.

.... snip ...

>
// Return 1 if the character is a legal C identifier
// character, zero if not. The parameter "start"
// means if an identifier START character
// (numbers) is desired.
static int IsIdentifier(in t c,int start)
{
if (c >= 'a' && c <= 'z')
return 1;
if (c >= 'A' && c <= 'Z')
return 1;
if (start == 0 && c >= '0' && c <= '9')
return 1;
if (c == '_')
return 1;
return 0;
}

Just this one example will do. Obvious problems:

1. Excessive indentation. Later it makes lines much too long.
Use spaces, not tabs, and indent by 3 or 4 places.

2. Use of // comments in Usenet. Causes nasty line wrapping
problems.

3. Faulty code. There is no guarantee 'a' .. 'z' etc. are
contiguous, in any specific order, etc.

4. Doesn't handle EOF.

Here is a sample of some code that may do what you want. It
doesn't allow line continuation within identifiers. You would
probably need to control '{' and '}' matching within skiptoident.

/* skips and echoes all characters that cannot start an
identifier. echoto may be NULL, to suppress any echoing
Returns the starting char for the following identifier,
which may be EOF and is still in the input stream.
*/
static int skiptoident(FIL E *f, FILE *echoto)
{
int ch;

do {
ch = getc(f);
if (('_' == ch) || isalpha(ch)) break;
if (echoto && (EOF != ch)) putc(ch, echoto);
} while (EOF != ch);
ungetc(ch, f);
return ch;
} /* skiptoident */

/* ----------------- */

/* generic function to extract the next identifier from a stream
Identifiers can begin with _ or alpha, and continue until a
non-alpha non _ non-numeric char is encountered.
'\0' terminate the string.
Leading chars that do not fit an identifier are echoed.
echoto may be NULL, to suppress any echoing
Returns char terminating the identifier, which is 'ungotten'
buf[bmax] should be valid storage space.
*/
static int getident(char *buf, int bmax, FILE *f, FILE *echoto)
{
int ch, ix;

if (EOF == skiptoident(f, echoto)) ch = EOF;
else ch = getc(f);
/* Here the input stream has been absorbed and echoed */
/* up to the first character of an identifier, in ch */
ix = 0;
while (('_' == ch) || isalnum(ch)) { /* skips on eof */
buf[ix++] = ch;
ch = getc(f);
if (ix >= bmax) break;
}
buf[ix] = '\0';
ungetc(ch, f);
return ch;
} /* getident */

These are extracts from id2id which has to do some elementary C
lexing, and is available on my site:

<http://cbfalconer.home.att.net/download/

PS: I find you have committed the sin of multi-posting, so I have
cross-posted this response. Luckily I didn't go back on line
before checking the lcc group.

--
"I don't know where bin Laden is. I have no idea and really
don't care. It's not that important." - G.W. Bush, 2002-03-13
"No, we've had no evidence that Saddam Hussein was involved
with September the 11th." - George Walker Bush 2003-09-17

[Richard Heathfield]

jacob navia said:

Hi guys

I have written this small parser to print out the functions defined in a
C file. This is an example of parsing in C, that I want to add to my
tutorial. Comments (and bug reports) are welcome.

foo.c:12: parse error before `/'
foo.c:17: stray '\' in program
foo.c:54: warning: type defaults to `int' in declaration of `IdBuffer'
foo.c:54: warning: ANSI C forbids zero-size array `IdBuffer'
foo.c:54: `c' undeclared here (not in a function)
foo.c:54: ANSI C forbids data definition with no type or storage class
foo.c:55: parse error before `while'
foo.c:64: `i' undeclared here (not in a function)
foo.c:64: warning: type defaults to `int' in declaration of `IdBuffer'
foo.c:64: variable `IdBuffer' has initializer but incomplete type
foo.c:64: conflicting types for `IdBuffer'
foo.c:54: previous declaration of `IdBuffer'
foo.c:64: ANSI C forbids data definition with no type or storage class
foo.c:65: parse error before `return'
foo.c:69: parse error before `/'
foo.c:83: parse error before `/'
foo.c:92: warning: type defaults to `int' in declaration of `c'
foo.c:92: warning: implicit declaration of function `Fgetc'
foo.c:92: `f' undeclared here (not in a function)
foo.c:92: initializer element is not constant
foo.c:92: ANSI C forbids data definition with no type or storage class
foo.c:93: parse error before `if'
foo.c:99: parse error before `/'
foo.c: In function `main':
foo.c:152: parse error before `*'
foo.c:153: `f' undeclared (first use in this function)
foo.c:153: (Each undeclared identifier is reported only once
foo.c:153: for each function it appears in.)
foo.c:157: parse error before `int'
foo.c:162: parse error before `/'
foo.c:168: case label not within a switch statement
foo.c:171: warning: implicit declaration of function `ParseComment'
foo.c:173: warning: implicit declaration of function `ParseCppCommen t'
foo.c:175: case label not within a switch statement
foo.c:176: warning: implicit declaration of function `ParseQuotedCha r'
foo.c:178: case label not within a switch statement
foo.c:179: `level' undeclared (first use in this function)
foo.c:182: case label not within a switch statement
foo.c:183: `inFunction' undeclared (first use in this function)
foo.c:184: `line' undeclared (first use in this function)
foo.c:191: case label not within a switch statement
foo.c:192: `parenlevel' undeclared (first use in this function)
foo.c:195: case label not within a switch statement
foo.c:200: warning: implicit declaration of function `SkipWhiteSpace '
foo.c:204: warning: implicit declaration of function `PrintFunction'
foo.c:208: default label not within a switch statement
foo.c:210: warning: implicit declaration of function `IsIdentifier'
foo.c:211: warning: implicit declaration of function `ReadId'
foo.c: At top level:
foo.c:215: warning: type defaults to `int' in declaration of `fclose'
foo.c:215: warning: parameter names (without types) in function declaration
foo.c:215: ANSI C forbids data definition with no type or storage class
foo.c:216: parse error before `return'
make: *** [foo.o] Error 1

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Keith Thompson]

Richard Heathfield <in*****@invali d.invalidwrites :

jacob navia said:

>Hi guys

I have written this small parser to print out the functions defined in a
C file. This is an example of parsing in C, that I want to add to my
tutorial. Comments (and bug reports) are welcome.

foo.c:12: parse error before `/'
foo.c:17: stray '\' in program

[51 lines deleted]

make: *** [foo.o] Error 1

Every one of those errors is caused by two things: "//" comments and
mixed declarations and statements.

The code compiles without error with "gcc -std=c99". It also compiles
without error with "gcc -ansi -pedantic" if I remove the "//" comments
and move a few object declarations.

It is, as far as I can tell, valid C99.

I understand and agree with your reasons for using a strict C90
compiler, but not everyone does so.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Richard Heathfield]

Keith Thompson said:

Richard Heathfield <in*****@invali d.invalidwrites :

>jacob navia said:

>>Hi guys

I have written this small parser to print out the functions defined in a
C file. This is an example of parsing in C, that I want to add to my
tutorial. Comments (and bug reports) are welcome.

foo.c:12: parse error before `/'
foo.c:17: stray '\' in program

[51 lines deleted]

>make: *** [foo.o] Error 1

Every one of those errors is caused by two things: "//" comments and
mixed declarations and statements.

<shrugI figured it had to be something like that. So - does anyone have a
conforming C99 compiler that we can use to test Mr Navia's code? No? Oh
well.

The code compiles without error with "gcc -std=c99".

Er, so what? Despite the misleading switch-name, gcc is not a C99-conforming
compiler.

It also compiles
without error with "gcc -ansi -pedantic" if I remove the "//" comments
and move a few object declarations.

That, in my view, is the author's job, not yours or mine. (And it shows that
the C99isms have been adopted gratuitously, presumably to make the code
less portable. Why anyone should wish to do this is beyond me.)

It is, as far as I can tell, valid C99.

I understand and agree with your reasons for using a strict C90
compiler, but not everyone does so.

Well, my principal reason for using a strict C90 compiler is simple - it's
so that I can be sure that /my/ code doesn't use any C99isms, because I
want /my/ code to compile everywhere, not just on the vanishingly small
number of conforming C99 implementations .

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[jacob navia]

Ancient_Hacker wrote:

jacob navia wrote:

>>It scans for a terminating parentheses and an immediately
following opening brace.

Um, can't if() and while() statements have that sequence?
A better strategy might be to count curly brackets. If the nesting
level of curlys is zero, then you're at the top level. Anything that
has parens is probably a function declaration.

Well I *do* count parens and brackets.... See the code

>
Of course there's the problem of macros,which I'm sure you don't want
to handle yourself. Maybe run cpp and pipe its output to your program?

Macros will be assumed function calls, but not function definitions...

I should ignore # lines, that would make it more robust.

[jacob navia]

CBFalconer wrote:

jacob navia wrote:

>>I have written this small parser to print out the functions
defined in a C file. This is an example of parsing in C, that I
want to add to my tutorial. Comments (and bug reports) are welcome.

... snip ...

>>// Return 1 if the character is a legal C identifier
// character, zero if not. The parameter "start"
// means if an identifier START character
// (numbers) is desired.
static int IsIdentifier(in t c,int start)
{
if (c >= 'a' && c <= 'z')
return 1;
if (c >= 'A' && c <= 'Z')
return 1;
if (start == 0 && c >= '0' && c <= '9')
return 1;
if (c == '_')
return 1;
return 0;
}

Just this one example will do. Obvious problems:

1. Excessive indentation. Later it makes lines much too long.
Use spaces, not tabs, and indent by 3 or 4 places.

OK

2. Use of // comments in Usenet. Causes nasty line wrapping
problems.

OK

3. Faulty code. There is no guarantee 'a' .. 'z' etc. are
contiguous, in any specific order, etc.

Mmmm, it *could* be, but I have never found a machine where they aren't
contiguous...

4. Doesn't handle EOF.

Why? It returns 0 at EOF, and EOF is NOT an identifier char, so it is
correct...

Here is a sample of some code that may do what you want. It
doesn't allow line continuation within identifiers. You would
probably need to control '{' and '}' matching within skiptoident.

/* skips and echoes all characters that cannot start an
identifier. echoto may be NULL, to suppress any echoing
Returns the starting char for the following identifier,
which may be EOF and is still in the input stream.
*/
static int skiptoident(FIL E *f, FILE *echoto)
{
int ch;

do {
ch = getc(f);
if (('_' == ch) || isalpha(ch)) break;
if (echoto && (EOF != ch)) putc(ch, echoto);
} while (EOF != ch);
ungetc(ch, f);
return ch;
} /* skiptoident */

This is interesting since it would eliminate the need for a
buffer. The problem is that

typedef struct _tagFoo {
int a;
} FOO;

would print the _tagfoo...

I can't decide whether an indentifier is really a function until
I see a ')' followed by {, so I can't put it out immediately.

But I see the point of '_' || isalpha(c)

It is much better. Thanks.

/* ----------------- */

/* generic function to extract the next identifier from a stream
Identifiers can begin with _ or alpha, and continue until a
non-alpha non _ non-numeric char is encountered.
'\0' terminate the string.
Leading chars that do not fit an identifier are echoed.
echoto may be NULL, to suppress any echoing
Returns char terminating the identifier, which is 'ungotten'
buf[bmax] should be valid storage space.
*/
static int getident(char *buf, int bmax, FILE *f, FILE *echoto)
{
int ch, ix;

if (EOF == skiptoident(f, echoto)) ch = EOF;
else ch = getc(f);
/* Here the input stream has been absorbed and echoed */
/* up to the first character of an identifier, in ch */
ix = 0;
while (('_' == ch) || isalnum(ch)) { /* skips on eof */
buf[ix++] = ch;
ch = getc(f);
if (ix >= bmax) break;
}
buf[ix] = '\0';
ungetc(ch, f);
return ch;
} /* getident */

These are extracts from id2id which has to do some elementary C
lexing, and is available on my site:

<http://cbfalconer.home.att.net/download/

PS: I find you have committed the sin of multi-posting, so I have
cross-posted this response. Luckily I didn't go back on line
before checking the lcc group.

[jacob navia]

Keith Thompson wrote:

Richard Heathfield <in*****@invali d.invalidwrites :

>>jacob navia said:

>>>Hi guys

I have written this small parser to print out the functions defined in a
C file. This is an example of parsing in C, that I want to add to my
tutorial. Comments (and bug reports) are welcome.

foo.c:12: parse error before `/'
foo.c:17: stray '\' in program

[51 lines deleted]

>>make: *** [foo.o] Error 1

Every one of those errors is caused by two things: "//" comments and
mixed declarations and statements.

The code compiles without error with "gcc -std=c99". It also compiles
without error with "gcc -ansi -pedantic" if I remove the "//" comments
and move a few object declarations.

It is, as far as I can tell, valid C99.

I understand and agree with your reasons for using a strict C90
compiler, but not everyone does so.

Since you compiled Keith, can you pass it through some
C code... Does it work?

jacob

[Richard Heathfield]

jacob navia said:

CBFalconer wrote:

<snip>

>3. Faulty code. There is no guarantee 'a' .. 'z' etc. are
contiguous, in any specific order, etc.

Mmmm, it *could* be, but I have never found a machine where they aren't
contiguous...

That doesn't mean such machines don't exist. I've spent several years
working on such machines. Look up "EBCDIC" in Google.

<snip>

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)