Programming Forums > Application Development > Java

Jhaqen · Jan 13th, 2006, 7:31 PM

Hello, I was wondering if someone could help me with this question:

Write recursive decent parsers for the following grammars:

E = �i� [�(� L �)�] | �(� L�)�
L = E {�,� E}

---------------------------------

E = �i� E� | �(� L�)�
E� = ε | �(� L �)�
L = E L�
L� = ε | �,� L

where Capital letters are non-terminals.

Thanks.

Arevos · Jan 14th, 2006, 4:18 AM

Recursive descent parsers mirror the EBNFs they parse. So in pseudocode, your first example might look something like:

(Toggle Plain Text)

function parse_E(input)
    if input = "i"
        # handle case "i"
    else if input = "i" + "(" + parse_L(substring of input) + ")"
        # handle second case
    else if input = "(" + parse_L(substring of input) + ")"
        # handle third case
    else
        raise invalid_syntax error

function parse_L(input)
    if input = parse_E(substring of input) + ",":
        # handle first valid input case
    else if input = parse_E(substring of input) + parse_E(substring of input):
        # handle second valid input
    else
        raise invalid_syntax error

See, it's just a matter of mapping your ENBF into code. Of course, the pseudocode above leaves out all of the details, but hopefully it'll give you the general idea of what you are supposed to do.

Jhaqen · Jan 14th, 2006, 6:22 AM

Thanks, that's a great help!

Jan 13th, 2006, 7:31 PM	#1
Jhaqen Newbie Join Date: Nov 2005 Posts: 4 Rep Power: 0	Recursive Decent Parser Hello, I was wondering if someone could help me with this question: Write recursive decent parsers for the following grammars: E = �i� [�(� L �)�] \| �(� L�)� L = E {�,� E} --------------------------------- E = �i� E� \| �(� L�)� E� = ε \| �(� L �)� L = E L� L� = ε \| �,� L where Capital letters are non-terminals. Thanks.

Jan 14th, 2006, 4:18 AM	#2
Arevos Programming Guru Join Date: Aug 2005 Location: England Posts: 1,499 Rep Power: 5	Recursive descent parsers mirror the EBNFs they parse. So in pseudocode, your first example might look something like: (Toggle Plain Text) function parse_E(input) if input = "i" # handle case "i" else if input = "i" + "(" + parse_L(substring of input) + ")" # handle second case else if input = "(" + parse_L(substring of input) + ")" # handle third case else raise invalid_syntax error function parse_L(input) if input = parse_E(substring of input) + ",": # handle first valid input case else if input = parse_E(substring of input) + parse_E(substring of input): # handle second valid input else raise invalid_syntax error function parse_E(input) if input = "i" # handle case "i" else if input = "i" + "(" + parse_L(substring of input) + ")" # handle second case else if input = "(" + parse_L(substring of input) + ")" # handle third case else raise invalid_syntax error function parse_L(input) if input = parse_E(substring of input) + ",": # handle first valid input case else if input = parse_E(substring of input) + parse_E(substring of input): # handle second valid input else raise invalid_syntax error See, it's just a matter of mapping your ENBF into code. Of course, the pseudocode above leaves out all of the details, but hopefully it'll give you the general idea of what you are supposed to do.

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Jan 14th, 2006, 6:22 AM	#3
Jhaqen Newbie Join Date: Nov 2005 Posts: 4 Rep Power: 0	Thanks, that's a great help!

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > Java

Recursive Decent Parser