java parser

[mickey]

Hello,
I must write a descendant recursive parser in Java. Do you know some good resources, please?

Thanks,

[bood]

The descendant recursive parser IMO is the most intuitive and easy one, compared to other parsers like LL or LR, as long as you have a correct grammar :-)

I think you can find it in almost all the text book teaching compiler principle.

You can also use something like bison/yacc to implement the parser too.

[mickey]

I need a LL1 grammar and that generators create a complex parser for my aims. I need a basic parser...

[bood]

Well, here's a compiler I wrote years ago, hope it would be useful:
http://www.supnate.com/qianhaib/cminus_0.4.zip

[mickey]

thanks, but it's much complex for me. I'd like something like the parser in c++ stroustrup book. Very simple but it isn't in java and not complete...

[bood]

then how would you like us to help you?
maybe you can post the grammer here

[mickey]

then how would you like us to help you?
maybe you can post the grammer here

hoping it's LL1: the parser must accept things like this below

<send>
  <target>
       <string name="find"> Primer <string>
  </target>
</send>

<send>
  <target>
       <string name="find"> Primer <string>
  </target>
</send>

To copy to clipboard, switch view to plain text mode 

The grammar should be something like this (I write it in Coco/r manner; how can I write it with "Dragon book" sintax?):

Xpml = Send 
Send = "<send>" Target  { Target } "<send>"
Target = "<target>" (String | Number) { String | Number } "</target>"
String = <string>" "name" "=" "\"" Char "\"" ">" Char "</string>"
Number =  "<integer>" "name" "=" "\"" Char "\"" ">" Char "</integer>"
Char = char - '"'

Xpml = Send 
Send = "<send>" Target  { Target } "<send>"
Target = "<target>" (String | Number) { String | Number } "</target>"
String = <string>" "name" "=" "\"" Char "\"" ">" Char "</string>"
Number =  "<integer>" "name" "=" "\"" Char "\"" ">" Char "</integer>"
Char = char - '"'

To copy to clipboard, switch view to plain text mode 

[bood]

Yes, I believe it could be converted to a LL1 grammer
however, LL1 does not allow any two sentences have the same beginning, so a trick is made here (actually should be done in your lexer) to treat "<send>" "<target>" "<string" "<integet" as a whole (they all begin with "<").

Xpml = Send
Send = Send_Start Target { Target } Send_End
Target = Target_Start (String | Number) { String | Number } Target_End
String = String_Start name="string" > string String_End
Number = Integer_Start name="string" > number Integer_End
Char = char - '"'

Then the parser is easy to implement, take Target for example:

parseTarget()
{
  expectToken(Target_Start);
  token=getToken();
  while(token!=Target_End) {
    if(token==String_Start) parseString();
    else if(token==Number) parseNumber();
    else error();
  }
  expectToken(Target_End);
}

parseTarget()
{
  expectToken(Target_Start);
  token=getToken();
  while(token!=Target_End) {
    if(token==String_Start) parseString();
    else if(token==Number) parseNumber();
    else error();
  }
  expectToken(Target_End);
}

To copy to clipboard, switch view to plain text mode 

[mickey]

Yes, I forget the '<' at begin; but isn't this fine too?

Xpml = Send 
Send = "<send>" 
    "<target>" 
         ("<string>" "name" "=" '"' Char '"' ">" CharText "</string>"
          | "<integer>" "name" "=" '"' Char "\"" ">" CharText "</integer>")
    "</target>"
    { "<target>" 
         ("<string>" "name" "=" '"' Char "\"" ">" CharText "</string>"
          | "<integer>" "name" "=" '"' Char '"' ">" CharText "</integer>")
    "</target>" }
"</send>"
Char = char - '"'
CharText = char - '<' //maybe it's necessay tihs too

Xpml = Send 
Send = "<send>" 
    "<target>" 
         ("<string>" "name" "=" '"' Char '"' ">" CharText "</string>"
          | "<integer>" "name" "=" '"' Char "\"" ">" CharText "</integer>")
    "</target>"
    { "<target>" 
         ("<string>" "name" "=" '"' Char "\"" ">" CharText "</string>"
          | "<integer>" "name" "=" '"' Char '"' ">" CharText "</integer>")
    "</target>" }
"</send>"
Char = char - '"'
CharText = char - '<' //maybe it's necessay tihs too

To copy to clipboard, switch view to plain text mode 

It's very ugly but it should be ok...
* for the parser: I wonder how can implement a sysmbol table in a very simple way? What do you suggest, please?

[bood]

Yes, I forget the '<' at begin; but isn't this fine too?

Well, basically no difference to the parser, only concern is the lexer

for the parser: I wonder how can implement a sysmbol table in a very simple way? What do you suggest, please?

You can just use the std::map as the symbol table. But why, I don't see anywhere can reference a string or number in your grammar.

[mickey]

isn't Char and CharText two strings??

[bood]

isn't Char and CharText two strings??

lexer will treat them as the same token though, I don't think lexer can tell the difference.
btw, why don't you just make them as tokens that only can be made of alphabet, numbers and underlines? just as ids in C language.

[mickey]

hoping it's LL1: the parser must accept things like this below

<send>
  <target>
       <string name="find"> Primer </string>
  </target>
</send>

<send>
  <target>
       <string name="find"> Primer </string>
  </target>
</send>

To copy to clipboard, switch view to plain text mode 

Hello,
here I did something like this:

Token nextToken() {
   while ( done ) {
     char = (char) _data[_pos++]; // I read the entire file into a block of memory
     switch (state) {
		case 0 : if (ch == '<')  state = 1; break;					
		case 1 : if (ch == 's') state = 2; break;	
		case 2 : if (ch == 'e') state = 3; 	break;						
		case 3 : if (ch == 'n') state = 4; break;	
		case 4 : if (ch == 'd') state = 5; break;
		case 5 : if (ch == '>') state = 6; return OpenSend;	
		case 6: .......// all other
                case n: if (ch == '<')  state = n+1; break;	
                case n+1 : if (ch == '/') state = n+2; break;
                //and so on to recognize "send" and ">"
        }
    }
}

Token nextToken() {
   while ( done ) {
     char = (char) _data[_pos++]; // I read the entire file into a block of memory
     switch (state) {
		case 0 : if (ch == '<')  state = 1; break;					
		case 1 : if (ch == 's') state = 2; break;	
		case 2 : if (ch == 'e') state = 3; 	break;						
		case 3 : if (ch == 'n') state = 4; break;	
		case 4 : if (ch == 'd') state = 5; break;
		case 5 : if (ch == '>') state = 6; return OpenSend;	
		case 6: .......// all other
                case n: if (ch == '<')  state = n+1; break;	
                case n+1 : if (ch == '/') state = n+2; break;
                //and so on to recognize "send" and ">"
        }
    }
}

To copy to clipboard, switch view to plain text mode 

I wonder: Must I to reconize in the scanner two time the string "send". Is there any tricks to avoid this? ( I mean, I'd like to avoid to write states that recognizes the same "string". I have the same problem with <string></string> and <target></target>).
Hope it's clear...
thanks,

[mickey]

sorry, Could anybody get me any suggestions, please?