Which one is "better" ?

[Baldurien (club internet)]

Hello

I  have  a  grammar  to do for my self, and since this grammar add the
same  expression  than  the one we could have in a SQL query language,
I'm wondering which grammar is better in term of performance.

My first one is the classical "one production per precedence" :

start: VARSTART e_no_prec VAREND
     ;

e_no_prec: e_xor OR e_no_prec
         | e_xor
         ;
e_xor: e_and XOR e_xor
     | e_and
     ;
e_and: e_equal_in AND e_and
     | e_equal_in
     ;

e_equal_in: e_cmp IN e_cmp
          | e_cmp IS e_cmp
          | e_cmp EQ e_cmp
          | e_cmp NE e_cmp
          | e_cmp '=' e_cmp
          | e_cmp
          ;
e_cmp: e_additive '<' e_additive
     | e_additive '>' e_additive
     | e_additive LE e_additive
     | e_additive GE e_additive
     | e_additive BETWEEN e_additive AND e_additive
     | e_additive
     ;

e_additive: e_mult '+' e_additive
          | e_mult '-' e_additive
          | e_mult CONCAT e_additive
          | e_mult
          ;

e_mult: e_final '/' e_mult
      | e_final '*' e_mult
      | e_final '%' e_mult
      | e_final
      ;

e_final: '(' e_no_prec ')'
       | constant
       | variable
       ;

This  works fine, and do what I want. But I've got a lot of rules, and
it give me 70 states for the automata.


With %left, and %nonassoc (and %right too) it give this :


start: VARSTART expr VAREND
     ;
     
expr: expr XTF_T_LOGICAL_OR expr
    | expr XTF_T_LOGICAL_XOR expr
    | expr XTF_T_LOGICAL_AND expr
    | expr_no_and
    ;
expr_no_and: expr_no_and XTF_T_IN expr_no_and
           | expr_no_and XTF_T_IS expr_no_and
           | expr_no_and XTF_T_CMP_EQ expr_no_and
           | expr_no_and '=' expr_no_and
           | expr_no_and XTF_T_CMP_NE expr_no_and
       
           | expr_no_and '<' expr_no_and
           | expr_no_and '>' expr_no_and
           | expr_no_and XTF_T_CMP_GE expr_no_and
           | expr_no_and XTF_T_CMP_LE expr_no_and
           | expr_no_and XTF_T_BETWEEN expr_no_and XTF_T_LOGICAL_AND expr_no_and
       
           | expr_no_and '+' expr_no_and
           | expr_no_and '-' expr_no_and
           | expr_no_and XTF_T_STRING_CONCAT expr_no_and
       
           | expr_no_and '/' expr_no_and
           | expr_no_and '%' expr_no_and
           | expr_no_and '*' expr_no_and

           | '(' expr ')'
       
           | constant
           | variable
           ;

(constant and variable are the same in the two grammars).

This  also  works  fine,  and  give me 64 states : but the Output file
shows me a bigger automata in term of transition.

The  second  one  is  based  on the grammar provided by PHP, and mySQL
(respectivly zend_language_parser.y and sql_parser.yy).


The  problem  here  is  that  I actually don't know which one I should
choose  :  the first get more state, but less transition per state, so
it  not  so  bad.  The second give less state, but more transition per
states.

Finally,  I  want to translate the generated parser in PHP, for that I
have  to  parse  the  output  file to get some arrays and by the time,
create some kind of transition table (well, it was my first idea) :

Is  there  a  better method ? (I don't understand how work exactly the
algorithm  in Bison, and I don't know if I can handle it without using
goto like Bison does).

Notice  that  I  don't  want  to write a manual parser (aka: using one
function  per  rules)  since  it  must be written in PHP, and I prefer
avoiding them.