Recursive Descent

audinue (35)

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.

Last edited on

Duoas (1456)

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?

Grey Wolf (637)

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 (35)

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.

Last edited on

audinue (35)

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]+

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86

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");

Last edited on

Duoas (1456)

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 (35)

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

This topic is archived - New replies not allowed.


		C++ : Forums : Lounge : Recursive Descent Search: