 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
shinya
Guest
|
 Posted: Wed Nov 16, 2005 9:46 am Post subject: syntax analyzer problem! |
 |
|
Hi there!
I'm getting involved in compiler's theory and all that esoteric stuff,
and I decided to write a simple syntax analyzer for simple expressions
like 3 * (4 + 5) as a start point.
I wrote a bunch of C++ code, but something goes wrong.
Here's the code, a very basic top-down parser with a recursive descent
algorithm:
#include <iostream>
#include <exception>
#include <stdexcept>
#include <string>
#include <cctype>
using namespace std;
void p_expression(const char *&);
void p_factor(const char *& s)
{
while (isspace(*s))
s++;
if (isdigit(*s)) {
while (isdigit(*s)) {
s++;
}
} else if (*s == '-') {
p_factor(s);
} else if (*s == '(') {
while (isspace(*s))
s++;
p_expression(s);
while (isspace(*s))
s++;
if (*s != ')')
throw runtime_error("expected a ')'");
} else
throw runtime_error("unexpected symbol");
}
void p_term(const char *& s)
{
while (isspace(*s))
s++;
p_factor(s);
while (isspace(*s))
s++;
if (*s == '*' || *s == '/') {
p_term(s);
}
}
void p_expression(const char *& s)
{
while (isspace(*s))
s++;
p_term(s);
while (isspace(*s))
s++;
if (*s == '+' || *s == '-') {
p_expression(s);
}
}
int main(int argc, char **argv)
{
string s;
cin >> s;
try {
const char *cstr = s.c_str();
p_expression(cstr);
cout << "ok!" << endl;
} catch (runtime_error ex) {
cout << ex.what() << endl;
}
return 0;
}
Sorry for the indentation, but the mail editor really sucks to write code.
It seems there's a problem with the while(isspace(*s)) { s++; } piece of
code, 'cause althougth che actual char is a white space, the s++;
istruction does not execute. But maybe there are a lot of other problems
I didn't notice! :/
Thanks for reply!
shinya.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Ulrich Eckhardt
Guest
|
| Posted: Wed Nov 16, 2005 12:47 pm Post subject: Re: syntax analyzer problem! |
|
|
shinya wrote:
| Quote: | void p_factor(const char *& s)
{
while (isspace(*s))
s++;
|
Make that
while( *s && isspace(*s))
s++;
I've written similar things, and I found it convenient to use streams
instead. The above would then be
void p_factor( istrea& in)
{
in >> std::ws;
| Quote: | } catch (runtime_error ex) {
|
Bad idea. If someone threw an exception derived from runtime_error, it would
be truncated to the baseclass. If the derived class had an override for
what(), only the base version would be called. Instead, catch by reference:
catch( std::exception const& ex)
Uli
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Wed Nov 16, 2005 12:51 pm Post subject: Re: syntax analyzer problem! |
|
|
On 16 Nov 2005 04:46:41 -0500, shinya <piccionevolante (AT) libero (DOT) it> wrote:
| Quote: | string s;
cin >> s;
It seems there's a problem with the while(isspace(*s)) { s++; } piece of
code, 'cause althougth che actual char is a white space, the s++;
istruction does not execute.
|
The operator>> starts by skipping whitespace, then reading until next
whitespace where it stops. The string will never contain any
whitespace. Did you intend to do getline(cin, s)?
John
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
kanze
Guest
|
| Posted: Wed Nov 16, 2005 5:56 pm Post subject: Re: syntax analyzer problem! |
|
|
shinya wrote:
| Quote: | I'm getting involved in compiler's theory and all that
esoteric stuff, and I decided to write a simple syntax
analyzer for simple expressions like 3 * (4 + 5) as a start
point. I wrote a bunch of C++ code, but something goes wrong.
Here's the code, a very basic top-down parser with a recursive
descent algorithm:
|
[code deleted...]
| Quote: | Sorry for the indentation, but the mail editor really sucks to
write code.
|
Which means that the code isn't just copy/pasted into the
message. Which means that if the problem is just some silly
typo, it probably isn't in the posted code.
| Quote: | It seems there's a problem with the while(isspace(*s)) { s++;
} piece of code, 'cause althougth che actual char is a white
space, the s++; istruction does not execute.
|
The most frequent cause of this, especially when the code is
formatted as in your example, is a stray ';' character
immediately after the while(), e.g.:
while(isspace(*s));
;
The less white space you use, the harder it is to see. But the
result is an endless loop if s points to white space. It didn't
see this problem in your posted code, but unless it was done by
copy/paste, that doesn't mean that it isn't present in your
actual code.
| Quote: | But maybe there are a lot of other problems I didn't notice!
:/
|
Well, there is the undefined behavior due to calling isspace,
isdigit, etc. with a char. These functions take an int in the
range 0...UCHAR_MAX, and any negative values for a char will
cause undefined behavior. Since you're picking up the data from
the outside, and you could end up with anything, you should
carefully cast (isspace(static_cast< unsigned char >( *s ) ))
everytime you call one of these functions. A better solution
would be to use the is() function of the ctype facet, but the
learning curve is a bit higher.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
shinya
Guest
|
| Posted: Thu Nov 17, 2005 12:06 am Post subject: Re: syntax analyzer problem! |
|
|
John Potter wrote:
| Quote: | The operator>> starts by skipping whitespace, then reading until next
whitespace where it stops. The string will never contain any
whitespace. Did you intend to do getline(cin, s)?
|
Thanks! This was the biggest problem! Now (with that and some other bug
fixing) my little program work!
shinya.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Meador Inge
Guest
|
| Posted: Thu Nov 17, 2005 12:16 am Post subject: Re: syntax analyzer problem! |
|
|
shinya wrote:
| Quote: | Sorry for the indentation, but the mail editor really sucks to write code.
It seems there's a problem with the while(isspace(*s)) { s++; } piece of
code, 'cause althougth che actual char is a white space, the s++;
istruction does not execute. But maybe there are a lot of other problems
I didn't notice! :/
|
One thing you may ought to consider is seperating the code that does
the lexical analysis from the recursive descent parser. This is
typically how compiler frontends are structered and would allow you to
remove the:
while (isspace(*s)) s++;
statements sprinkled throughout your parser and consolidate them into
one place: the lexer. Most compiler texts present the structure of
compilers this way. The book 'Compilers: Principles, Techniques and
Tools' (the "Dragon Book") is a good intro. It also contains the C code
for a simple expression evaluator similiar to what you are implementing.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
kanze
Guest
|
| Posted: Thu Nov 17, 2005 11:07 am Post subject: Re: syntax analyzer problem! |
|
|
Ulrich Eckhardt wrote:
| Quote: | shinya wrote:
void p_factor(const char *& s)
{
while (isspace(*s))
s++;
Make that
while( *s && isspace(*s))
s++;
|
Why? isspace( ' ' ) returns 0, which is interpreted in this
context as false.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
