7 Replies - 14844 Views - Last Post: 22 March 2010 - 02:03 PM Rate Topic: -----

#1 gammaman  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 20-March 10

recursive descent parser

Posted 20 March 2010 - 11:11 AM

anyone have an RDP program that can accept the following grammar?

<elist>  ->  <elist>,<e>|<e>      
<e>      ->   <n>^<e>|<n>
<n>     ->    <n><d>|<d>
<d>    ->    0|1|2|3|4|5|6|7|8|9



in case you were wondering, this grammar says that something like the following can be taken as an input string.

2^2^3,15,20^2

Is This A Good Question/Topic? 0
  • +

Replies To: recursive descent parser

#2 Guest_mustermeister*


Reputation:

Re: recursive descent parser

Posted 20 March 2010 - 12:55 PM

Funny, I'm just writing a C++ program for compiling a BNF schema to a C++ program for checking syntax and parsing. Just what you need, but it's not quite finished yet.

In my slightly modified BNF syntax your schema becomes:

elist => <e>{,<e>}
e => <n>{^<n>}
n => <d>{<d>}
d => (=0-9)

It's unnecessary to use recursive definitions here. My program can handle that too, however, albeit with a slight limitation for efficiency reasons. Without recursion one can translate the schema to a regular expression like in Perl.
Was This Post Helpful? 0

#3 s243a  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 137
  • Joined: 17-March 10

Re: recursive descent parser

Posted 20 March 2010 - 01:02 PM

I haven't studied parsers so I wouldn't know but the following parser generator seems popular for c programs:

http://en.wikipedia.org/wiki/Yacc
Was This Post Helpful? 0
  • +
  • -

#4 Martyn.Rae  Icon User is offline

  • The programming dinosaur
  • member icon

Reputation: 540
  • View blog
  • Posts: 1,406
  • Joined: 22-August 09

Re: recursive descent parser

Posted 20 March 2010 - 01:34 PM

I always write my own in assembler ... much easier and faster than YACC or BISON.
Was This Post Helpful? 1
  • +
  • -

#5 gammaman  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 20-March 10

Re: recursive descent parser

Posted 20 March 2010 - 01:46 PM

View Postmustermeister, on 20 March 2010 - 11:55 AM, said:

Funny, I'm just writing a C++ program for compiling a BNF schema to a C++ program for checking syntax and parsing. Just what you need, but it's not quite finished yet.

In my slightly modified BNF syntax your schema becomes:

elist => <e>{,<e>}
e => <n>{^<n>}
n => <d>{<d>}
d => (=0-9)

It's unnecessary to use recursive definitions here. My program can handle that too, however, albeit with a slight limitation for efficiency reasons. Without recursion one can translate the schema to a regular expression like in Perl.


Would you mind posting the file when you finish?
Was This Post Helpful? 0
  • +
  • -

#6 mustermeister  Icon User is offline

  • New D.I.C Head

Reputation: -10
  • View blog
  • Posts: 11
  • Joined: 20-March 10

Re: recursive descent parser

Posted 20 March 2010 - 01:55 PM

You want the source code or an exe program? I think I'll post both at my web site www.mustermeister.com

By the way do you want the code for the BNF compiler or the output code for checking/parsing your particular kind of expression?

This post has been edited by mustermeister: 20 March 2010 - 01:59 PM

Was This Post Helpful? 0
  • +
  • -

#7 gammaman  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 20-March 10

Re: recursive descent parser

Posted 20 March 2010 - 05:43 PM

View Postmustermeister, on 20 March 2010 - 12:55 PM, said:

You want the source code or an exe program? I think I'll post both at my web site www.mustermeister.com

By the way do you want the code for the BNF compiler or the output code for checking/parsing your particular kind of expression?



The output code. The user should be able to enter a comma seperated list like 2^2,15,2^5 and the parser should be able to handle it.
Was This Post Helpful? 0
  • +
  • -

#8 mustermeister  Icon User is offline

  • New D.I.C Head

Reputation: -10
  • View blog
  • Posts: 11
  • Joined: 20-March 10

Re: recursive descent parser

Posted 22 March 2010 - 02:03 PM

Here is what I've got so far: A syntax checker for your kind of expression. The code is autogenerated by my BNF compiler. It's a series of macro calls. The macro definitions are below. The code uses my string class which you might like to replace with the standard one. You must include some standard library headers. The program takes input from the standard input channel and prints yes/no if the expression is syntactically correct/wrong. The code is somewhat repetitive which I hope to avoid in the future.

