[antlr-interest] tree construction that cannot be done with rewrite rule

[Han Chen]

I am just started to explore ANTLR v3. After reading the grammar manual, tree construction tutorial, I have a hard problem (at least for me it is) regarding the tree construction

Given the following input.

proxy-list testList
  id 2 cipher rsa-with-rc4-128-md5 vip 192.168.0.1 12345
  id 2 queue-delay 400
  id 3 cipher rsa-with-rc4-128-md5 vip 192.168.0.2 12345
  id 2 cipher rsa-with-rc4-128-sha vip 192.168.0.3 12345
  id 2 cert testcert
  id 3 cert testcert
  id 2 rsakey testkey
  id 2 cipher rsa-with-3des-ede-cbc-sha vip 192.168.0.4 12345
  id 3 vip address 192.168.0.5
  id 2 vip address 192.168.0.6
  id 3 rsakey testkey

the statement with the same 'id' is not in any specific order. However, I would like to construct a tree that put all of the ID specific information as a subroot node and the proxy-list name as the root node of the tree. For example, the above configuration, I would like the resulting tree look similar to the following

^(testList ^(2  ^( cipher ^(rsa-with-rc4-128-md5 192.168.0.1 12345) ^(rsa-with-rc4-128-sha 192.168.0.3 12345) ^(rsa-with-3des-ede-cbc-sha 192.168.0.4 12345) ) ^(queue-delay 400) ^(cert testcert) ^(rsakey testkey) ^(vip 192.168.0.6) ) ^(3 ^( cipher ^(rsa-with-rc4-128-md5 192.168.0.2 12345) ) ^(cert testcert) ^(vip 192.168.0.5) ^(rsakey testkey) ) )

The order of the child node should be the same as the parse sequence, but group under the same subroot node accordingly.

I have the following test grammar, but using rewrite rule, I don't know how to construct the desired tree forementioned

proxyConfig: 'proxy-list' IDENT proxyConfigSt+;

proxyConfigSt: 'id' NUM proxyConfigOption;

proxyConfigOption: 

   'cipher' CIPHER 'vip' IP NUM |

   'queue-delay' NUM |

   'cert' IDENT |

   'rsakey' IDENT |

   'vip' 'address' IP;

IDENT: (~WS)+;

IP: NUM '.' NUM '.' NUM '.' NUM;

NUM: '0'..'9'+;

fragment

WS: (' ' | '\t' | '\r' | '\n')+;

I could, just using action, create an appropriate data structure to represent the above, and then go through the data structure after the rule is complete to build a tree. But the order within the same ID config is lost, I can add more detail into the data structure and then sort it, but that's a little too cumbersome. At the end, I just want the output look like the following. If I have the desired AST constructed, a simple depth-first walk would result the correct output.

proxy-list testList

  id 2 cipher rsa-with-rc4-128-md5 vip 192.168.0.1 12345

  id 2 queue-delay 400

  id 2 cipher rsa-with-rc4-128-sha vip 192.168.0.3 12345

  id 2 cert testcert

  id 2 rsakey testkey

  id 2 cipher rsa-with-3des-ede-cbc-sha vip 192.168.0.4 12345

  id 2 vip address 192.168.0.6

  id 3 cipher rsa-with-rc4-128-md5 vip 192.168.0.2 12345

  id 3 cert testcert

  id 3 vip address 192.168.0.5

  id 3 rsakey testkey

I could do it easily with perl using array of an array. But then I handcoded the parser to fit my need. I am just getting and feet wet with ANTLR and try to do the samething. Any feedback regarding how should I approach this problem using ANTLR is greatly appreciated.

-Han



      
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20090407/eb70732f/attachment.html