recursive decent parser
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 8 of 8

Thread: recursive decent parser

  1. #1
    Join Date
    Sep 2006
    Location
    Wantagh,NY
    Posts
    151

    recursive decent parser

    Anyone happen to have a RDP program that handles the following grammar?

    Code:
    <elist>  ->  <elist>,<e>|<e>      
    <e>      ->   <n>^<e>|<n>
    <n>     ->    <n><d>|<d>
    <d>    ->    0|1|2|3|4|5|6|7|8|9

  2. #2
    Join Date
    Sep 2006
    Location
    Wantagh,NY
    Posts
    151

    Re: recursive decent parser

    I wrote some pseudocode which I think will do the trick. I just need some help converting this into Java. I must use Java for this project. If it were me I would have done this in Perl or PHP, something I am more familar with, but I can't. Here is the pseudcode.

    Code:
    procedure RDPARSER;
       while NOT EOF do
       SUCCEEDED = TRUE;
       GET_INP_LINE; //reads in the next input line
      GET_NEXT_SYMBOL; //returns the next input symbol
      ELIST;
     if SUCCEEDED
    then SUCCESS_MESSAGE;
    else FAILURE_MESSAGE enif
    endwhile
    end RDPARSER
    Code:
    procedure ELIST;
    E;
    if SUCCEEDED
     then ELIST_TAIL endif
    end ELIST;
    Code:
    procedure ELIST_TAIL;
    if EOL
    then print E_Value
    else if next_inp_symbol = ","
    then print E_Value;
    GET_NEXT_SYMBOL;
    ELIST;
    else SUCCEEDED = FALSE endif
    endif
    end ELIST_TAIL;
    Code:
    procedure E;
    N_value = 0;
    N;
    if SUCCEEDED
    then ETAIL endif
    end E;
    Code:
    procedure ETAIL
    if(NOT((next_inp_symbol = ",") OR EOL))
    then if next_inp_symbol = '^'
    then GET_NEXT_SYMBOL;
    E;
    E_value = N_value ** E_value;
    else SUCCEEDED = FALSE endif
    else E_value = N_value enidf
    end ETAIL;
    Code:
    procedure N;
    D;
    if SUCCEEDED
    then N_value = N_value * 10 + D_value;
    NTAIL endif
    end N;
    Code:
    procedure NTAIL;
    if(NOT((next_inp_symbol = '^' | ',') OR EOL))
    then N endif
    end NTAIL;
    Code:
    procedure D;
    if next_inp_symbol is a digit
    then compute D_value;
    GET_NEXT_SYMBOL
    else SUCCEEDED = FALSE endif
    end D;
    any help converting this pseudocode I wrote into Java would be greatly appriciated.

  3. #3
    Join Date
    Mar 2006
    Posts
    149

    Re: recursive decent parser

    I didn't look at your pseudocode, but some grammars with left-recursion can be modified so they are suitable for recursive descent parsing. The grammar productions you show are among them.

    Is this for a compiler class? Your text should have a section on "eliminating left recursion".
    Your two problem productions are <elist> and <n>. To eliminate left recursion, you want to transform a grammar production of the form

    Code:
    <lrecursor>    ->   <lrecursor><Alt1> | <Alt2>
    into the two alternatives

    Code:
    <lrecursor>    ->   <Alt2><rrecursor>
    <rrecursor>   ->   <Alt1><rrecursor> | NULL
    to eliminate the roadblock.

    Hope this helps.

  4. #4
    Join Date
    Sep 2006
    Location
    Wantagh,NY
    Posts
    151

    Re: recursive decent parser

    I know but our prof wants us to implement the RDP just as I have it in the pseudocode. The class is called Theoretical Concepts of Programming Languages. We are studying lexical and syntactical analysis.

  5. #5
    Join Date
    Sep 2006
    Location
    Wantagh,NY
    Posts
    151

    Re: recursive decent parser

    Well maybe I should also mention that our prof wants us to have the user of the program be able to enter a string such as 2^2^3,15,2^2. Notice the comma seperated list. This string is what gets handled by the regular langauge I showed. So this would translate to
    2^2^3(+|-|*)15(+|-|*)2^2

  6. #6
    Join Date
    Mar 2006
    Posts
    149

    Re: recursive decent parser

    I see (I think). I did not previously look at your pseudocode but you have already used the suggested mechanism or something similar to eliminate the left recursion.

    About the only thing I can offer then would be to use the return values from your procedures to construct the numerical values rather than having global values. More importantly, you'll probably get a cleaner implementation if you use Java's exception mechanism to handle syntax/parse errors, because then you won't have to obscure intermediate procedures with error handling.

    Be sure your code follows the grammar as closely as possible: I'm mildly suspicious of the pseudocode for <etail>. I would expect to <etail> to be
    Code:
    <etail>   ->   ^<e><etail> | NULL
    but the pseudocode has a test for a comma and end-of-line in addition to the ^.
    Also the eol seems to be a non-whitespace character in the language, but it does not appear in the grammar.

    Sorry not to be more helpful... I haven't done anything significant with Java in many years.

  7. #7
    Join Date
    Mar 2010
    Posts
    16

  8. #8
    Join Date
    Mar 2010
    Posts
    16

    Re: recursive decent parser

    Now also on the Ranch as a thread hijack:
    [http://www.coderanch.com/t/487691/Ja...escent-Parser]

    db

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)