#define ELIST ghfmbjoi
DECLARE(anmkehmf)
DECLARE(cbcclhpb)
DECLARE(oljnlocp)
CHARTABLE(inncfnpg)
TABLEINIT_HEADER(lkdjknbd)
TABLEINIT_RANGE(inncfnpg,48,58)
}
CHARSET(dmpadghd,inncfnpg,oljnlocp)
REPEAT(oljnlocp,dmpadghd,cbcclhpb)
CHARTABLE(cpljkjhm)
TABLEINIT_HEADER(mehkphjf)
TABLEINIT_RANGE(cpljkjhm,48,58)
}
CHARSET(kpdlehij,cpljkjhm,oljnlocp)
CONSTANT(kjhmbeei,^,1,kpdlehij)
REPEAT(cbcclhpb,kjhmbeei,anmkehmf)
DECLARE(npmnbmdg)
CHARTABLE(ibaeddll)
TABLEINIT_HEADER(ddfkkojb)
TABLEINIT_RANGE(ibaeddll,48,58)
}
CHARSET(npconioj,ibaeddll,npmnbmdg)
REPEAT(npmnbmdg,npconioj,cbcclhpb)
CHARTABLE(hcbbibng)
TABLEINIT_HEADER(elaijkop)
TABLEINIT_RANGE(hcbbibng,48,58)
}
CHARSET(apaneknc,hcbbibng,npmnbmdg)
CONSTANT(ghjoplmm,\054,1,apaneknc)
REPEAT(anmkehmf,ghjoplmm,END)
DECLARE(haengnnc)
DECLARE(kkpojdjl)
CHARTABLE(hknmjcmd)
TABLEINIT_HEADER(ljdfpfgk)
TABLEINIT_RANGE(hknmjcmd,48,58)
}
CHARSET(hcmjflld,hknmjcmd,kkpojdjl)
REPEAT(kkpojdjl,hcmjflld,haengnnc)
CHARTABLE(aigpkgeg)
TABLEINIT_HEADER(bndpcomo)
TABLEINIT_RANGE(aigpkgeg,48,58)
}
CHARSET(emjjenem,aigpkgeg,kkpojdjl)
CONSTANT(nacnlbac,^,1,emjjenem)
REPEAT(haengnnc,nacnlbac,anmkehmf)
DECLARE(akmbgnhi)
CHARTABLE(fakphhhk)
TABLEINIT_HEADER(libdilpi)
TABLEINIT_RANGE(fakphhhk,48,58)
}
CHARSET(cbmbbhdf,fakphhhk,akmbgnhi)
REPEAT(akmbgnhi,cbmbbhdf,haengnnc)
CHARTABLE(aljndolj)
TABLEINIT_HEADER(nkkcafep)
TABLEINIT_RANGE(aljndolj,48,58)
}
CHARSET(ghfmbjoi,aljndolj,akmbgnhi)
MAIN(ghfmbjoi,lkdjknbd();mehkphjf();ddfkkojb();elaijkop();ljdfpfgk();bndpcomo();libdilpi();nkkcafep();)/>



Here are the macro defs:

inline bool TRUE(string &x)
{
	return true;
}

inline bool END(string &x)
{
	return x.length == 0;
}

#define DECLARE(fname) \
bool fname(string &x);

#define CONSTANT(fname,c,clen,next) \
bool fname(string &x) \
{ \
	return x.starts_with(#c) && next(x(clen)); \
}

#define REPEAT(fname,what,next) \
bool fname(string &x) \
{ \
	return what(x) || next(x); \
}

#define OPTION(fname,what,next) \
bool fname(string &x) \
{ \
	return what(x) || next(x); \
}

#define PARALLELL(fname, par) \
bool fname(string &x) \
{ \
	return par; \
}

#define CHARTABLE(tname) bool tname[0x100];

#define CHARSET(fname,table,next) \
bool fname(string &x) \
{ \
	return table[x[0]] && next(x(1)); \
}

#define TABLEINIT_HEADER(fname) \
void fname() { int i;

#define TABLEINIT_RANGE(table, from, to) \
for (i = from; i < to; i++) table[i] = true;

#define TABLEINIT_SINGLE(table, ch) table[ch] = true;

#define MAIN(fname,init) \
int main(int argc, char* argv[]) \
{ \
	init \
	char x[0x100]; \
	gets(x); \
	if (fname(string(x))) puts("yes!"); \
	else puts("no!"); \
	return 0; \
}




Some headers to include:

#include <malloc.h>
#include <memory.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1