Recursive Descent

[audinue]

I have a little example of syntax rule here (using regex syntax):

number = [1-9]([0-9]+) | [0-9]([1-9]+).([0-9])+ | 0x([a-f0-9])+

Could somebody give me an example how to implement syntax rule above using recursive descent algorithm?

A nice and simple one will be very grateful of course :)

Thanks in advance.

[Duthomhas]

The Wikipedia has a pretty good example...
http://en.wikipedia.org/wiki/Recursive_descent

It takes a minute to figure it out but it is relatively straight-forward.

You'll have to write the getsym() function to gather symbols from the input stream.


If this is homework, it is poorly-designed. The above would better fall under the category of lexing, whereas recursive descent is parsing, or analysis of lexed tokens.

Alas, I know this doesn't help too much. Can you be more specific in terms of what you are doing?

[z05DSL3A]

The following post may help:
http://www.cplusplus.com/forum/general/1116/page2.html
(the post that starts "Here is some code put together from Stroustrups book")

[audinue]

Wow guys! Thats very helpful!

Why they use scanner/lexer?
Is it makes easier to recognize the syntax?

I think it slow things down because to parse the source we need to do several processes...

Btw, this is not a homework :)
I just want to learn how recursive descent works.

[audinue]

Btw, any example how to convert this traditional parsing into recursive descent one?

Based on this rule:

   number = [1-9][0-9]+ | [0-9]+.[0-9]+ | 0x[a-f0-9]+

char c = getchar();

if(c >= '1' && c <= '9')
{
    putchar(c);
    c = getchar();

    while(c >= '0' && c <= '9')
    {
        putchar(c);
        c = getchar();

        if(c == '.')
        {
            putchar(c);
            c = getchar();
            
            if(c < '0' || c > '9')
            {
                puts("\nExpected 'number'.");
                goto end;
            }

            while(c >= '0' && c <= '9')
            {
                putchar(c);
                c = getchar();
            }
        }
    }
}
else if(c == '0')
{
    putchar(c);
    c = getchar();

    switch(c)
    {
        case '.':
        {
            putchar(c);
            c = getchar();

            if(c < '0' || c > '9')
            {
                puts("\nExpected 'number'.");
                goto end;
            }

            while(c >= '0' && c <= '9')
            {
                putchar(c);
                c = getchar();
            }

            break;
        }
        case 'x':
        {
            putchar(c);
            c = getchar();

            if(c < '0' || c > '9' && c < 'a' || c > 'f')
            {
                puts("\nExpected 'hexadecimal number'.");
                goto end;
            }

            while(c >= '0' && c <= '9' || c >= 'a' && c <= 'f')
            {
                putchar(c);
                c = getchar();
            }

            break;
        }
        default:
        {
            puts("\nExpected 'floating or hexadecimal number'.");
            goto end;
        }
    }
}

end:
system("pause");

[Duthomhas]

It doesn't affect speed significantly. But it makes the whole process much easier to control.

To fix the routine, the getsym() compares to getchar() (since each 'symbol' in a number is a single character) and use functions like in the Wikipedia article to work your way through the number to either validate it or reject it.

Good luck!

[audinue]

A little example please... I still don't understand Wikipedia's example *sob*,... please.