By grammar rules of recursive descent parser how can we validate the source string.

Question

If the following two input strings are inputed :

1)<id> + <id> * <id>
2) <id> * <id> <id>

E ::= T{+T}* 
T ::= V{*V}* 
V ::= <id>

Then by applying the above grammar rules of recursive descent parser how can we validate the above source string. What type of the error will be indicated by recursive descent parser ?

Thanks...

Answer 1

Your grammar rules look like arithmetic infix notation. Pyparsing (a Python parsing add-on module) has a built-in method for building parser expressions for this kind of notation, called operatorPrecedence. Here is how a pyparsing parser would parse your two examples:

from pyparsing import operatorPrecedence, opAssoc, ParseException

expr = operatorPrecedence("<id>",
    [
    ('*', 2, opAssoc.LEFT),
    ('+', 2, opAssoc.LEFT),
    ])

tests = """\
<id> + <id> * <id> 
<id> * <id> <id>""".splitlines()

for t in tests:
    print t
    try:
        print expr.parseString(t, parseAll=True).asList()
    except ParseException,pe:
        print "parsing failed"
    print

Prints:

<id> + <id> * <id> 
[['<id>', '+', ['<id>', '*', '<id>']]]

<id> * <id> <id>
parsing failed

Hope this helps you in your studies.

Answer 2

can anyone help me how to perform the above two examples step-by-step according to the D M Dhamdhere Systems Programming book.. Instead of algorithm in Pascal or Java i want to see how does CSF is predicted and SSM is incremented thenafter...step by step procedure..

Will i get an error msg for the (2) source string only ? Will (1) source string be validated ? on the basis or RD recursive descent parser...