Pastebin launched a little side project called HostCabi.net, check it out ;-)Don't like ads? PRO users don't see any ads ;-)
Guest

Alex D

By: a guest on Nov 25th, 2010  |  syntax: D  |  size: 36.59 KB  |  hits: 40  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. module ast_parser ;
  2. import std.stdio ;
  3.  
  4. import core.stdc.ctype ; //isspace
  5.  
  6. class TokenList
  7. {
  8.     enum
  9.     {
  10.         ID_VOID = 0,
  11.         ID_STRING = 1,
  12.         ID_LIST = 2,
  13.     } ;
  14.     enum
  15.     {
  16.         LEFT_TO_RIGHT = 1,
  17.         RIGHT_TO_LEFT = 2,
  18.     }
  19.     enum
  20.     {
  21.         INFIX       = 0,
  22.         PREFIX      = 1,
  23.         POSTFIX     = 2,
  24.         PAREN       = 3,
  25.         //SEPARATOR   = 4  //not yet done
  26.     }
  27.  
  28.     struct OperatorProperties
  29.     {
  30.         int type ; //prefix, postfix, infix, paren
  31.         int priority ;
  32.         int direction ; // left-to-right, right-to-left
  33.     } ;
  34.  
  35.     static OperatorProperties [string] ms_operator ;
  36.  
  37.     static this ()
  38.     {
  39.         {
  40.             OperatorProperties w = {INFIX, 0, LEFT_TO_RIGHT} ;
  41.             ms_operator [";"] = w ;
  42.         }
  43.         {
  44.             OperatorProperties w = {PREFIX, 1, LEFT_TO_RIGHT} ;
  45.             ms_operator ["foreach"] = w ;
  46.         }
  47.         {
  48.             OperatorProperties w = {PREFIX, 1, LEFT_TO_RIGHT} ;
  49.             ms_operator ["for"] = w ;
  50.         }
  51.         {
  52.             OperatorProperties w = {PREFIX, 1, LEFT_TO_RIGHT} ;
  53.             ms_operator ["while"] = w ;
  54.         }
  55.         {
  56.             OperatorProperties w = {PREFIX, 1, LEFT_TO_RIGHT} ;
  57.             ms_operator ["do"] = w ;
  58.         }
  59.         {
  60.             OperatorProperties w = {PREFIX, 2, LEFT_TO_RIGHT} ;
  61.             ms_operator ["return"] = w ;
  62.         }        
  63.         {
  64.             OperatorProperties w = {INFIX, 3, LEFT_TO_RIGHT} ;
  65.             ms_operator [","] = w ;
  66.         }
  67.         {
  68.             OperatorProperties w = {INFIX, 4, RIGHT_TO_LEFT} ;
  69.             ms_operator ["="] = w ;
  70.         }
  71.         {
  72.             OperatorProperties w = {INFIX, 4, RIGHT_TO_LEFT} ;
  73.             ms_operator ["+="] = w ;
  74.         }
  75.         {
  76.             OperatorProperties w = {INFIX, 4, RIGHT_TO_LEFT} ;
  77.             ms_operator ["-="] = w ;
  78.         }
  79.         {
  80.             OperatorProperties w = {INFIX, 4, RIGHT_TO_LEFT} ;
  81.             ms_operator ["*="] = w ;
  82.         }
  83.         {
  84.             OperatorProperties w = {INFIX, 4, RIGHT_TO_LEFT} ;
  85.             ms_operator ["/="] = w ;
  86.         }
  87.         {
  88.             OperatorProperties w = {INFIX, 4, RIGHT_TO_LEFT} ;
  89.             ms_operator ["%="] = w ;
  90.         }
  91.         {
  92.             OperatorProperties w = {INFIX, 4, RIGHT_TO_LEFT} ;
  93.             ms_operator ["&="] = w ;
  94.         }
  95.         {
  96.             OperatorProperties w = {INFIX, 4, RIGHT_TO_LEFT} ;
  97.             ms_operator ["|="] = w ;
  98.         }
  99.         {
  100.             OperatorProperties w = {INFIX, 4, RIGHT_TO_LEFT} ;
  101.             ms_operator ["^="] = w ;
  102.         }
  103.         {
  104.             OperatorProperties w = {INFIX, 4, RIGHT_TO_LEFT} ;
  105.             ms_operator ["<<="] = w ;
  106.         }
  107.         {
  108.             OperatorProperties w = {INFIX, 4, RIGHT_TO_LEFT} ;
  109.             ms_operator [">>="] = w ;
  110.         }
  111.         {
  112.             OperatorProperties w = {INFIX, 4, RIGHT_TO_LEFT} ;
  113.             ms_operator [">>>="] = w ;
  114.         }
  115.         {
  116.             OperatorProperties w = {INFIX, 5, RIGHT_TO_LEFT} ;
  117.             ms_operator ["?"] = w ;
  118.         }
  119.         {
  120.             OperatorProperties w = {INFIX, 6, LEFT_TO_RIGHT} ;
  121.             ms_operator [":"] = w ;
  122.         }
  123.         {   //TODO : check
  124.             //OperatorProperties w = {INFIX, 7, RIGHT_TO_LEFT} ;
  125.             //ms_operator ["?:"] = w ;
  126.         }
  127.         {
  128.             OperatorProperties w = {INFIX, 8, LEFT_TO_RIGHT} ;
  129.             ms_operator ["||"] = w ;
  130.         }
  131.                 {
  132.             OperatorProperties w = {INFIX, 9, LEFT_TO_RIGHT} ;
  133.             ms_operator ["&&"] = w ;
  134.         }
  135.         {
  136.             OperatorProperties w = {INFIX, 10, LEFT_TO_RIGHT} ;
  137.             ms_operator ["|"] = w ;
  138.         }
  139.         {
  140.             OperatorProperties w = {INFIX, 11, LEFT_TO_RIGHT} ;
  141.             ms_operator ["^"] = w ;
  142.         }
  143.         {
  144.             OperatorProperties w = {INFIX, 12, LEFT_TO_RIGHT} ;
  145.             ms_operator ["&"] = w ;
  146.         }
  147.         {
  148.             OperatorProperties w = {INFIX, 13, LEFT_TO_RIGHT} ;
  149.             ms_operator ["=="] = w ;
  150.         }
  151.         {
  152.             OperatorProperties w = {INFIX, 13, LEFT_TO_RIGHT} ;
  153.             ms_operator ["!="] = w ;
  154.         }
  155.         {
  156.             OperatorProperties w = {INFIX, 14, LEFT_TO_RIGHT} ;
  157.             ms_operator [">"] = w ;
  158.         }
  159.         {
  160.             OperatorProperties w = {INFIX, 14, LEFT_TO_RIGHT} ;
  161.             ms_operator [">="] = w ;
  162.         }
  163.         {
  164.             OperatorProperties w = {INFIX, 14, LEFT_TO_RIGHT} ;
  165.             ms_operator ["<"] = w ;
  166.         }
  167.         {
  168.             OperatorProperties w = {INFIX, 14, LEFT_TO_RIGHT} ;
  169.             ms_operator ["<="] = w ;
  170.         }
  171.         {
  172.             OperatorProperties w = {INFIX, 15, LEFT_TO_RIGHT} ;
  173.             ms_operator [">>"] = w ;
  174.         }
  175.         {
  176.             OperatorProperties w = {INFIX, 15, LEFT_TO_RIGHT} ;
  177.             ms_operator [">>>"] = w ;
  178.         }
  179.         {
  180.             OperatorProperties w = {INFIX, 15, LEFT_TO_RIGHT} ;
  181.             ms_operator ["<<"] = w ;
  182.         }
  183.         {   //TODO : check priority
  184.             OperatorProperties w = {INFIX, 16, LEFT_TO_RIGHT} ;
  185.             ms_operator ["is"] = w ;
  186.         }
  187.         {   //TODO : check priority
  188.             OperatorProperties w = {INFIX, 16, LEFT_TO_RIGHT} ;
  189.             ms_operator ["!is"] = w ;
  190.         }
  191.         {   //TODO : check priority
  192.             OperatorProperties w = {INFIX, 16, LEFT_TO_RIGHT} ;
  193.             ms_operator ["in"] = w ;
  194.         }
  195.         {   //TODO : check priority
  196.             OperatorProperties w = {INFIX, 16, LEFT_TO_RIGHT} ;
  197.             ms_operator ["!in"] = w ;
  198.         }
  199.         {
  200.             OperatorProperties w = {INFIX, 17, LEFT_TO_RIGHT} ;
  201.             ms_operator ["+"] = w ;
  202.         }
  203.         {
  204.             OperatorProperties w = {INFIX, 17, LEFT_TO_RIGHT} ;
  205.             ms_operator ["-"] = w ;
  206.         }
  207.         {
  208.             OperatorProperties w = {INFIX, 18, LEFT_TO_RIGHT} ;
  209.             ms_operator ["*"] = w ;
  210.         }
  211.         {   //TODO : check priority
  212.             OperatorProperties w = {INFIX, 18, LEFT_TO_RIGHT} ;
  213.             ms_operator ["~"] = w ;
  214.         }        
  215.         {
  216.             OperatorProperties w = {INFIX, 18, LEFT_TO_RIGHT} ;
  217.             ms_operator ["/"] = w ;
  218.         }
  219.         {
  220.             OperatorProperties w = {INFIX, 18, LEFT_TO_RIGHT} ;
  221.             ms_operator ["%"] = w ;
  222.         }
  223.         {
  224.             OperatorProperties w = {INFIX, 19, LEFT_TO_RIGHT} ;
  225.             ms_operator ["%list"] = w ;
  226.         }
  227.         {
  228.             OperatorProperties w = {PREFIX, 20, RIGHT_TO_LEFT} ;
  229.             ms_operator ["%o1+"] = w ;
  230.         }
  231.         {
  232.             OperatorProperties w = {PREFIX, 20, RIGHT_TO_LEFT} ;
  233.             ms_operator ["%o1-"] = w ;
  234.         }
  235.         {
  236.             OperatorProperties w = {PREFIX, 20, RIGHT_TO_LEFT} ;
  237.             ms_operator ["%o1*"] = w ;
  238.         }
  239.         {
  240.             OperatorProperties w = {PREFIX, 20, RIGHT_TO_LEFT} ;
  241.             ms_operator ["%o1&"] = w ;
  242.         }
  243.         {
  244.             OperatorProperties w = {PREFIX, 20, RIGHT_TO_LEFT} ; // virtual, it convers to prefix or postfix form
  245.             ms_operator ["++"] = w ;
  246.         }
  247.         {
  248.             OperatorProperties w = {PREFIX, 20, RIGHT_TO_LEFT} ; // virtual
  249.             ms_operator ["--"] = w ;
  250.         }
  251.         {
  252.             OperatorProperties w = {PREFIX, 20, RIGHT_TO_LEFT} ;
  253.             ms_operator ["%o1++"] = w ;
  254.         }
  255.         {
  256.             OperatorProperties w = {PREFIX, 20, RIGHT_TO_LEFT} ;
  257.             ms_operator ["%o1--"] = w ;
  258.         }
  259.         {
  260.             OperatorProperties w = {PREFIX, 20, RIGHT_TO_LEFT} ;
  261.             ms_operator ["%o1!"] = w ;
  262.         }
  263.         {
  264.             OperatorProperties w = {PREFIX, 20, RIGHT_TO_LEFT} ;
  265.             ms_operator ["%o1~"] = w ;
  266.         }
  267.         //postfix: hightest priority        
  268.         {
  269.             OperatorProperties w = {POSTFIX, 21, LEFT_TO_RIGHT} ;
  270.             ms_operator ["%o2--"] = w ;
  271.         }
  272.         {
  273.             OperatorProperties w = {POSTFIX, 21, LEFT_TO_RIGHT} ;
  274.             ms_operator ["%o2++"] = w ;
  275.         }
  276.         {
  277.             OperatorProperties w = {INFIX, 21, LEFT_TO_RIGHT} ;
  278.             ms_operator ["."] = w ;
  279.         }
  280.         {
  281.             OperatorProperties w = {INFIX, 21, LEFT_TO_RIGHT} ;
  282.             ms_operator ["!"] = w ;
  283.         }
  284.         {
  285.             OperatorProperties w = {PAREN, 21, LEFT_TO_RIGHT} ;
  286.             ms_operator ["%lparen"] = w ;
  287.         }
  288.         {
  289.             OperatorProperties w = {PAREN, 21, RIGHT_TO_LEFT} ;
  290.             ms_operator ["%rparen"] = w ;
  291.         }        
  292.         {
  293.             OperatorProperties w = {PAREN, 21, LEFT_TO_RIGHT} ;
  294.             ms_operator ["%lbracket"] = w ;
  295.         }
  296.         {
  297.             OperatorProperties w = {PAREN, 21, RIGHT_TO_LEFT} ;
  298.             ms_operator ["%rbracket"] = w ;
  299.         }        
  300.         {
  301.             OperatorProperties w = {PAREN, 21, LEFT_TO_RIGHT} ;
  302.             ms_operator ["%lbrace"] = w ;
  303.         }
  304.         {
  305.             OperatorProperties w = {PAREN, 21, RIGHT_TO_LEFT} ;
  306.             ms_operator ["%rbrace"] = w ;
  307.         }
  308.     }
  309.  
  310. private :
  311.     int     m_typeId ;
  312.     bool    m_isSameOperator = false ;
  313.     string  m_str ;
  314.     TokenList[] m_vals ;
  315.     TokenList   m_parent ;
  316.     static int     m_numParenths = 0 ;
  317.    
  318.     void setString (string s)
  319.     {
  320.         m_str = s ;
  321.         m_typeId = ID_STRING ;
  322.         m_vals = null ;
  323.     }
  324.  
  325.     void add_node (TokenList node)
  326.     {
  327.         if (m_typeId == ID_VOID)
  328.         {
  329.             m_typeId = ID_LIST ;
  330.             m_vals = new TokenList [1] ;
  331.             m_vals [0] = node ;
  332.             return ;
  333.         }
  334.         if (m_typeId == ID_STRING)
  335.         {
  336.             string data = m_str ;
  337.             m_typeId = ID_LIST ;
  338.             m_vals = new TokenList [2] ;
  339.             m_vals [0] = new TokenList (this, data) ;
  340.             m_vals [1] = node ;
  341.             return ;
  342.         }
  343.         //type_id == ID_LIST
  344.         m_vals ~= node ;
  345.     }
  346.  
  347. public :
  348.     this ()
  349.     {
  350.         m_typeId = ID_VOID ;
  351.         m_str = null ;
  352.         m_vals = null ;
  353.         m_parent = null ;
  354.         return this ;
  355.     }
  356.  
  357.     this (string s)
  358.     {
  359.         this () ;
  360.         setString (s) ;
  361.         return this ;
  362.     }
  363.  
  364.     this (TokenList p)
  365.     {
  366.         this () ;
  367.         m_parent = p ;
  368.         return this ;
  369.     }
  370.  
  371.     this (TokenList p, string s)
  372.     {
  373.         this () ;
  374.         setString (s) ;
  375.         m_parent = p ;
  376.         return this ;
  377.     }
  378.  
  379.     this (TokenList parent, TokenList leaf)
  380.     {
  381.         this () ;
  382.         m_parent = parent ;
  383.         m_typeId = ID_LIST ;
  384.         m_vals = new TokenList [1] ;
  385.         m_vals [0] = leaf ;
  386.         return this ;
  387.     }
  388.  
  389.     string toString ()
  390.     {
  391.         switch (m_typeId)
  392.         {
  393.             case ID_VOID :
  394.                 return "void" ;
  395.             case ID_STRING :
  396.                 return m_str ;
  397.             case ID_LIST :
  398.             {
  399.                 string result = "(" ;
  400.                 foreach (i, val ; m_vals)
  401.                 {
  402.                     result ~= val.toString () ;
  403.                     if (i != m_vals.length - 1)
  404.                         result ~= " " ;
  405.                 }
  406.                 result ~= ")" ;
  407.                 return result ;
  408.             }
  409.         }
  410.     }
  411.    
  412.     string toD_String ()
  413.     {
  414.         switch (m_typeId)
  415.         {
  416.             case ID_VOID :
  417.                 return "void" ;
  418.             case ID_STRING :
  419.                 return m_str ;
  420.             case ID_LIST :
  421.             {
  422.                 string result = "" ;
  423.                 if (m_vals.length >= 1)
  424.                 {
  425.                     if (is_prefix_operator (m_vals [0]))
  426.                     {
  427.                         result ~= m_vals [0].m_str [3 .. $] ;
  428.                         if (m_vals.length != 2)
  429.                             assert (false, "Prefix operator should have only one argument") ;
  430.                         result ~= m_vals [1].toD_String () ;
  431.                     }
  432.                     else
  433.                     if (is_infix_operator (m_vals [0]))
  434.                     {
  435.                         string s = " " ~ m_vals [0].m_str ~ " ";
  436.                         if (s == " %list ")
  437.                             s = " " ;
  438.                         if (m_vals.length < 3)
  439.                             assert (false, "Infix operator should have at list 2 arguments") ;
  440.                         foreach (i, val ; m_vals [1..$-1])
  441.                         {
  442.                             result ~= val.toD_String () ~ s;
  443.                         }
  444.                         result ~= m_vals [$-1].toD_String () ;
  445.                         if (m_isSameOperator)
  446.                             result ~= s ;
  447.                     }
  448.                     else
  449.                     if (is_any_left_paren (m_vals [0]))
  450.                     {
  451.                         string s1, s2 ;
  452.                         switch (m_vals [0].m_str)
  453.                         {
  454.                             case "%lparen"      : s1 = " (" ; s2 = " ) " ; break ;
  455.                             case "%lbracket"    : s1 = " [" ; s2 = " ] " ; break ;
  456.                             case "%lbrace"      : s1 = " {" ; s2 = " } " ; break ;
  457.                         }
  458.                         result ~= s1 ;
  459.                         foreach (val ; m_vals [1 .. $])
  460.                             result ~= " " ~ val.toD_String () ;
  461.                         result ~= s2 ;
  462.                     }
  463.                     else
  464.                     if (is_operator (m_vals [0])) // is postrix operator
  465.                     {
  466.                         if (m_vals.length != 2)
  467.                             assert (false, "Postfix operator should have one argument") ;
  468.                         result ~= m_vals [1].toD_String () ;
  469.                         result ~= " " ~ m_vals [0].m_str [3..$] ;
  470.                     }
  471.                     else  // is data
  472.                     {
  473.                         result ~= " " ~ m_vals [0].toD_String () ;
  474.                     }
  475.                 }
  476.                 //result ~= ")" ;
  477.                 return result ;
  478.             }
  479.         }
  480.     }
  481.    
  482.     unittest
  483.     {
  484.         TokenList list = new TokenList ;
  485.  
  486.         list.setString ("123");
  487.         assert (list.toString () == "123") ;
  488.  
  489.         list.m_typeId = ID_VOID ;
  490.         assert (list.toString () == "void") ;
  491.  
  492.         list.m_typeId = ID_LIST ;
  493.         list.m_vals = new TokenList [4] ;
  494.         list.m_vals [0] = new TokenList ("+") ;
  495.         list.m_vals [1] = new TokenList ("a") ;
  496.         list.m_vals [2] = new TokenList () ;
  497.         list.m_vals [2].m_typeId = ID_LIST ;
  498.         list.m_vals [2].m_vals = new TokenList [3] ;
  499.         list.m_vals [2].m_vals [0] = new TokenList ("*") ;
  500.         list.m_vals [2].m_vals [1] = new TokenList ("b") ;
  501.         list.m_vals [2].m_vals [2] = new TokenList ("c") ;
  502.         list.m_vals [3] = new TokenList ("d") ;
  503.         assert (list.toString () == "(+ a (* b c) d)", list.toString ()) ;
  504.     }
  505.  
  506.     static bool is_operator (string s)
  507.     {
  508.         return (s in ms_operator) != null;
  509.     }
  510.  
  511.     static bool is_operator (TokenList list)
  512.     {
  513.         if (list !is null && list.m_typeId == ID_STRING)
  514.             return (list.m_str in ms_operator) != null ;
  515.         return false ;
  516.     }
  517.  
  518.     static bool is_prefix_operator (string s)
  519.     {
  520.         if ((s in ms_operator) is null)
  521.             return false ;
  522.         return ms_operator [s].type == PREFIX ;
  523.     }
  524.  
  525.     static bool is_prefix_operator (TokenList list)
  526.     {
  527.         if (list !is null && list.m_typeId == ID_STRING)
  528.             return is_prefix_operator (list.m_str) ;
  529.         return false ;
  530.     }
  531.  
  532.     static bool is_infix_operator (string s)
  533.     {
  534.         if ((s in ms_operator) is null)
  535.             return false ;
  536.         return ms_operator [s].type == INFIX ;
  537.     }
  538.  
  539.     static bool is_infix_operator (TokenList list)
  540.     {
  541.         if (list !is null && list.m_typeId == ID_STRING)
  542.             return is_infix_operator (list.m_str) ;
  543.         return false ;
  544.     }
  545.  
  546.     static bool is_any_left_paren (string s)
  547.     {
  548.         if ((s in ms_operator) is null)
  549.             return false ;
  550.         return ms_operator [s].type == PAREN && s [1] == 'l' ;
  551.     }
  552.  
  553.     static bool is_any_left_paren (TokenList list)
  554.     {
  555.         if  (list !is null && list.m_typeId == ID_STRING && is_any_left_paren (list.m_str))
  556.             return true ;
  557.         return false ;
  558.     }
  559.    
  560.     static private bool is_any_right_paren (string s)
  561.     {
  562.         if ((s in ms_operator) is null)
  563.             return false ;
  564.         return ms_operator [s].type == PAREN && s [1] == 'r' ;
  565.     }
  566.  
  567.     static private bool is_any_right_paren (TokenList list)
  568.     {
  569.         if  (list !is null && list.m_typeId == ID_STRING && is_any_right_paren (list.m_str))
  570.             return true ;
  571.         return false ;
  572.     }
  573.  
  574.     //TODO : remove, as direction is used directly
  575.     /+
  576.     static private int operator_direction (string s)
  577.     {
  578.         if (s in ms_operator)
  579.         {
  580.             return ms_operator [s].direction ;
  581.         }
  582.         return LEFT_TO_RIGHT ;
  583.     }
  584.     +/
  585.  
  586.     private TokenList add_d (string s)
  587.     {
  588.         //rule 1.0
  589.         if (!is_operator (s))
  590.         {
  591.             // rule 1.1
  592.             if (m_typeId == ID_STRING && !is_operator (m_str))
  593.             {
  594.                 TokenList old_parent = this.m_parent ;
  595.                 TokenList new_parent = new TokenList (old_parent) ;
  596.                 new_parent.m_typeId = ID_LIST ;
  597.                 new_parent.m_vals.length = 0 ;
  598.                 new_parent.m_vals ~= new TokenList ("%list") ;
  599.                 new_parent.m_vals ~= this ;
  600.                 new_parent.m_vals ~= new TokenList (s) ;
  601.                 this = new_parent ;
  602.                 return this;
  603.             }
  604.             else if (m_typeId == ID_LIST && m_vals.length == 1 && !is_operator (m_vals [0]))
  605.             {
  606.                 m_vals ~= m_vals [0] ;
  607.                 m_vals [0] = new TokenList ("%list") ;
  608.                 m_vals ~= new TokenList (s) ;
  609.                 return this ;
  610.             }
  611.             else if (m_typeId == ID_LIST && (
  612.                 m_vals.length == 2 && (is_prefix_operator (m_vals [0]) || is_any_left_paren (m_vals [0]))
  613.                 || m_vals.length >= 3 && is_infix_operator (m_vals [0]) && !m_isSameOperator))
  614.             {
  615.                 this = add_d ("%list") ;
  616.                 this = add_d (s) ;
  617.                 return this ;
  618.             }
  619.            
  620.             //rule 1.2
  621.             add_node (new TokenList (this, s)) ;
  622.             m_isSameOperator = false ;
  623.             return this ;
  624.         }
  625.         //is operator:
  626.         //rule 2.0
  627.         if (s == "++" || s == "--")
  628.         {
  629.             if (m_typeId == ID_STRING )
  630.             {
  631.                 if (! is_operator (m_str))
  632.                 {
  633.                     TokenList old_parent = this.m_parent ;
  634.                     if (old_parent is null)
  635.                     {
  636.                         old_parent = new TokenList (null, cast(TokenList)null) ;
  637.                     }
  638.                     TokenList new_parent = new TokenList (old_parent, new TokenList ("%o2" ~ s)) ;
  639.                     new_parent.m_vals [0].m_parent = new_parent ;
  640.                     new_parent.m_vals ~= this ;
  641.                     this.m_parent = new_parent ;
  642.                     old_parent.m_vals [0] = new_parent ;
  643.                     this = old_parent ;
  644.                     return this ;
  645.                 }
  646.             }
  647.             if (m_typeId == ID_LIST)
  648.             {
  649.                 if (m_vals.length == 1 && !is_operator (m_vals [0]))
  650.                 {
  651.                     auto cp_list = m_vals [0] ;
  652.                     m_vals [0] = new TokenList (this, "%o2" ~ s) ;
  653.                     m_vals ~= cp_list ;
  654.                     return this ;
  655.                 }
  656.                 if (m_vals.length >= 2 && (is_prefix_operator (m_vals [0]) || is_any_left_paren (m_vals [0]))
  657.                     || m_vals.length >= 3 && is_infix_operator (m_vals [0]) && !m_isSameOperator)
  658.                 {
  659.                     TokenList data = m_vals [$-1] ;
  660.                     m_vals [$-1] = new TokenList (this, new TokenList ("%o2" ~ s)) ;
  661.                     m_vals [$-1].m_vals [0].m_parent = m_vals [$-1] ;
  662.                     m_vals [$-1].add_node (data) ;
  663.                     data.m_parent = m_vals [$-1] ;
  664.                     return this ;
  665.                 }
  666.             }
  667.         }
  668.        
  669.         //rule 2.0.1
  670.         if (is_any_left_paren (s))
  671.         {
  672.             if (m_typeId == ID_VOID || m_typeId == ID_LIST && m_vals.length == 0)
  673.             {
  674.                 add_node (new TokenList (this, s)) ;
  675.                 ++ m_numParenths ;
  676.                 return this ;
  677.             }
  678.             if (m_typeId == ID_LIST && (
  679.                     is_infix_operator (m_vals [0]) &&
  680.                         (m_vals.length == 2  || m_vals.length >= 3 && m_isSameOperator)
  681.                     || m_vals.length == 1 && (is_prefix_operator (m_vals [0]) || is_any_left_paren (m_vals [0]))
  682.                     ) )
  683.             {
  684.                 m_isSameOperator = false ;
  685.                 auto list = new TokenList (this) ;
  686.                 list.add_node (new TokenList (list, s)) ;
  687.                 add_node (list) ;
  688.                 ++ m_numParenths ;
  689.                 this = list ;
  690.                 return this ;
  691.             }
  692.             if (m_typeId == ID_LIST && (
  693.                     m_vals.length >= 3 && is_infix_operator (m_vals [0]) && !m_isSameOperator
  694.                     || m_vals.length == 2 && (is_prefix_operator (m_vals [0]) || is_any_left_paren (m_vals [0]))
  695.                     ) )
  696.             {
  697.                  auto nl1 = new TokenList (this) ;
  698.                  nl1.add_node (new TokenList (nl1, "%list")) ;
  699.                  nl1.m_vals ~= m_vals [$-1] ;
  700.                  nl1.m_vals [1].m_parent = nl1 ;
  701.                  auto nl2 = new TokenList (nl1) ;
  702.                  nl2.add_node (new TokenList (nl1, s)) ;
  703.                  nl1.m_vals ~= nl2 ;
  704.                  m_vals [$-1] = nl1 ;
  705.                  ++ m_numParenths ;
  706.                  this = nl2 ;                      
  707.                  return this ;
  708.             }
  709.            
  710.             if (m_typeId == ID_LIST && m_vals.length == 1 && !is_operator (m_vals [0]))
  711.             {
  712.                 auto list = m_vals [0] ;
  713.                 m_vals [0] = new TokenList (this, "%list") ;
  714.                 m_vals ~= list ;
  715.                 auto c_list = new TokenList (this) ;
  716.                 c_list.add_node (new TokenList (c_list, s)) ;
  717.                 m_vals ~= c_list ;
  718.                 this = c_list ;
  719.                 ++ m_numParenths ;
  720.                 return this ;
  721.             }
  722.             assert (false, "AST error : this can't happen") ;
  723.         }
  724.        
  725.         //todo: rule 2.0.2
  726.         if (is_any_right_paren (s))
  727.         {
  728.             -- m_numParenths ;
  729.             if (m_numParenths < 0)
  730.                 assert (false, "AST error : Too much rigth " ~ s) ;
  731.         l_rule_2_0_2_local : ;  //horrible, but, eh... can be for (;;)
  732.             if (m_typeId != ID_LIST
  733.                 || m_typeId == ID_LIST && (m_vals.length == 0 ||
  734.                     m_vals.length >= 1 && !is_operator (m_vals [0]) ) )
  735.                 assert (0, "AST error : Too much rigth " ~ s) ;
  736.             if (is_any_left_paren (m_vals [0]))
  737.             {
  738.                 if (m_vals [0].m_str [2..$] != s [2..$])
  739.                     assert (false, "AST error : no closing to "~m_vals [0].m_str ) ;
  740.                 if (m_parent !is null)
  741.                 {
  742.                     this = m_parent ;
  743.                     return this ;
  744.                 }
  745.                 return this ;
  746.             }
  747.             if (m_parent is null)
  748.                 assert (0, "AST error : Too much rigth " ~ s) ;
  749.             this = m_parent ;
  750.             goto l_rule_2_0_2_local ;
  751.             assert (0, "Can't be here") ;            
  752.         }
  753.  
  754.         //rule 2.1
  755.         //todo:
  756.         if (m_typeId == ID_LIST && m_vals.length >= 1 &&
  757.                 (is_infix_operator (m_vals [0]) &&
  758.                     ( m_vals.length <= 2 || m_vals.length >= 3 && m_isSameOperator)                
  759.                 || is_prefix_operator (m_vals [0]) && m_vals.length == 1)
  760.                 //&& !is_any_left_paren (m_vals [0])
  761.             || m_typeId == ID_VOID || m_typeId == ID_LIST && m_vals.length == 0
  762.             || m_typeId == ID_LIST && m_vals.length == 1 && is_any_left_paren (m_vals [0]) )
  763.         {
  764.             m_isSameOperator = false ;
  765.             string new_op = "%o1" ~ s ;
  766.             if ((new_op in ms_operator) == null)
  767.                 assert (false, "AST error - unknown operator " ~ new_op) ;
  768.             auto new_op_list = new TokenList (this, new_op) ;
  769.             if (m_typeId == ID_VOID)
  770.             {
  771.                 add_node (new_op_list) ;
  772.             }
  773.             else
  774.             {
  775.                 TokenList pre_list = new TokenList (this, new_op_list) ;
  776.                 new_op_list.m_parent = pre_list ;
  777.                 add_node (pre_list) ;
  778.                 this = pre_list ;
  779.             }
  780.             return this ;
  781.         }
  782.  
  783.         //rule 2.2
  784.     l_rule_2_2 : ;
  785.         if (m_typeId == ID_STRING && !is_operator (this)
  786.             || m_typeId == ID_LIST && m_vals.length == 1 && !is_operator (m_vals [0]))
  787.         {
  788.             TokenList swap ;
  789.             if (m_typeId == ID_STRING)
  790.             {
  791.                 swap = new TokenList (this, m_str) ;
  792.             }
  793.             else if (m_typeId == ID_LIST && m_vals.length == 1)
  794.                 swap = m_vals [0] ;
  795.             add_node (swap) ;
  796.             m_vals [0] = new TokenList (this, s) ;
  797.             return this ;
  798.         }
  799.  
  800.         //rule 2.2.1
  801.         if (m_typeId == ID_LIST && (
  802.                 m_vals.length >= 3 && is_infix_operator (m_vals [0]) && !m_isSameOperator
  803.                     /* && (s in ms_operator) != null  -- already tested */
  804.                     && ms_operator [s].priority > ms_operator [this.m_vals [0].m_str].priority
  805.                 || m_vals.length >= 2 && is_prefix_operator (m_vals [0])
  806.                         && ms_operator [s].priority > ms_operator [this.m_vals [0].m_str].priority
  807.                 || m_vals.length >= 2 && is_any_left_paren (m_vals [0]) )
  808.             )
  809.         {
  810.             auto new_op_list = new TokenList (this, new TokenList (null, s)) ;
  811.             new_op_list.m_vals [0].m_parent = new_op_list ;
  812.             new_op_list.add_node (this.m_vals [$-1]) ;
  813.             m_vals [$-1] = new_op_list ;
  814.             this = new_op_list ;
  815.             return this ;
  816.         }
  817.  
  818.         //rule 2.3
  819.         if (m_typeId == ID_LIST && m_vals.length >= 1 && is_operator (m_vals [0]) &&
  820.             ms_operator [s].priority < ms_operator [m_vals [0].m_str].priority )
  821.         {
  822.             if (! is_any_left_paren (m_vals [0]))
  823.             {
  824.                 if (m_parent is null)
  825.                     m_parent = new TokenList (null, this) ;
  826.                 this = m_parent ;
  827.                 goto l_rule_2_2 ;
  828.             }
  829.         }
  830.        
  831.         //rule 2.4
  832.         if (m_typeId == ID_LIST && m_vals.length >= 2)
  833.         {
  834.             auto val = m_vals [0] ;
  835.             if (is_operator (val))
  836.             {
  837.                 auto str = val.m_str ;
  838.                 auto this_op = ms_operator [s] ;
  839.                 auto curr_op = ms_operator [str] ;
  840.                 if (this_op.priority == curr_op.priority
  841.                     && !is_any_left_paren (str) && !is_prefix_operator (str))
  842.                 {
  843.                     if (this_op.direction != curr_op.direction)
  844.                         assert (false,
  845. "AST error : currently no support for operators with different directions to be equal in priority") ;
  846.                     if (this_op.direction == RIGHT_TO_LEFT)
  847.                     {
  848.                         auto op_list = new TokenList (this, new TokenList (null, s)) ;
  849.                         op_list.m_vals [0].m_parent = op_list ;
  850.                         op_list.add_node (m_vals [$-1]) ;
  851.                         op_list.m_vals [1].m_parent = op_list ;
  852.                         m_vals [$-1] = op_list ;
  853.                         this = op_list ;
  854.                         return this ;
  855.                     }
  856.                     //direction == LEFT_TO_RIGHT
  857.                     if (str != s)
  858.                     {
  859.                         if (m_parent is null)
  860.                         {
  861.                             m_parent = new TokenList (null, this) ;
  862.                         }
  863.                         this = m_parent ;
  864.                         goto l_rule_2_2 ;
  865.                     }
  866.                     //rule 2.4 г
  867.                     m_isSameOperator = true ;
  868.                     return this ;
  869.                 }
  870.             }
  871.         }
  872.         assert (0, "AST no matching rule to \"" ~ s ~ "\"") ;
  873.         //return this ;
  874.     }
  875.  
  876.     static TokenList parseD (string s)
  877.     {
  878.         /+  PREUDOCODE
  879.         int ws = -1 ;
  880.         for (int i = 0 ; i < s.len ;)
  881.         {
  882.             skip_space () ;
  883.             skip_comments () ;
  884.             if (if_nameable (s [i]) )
  885.                 ws = i ;
  886.                 do_while_nameabe (s [i]) ;
  887.                  ++i;
  888.             word = s [ws .. i] ;
  889.             add_d (word)
  890.             continue ;
  891.  
  892.             if (is_first_operator_symbol (s[i]))
  893.                 max_op = s [i]
  894.                 while max_op + s[i+1] in operators
  895.                     max_op ~= s [i+1]
  896.                     ++i ;
  897.             add_d (max_op) ;
  898.         }
  899.         +/
  900.         bool is_nameable (char c)
  901.         {
  902.             immutable byte [] symbs =
  903.             [
  904.                 '_', '@', '$'
  905.             ] ;
  906.             bool result = false ;
  907.             if ('a' <= c && c <= 'z')
  908.                 result = true ;
  909.             if ('A' <= c && c <= 'Z')
  910.                 result = true ;
  911.             if ('0' <= c && c <= '9')
  912.                 result = true ;
  913.             foreach (i ; symbs)
  914.                 if (c == i)
  915.                 {
  916.                     result = true ;
  917.                     break ;
  918.                 }
  919.             return result ;
  920.         }
  921.  
  922.         bool is_first_operator_symbol (char c)
  923.         {
  924.             immutable ubyte [] symbs =
  925.             [
  926.                 ';', ',', '=', '?', ':', '|', '&',
  927.                 '^', '<', '>', '!', '+', '-', '*', '/', '%', '~', '.',
  928.                 '[', ']', '(', ')', '{', '}',
  929.             ] ;
  930.             foreach (v ; symbs)
  931.                 if (c == v)
  932.                     return true ;
  933.             return false ;
  934.         }
  935.  
  936.         auto list = new TokenList () ;
  937.         list.m_typeId = ID_VOID ;
  938.         list.m_str = null ;
  939.         list.m_vals = null ;
  940.  
  941.         int ws = -1 ;
  942.         for (int i = 0 ; i < s.length ;)
  943.         {
  944.             while (i < s.length && isspace (s [i]))
  945.                 ++ i ;
  946.  
  947.             //TODO : skip_comments () ;
  948.  
  949.             if (i < s.length && is_nameable (s [i]) )
  950.             {
  951.                 ws = i ;
  952.                 ++i ;
  953.                 while (i < s.length && is_nameable (s [i]) )
  954.                     ++i ;
  955.                 string word = s [ws .. i] ;
  956.                 list = list.add_d (word) ;
  957.                 continue ;
  958.             }
  959.  
  960.             if (i < s.length && is_first_operator_symbol (s[i]))
  961.             {
  962.                 string max_op = "" ~ s [i] ;
  963.                 ++ i ;
  964.                 while (i < s.length && (max_op ~ s[i]) in ms_operator)
  965.                 {
  966.                     max_op ~= s [i] ;
  967.                     ++i ;
  968.                 }
  969.                 switch (max_op)
  970.                 {
  971.                     case "(" : max_op = "%lparen" ; break ;
  972.                     case ")" : max_op = "%rparen" ; break ;
  973.                     case "[" : max_op = "%lbracket" ; break ;
  974.                     case "]" : max_op = "%rbracket" ; break ;
  975.                     case "{" : max_op = "%lbrace" ; break ;
  976.                     case "}" : max_op = "%rbrace" ; break ;
  977.                     default : break ;
  978.                 }
  979.                 list = list.add_d (max_op) ;
  980.                 continue ;
  981.             }
  982.         }
  983.        
  984.         while (list.m_parent !is null)
  985.             list = list.m_parent ;
  986.         return list ;
  987.     }
  988.    
  989.     unittest
  990.     {
  991.         TokenList test ; //= new TokenList () ;
  992.        
  993.         test = TokenList.parseD ("++a . b * c") ;
  994.         assert (test.toString () == "(* (%o1++ (. a b)) c)") ;
  995.        
  996.         test = TokenList.parseD ("a + b * c") ;
  997.         assert (test.toString () == "(+ a (* b c))") ;
  998.        
  999.         test = TokenList.parseD ("a + b + * c") ;
  1000.         assert (test.toString () == "(+ a b (%o1* c))") ;
  1001.        
  1002.         test = TokenList.parseD ("a + b * c * d") ;
  1003.         assert (test.toString () == "(+ a (* b c d))") ;
  1004.        
  1005.         test = TokenList.parseD ("a + b + c") ;
  1006.         assert (test.toString () == "(+ a b c)") ;
  1007.        
  1008.         test = TokenList.parseD ("a * b + c") ;
  1009.         assert (test.toString () == "(+ (* a b) c)") ;
  1010.        
  1011.         test = TokenList.parseD ("a * (b + c) ") ;
  1012.         assert (test.toString () == "(* a (%lparen (+ b c)))") ;
  1013.        
  1014.         test = TokenList.parseD ("a + b c ") ;
  1015.         assert (test.toString () == "(+ a (%list b c))") ;
  1016.        
  1017.         test = TokenList.parseD ("a . b c ") ;
  1018.        
  1019.         assert (test.toString () == "(%list (. a b) c)") ;
  1020.         test = TokenList.parseD ("a * (b + c / d ++ ) ") ;
  1021.         assert (test.toString () == "(* a (%lparen (+ b (/ c (%o2++ d)))))") ;
  1022.        
  1023.         test = TokenList.parseD ("a ++") ;
  1024.         assert (test.toString () == "(%o2++ a)") ;
  1025.        
  1026.         test = TokenList.parseD ("(a ++)") ;
  1027.         assert (test.toString () == "(%lparen (%o2++ a))") ;
  1028.        
  1029.         test = TokenList.parseD (" + a") ;
  1030.         assert (test.toString () == "(%o1+ a)") ;
  1031.    
  1032.         test = TokenList.parseD ("{abb + (x+c); c, ++d.x ;d ; e+f ; if (x = 1) x + 1 ;}") ;
  1033.         assert (test.toString () == "(%lbrace (; (+ abb (%lparen (+ x c))) (, c (%o1++ (. d x))) " ~
  1034.             "d (+ e f) (+ (%list if (%lparen (= x 1)) x) 1)))") ;
  1035.         //writeln (test.toD_String ()) ;
  1036.  
  1037.         test = TokenList.parseD ("a [] + b") ;
  1038.         assert (test.toString () == "(+ (%list a (%lbracket)) b)") ;
  1039.  
  1040.         test = TokenList.parseD ("a + b []") ;
  1041.         assert (test.toString () == "(+ a (%list b (%lbracket)))") ;
  1042.        
  1043.         test = TokenList.parseD ("a . b []") ;
  1044.         assert (test.toString () == "(. a (%list b (%lbracket)))") ;
  1045.        
  1046.         test = TokenList.parseD ("(a b)") ;
  1047.         assert (test.toString () == "(%lparen (%list a b))") ;
  1048.        
  1049.         test = TokenList.parseD ("a++ . b") ;
  1050.         assert (test.toString () == "(. (%o2++ a) b)") ;
  1051.        
  1052.         test = TokenList.parseD ("++a . b") ;
  1053.         assert (test.toString () == "(%o1++ (. a b))") ;
  1054.  
  1055.         test = TokenList.parseD ("++a ; b ;") ;
  1056.         assert (test.toString () == "(; (%o1++ a) b)" && test.m_isSameOperator) ;
  1057.        
  1058.         test = TokenList.parseD ("+ +a ") ;
  1059.         assert (test.toString () == "(%o1+ (%o1+ a))") ;
  1060.        
  1061.         test = TokenList.parseD ("i = 1:1:10, if(i % 2 == 0); i*i +1") ;
  1062.         assert (test.toString () == "(; (, (= i (: 1 1 10)) (%list if (%lparen (== (% i 2) 0)))) " ~
  1063.             "(+ (* i i) 1))") ;
  1064.         //writeln (test.toD_String ()) ;
  1065.        
  1066.     }
  1067.    
  1068.     string getStringItem (int n)
  1069.     {
  1070.         assert (m_typeId == ID_LIST, "AST error : expected ID_LIST argument, but found "
  1071.                 ~ (m_typeId == ID_VOID ? "ID_VOID" : "ID_STRING") ) ;
  1072.         assert (m_vals.length > n, "AST error : index out of bounds") ;
  1073.         assert (m_vals [n].m_typeId == ID_STRING, "AST error : List should be of type string") ;
  1074.         return m_vals [n].m_str ;
  1075.     }
  1076.    
  1077.     TokenList getItem (int n)
  1078.     {
  1079.         assert (m_typeId == ID_LIST, "AST error : expected ID_LIST argument, but found "
  1080.                 ~ (m_typeId == ID_VOID ? "ID_VOID" : "ID_STRING") ) ;
  1081.         assert (m_vals.length > n, "AST error : index out of bounds") ;
  1082.         return m_vals [n] ;
  1083.     }
  1084.    
  1085.     @property int typeId ()
  1086.     {
  1087.         return m_typeId ;
  1088.     }
  1089.    
  1090.     @property bool isEndSeparator ()
  1091.     {
  1092.         return m_isSameOperator ;
  1093.     }
  1094.    
  1095.     @property string str ()
  1096.     {
  1097.         assert (m_typeId == ID_STRING, "AST error : expected list m_typeId to be ID_STRING") ;
  1098.         return m_str ;
  1099.     }
  1100.    
  1101.     @property int length  ()
  1102.     {
  1103.         assert (m_typeId == ID_LIST, "AST error : expected list m_typeId to be ID_LIST") ;
  1104.         return m_vals.length ;
  1105.     }
  1106. }