[PHP4BETA] zend-parser.y shift/reduce conflicts and suggestions

I have seen that the Zend scanner does not solve shift/reduce conflicts for IF/ELSE statements very cleanly. In fact I suspect that the current implementation also has reduce/reduce conflicts after parsing "if(condition)" where a reduce action is required, but where there is no clean solution do decide which reduction will match (this is because the "else" and "elseif" branchs have been made optional using null reductions. I think that this causes poor analysis for IF/ELSE and for ELSE IF constructs. But there's an alternative in yacc/Bison to solve this, which does not cause problems with ELSE IF combined-statements. Here is what I have written for a running Sybase Transac SQL parser, which does not exhibit any shift/reduce and reduce/reduce conflict when introducing the ELSE IF construction (by two consecutive IF/ELSE statements) when I want to detect exclusive branchs. This code was necessary in a compiler to avoid much code redondancy and to enhance the readability of the generated code, avoiding many embedded instruction blocks: ------------ cut here (begin 1) ------------- %union { /* token type names definitions (snipped)... */ } /* tokens with precedence */ %nonassoc LOWER_THAN_ELSE /* pseudo-token which never gets generated by flex */ /* but is only used for precedence resolution. */ /* this token must have immediate lower priority */ /* than the ELSE token. */ %nonassoc ELSE %left OR %left AND %left NOT %left TIMES_EQUAL EQUAL_TIMES '=' '<' '>' %nonassoc '!' %left '+' '-' '|' '^' '&' DOUBLE_PIPES %left '*' '/' '%' %nonassoc UMINUS '~' /* UMINUS never gets generated by flex but is */ /* convenient when fixing precedence of an unary '-' */ /* operator */ /* other tokens... */ %token IF WHILE BREAK RETURN GOTO /* etc... */ %% statement_list: statement { GiConstTokenState = L_TOP; } | statement_list statement { GiConstTokenState = L_TOP; } ; statement: if_condition_statement %prec LOWER_THAN_ELSE { vEndIf(); } | if_condition_statement ELSE { vElseBranch(); } statement_but_if %prec ELSE { vEndIf(); } | statement_but_if ; if_condition_statement: IF { GiLanguageState = S_SPL; } search_condition { vIfStatement($3); GiLanguageState = S_INIT; } statement | if_condition_statement ELSE IF { GiLanguageState = S_SPL; } search_condition { vElifBranch($5); GiLanguageState = S_INIT; } statement ; statement_but_if: declare_variable_list | begin_end_block | break_statement /* | other statements (snipped)... */ ; ------------ cut here (end 1) ------------- The main idea there is that we do not need to markup the end of IF/ELSEIF/ELSE constructs by special marks like an ENDIF keyword, and we are still able to detect "ELSE IF" constructs, only by its combined syntax while preserving the syntax and semantic of the simple IF statement with a single optionnal ELSE branch. More, you do not need rules with empty alternates which cause parser to produce much more reductions than necessary, and sometimes produces bad code in the actions launched from reductions. Note that my grammar does not require a specific ELSEIF token to be detected by the scanner, so they are detected as two separate tokens with any number of blanks or comments between them (this suppresses complex regular expressions tricks used to detect an ELSEIF single token and this allows the preservation of comments in the code generation phase if they are desired...) Note also that in the code above, the GiLanguageState and GiConstTokenState are used only by the code generator, and it does not alter the syntaxic parser. They are there only to demonstrate that you can really insert code reduction rules at the places where they are shown without introducing any reduce/reduce conflicts. The role of my two variables are to manage some special tokens (e.g. CLIENT, FILE or SIZE) which may be recognized as such by the lexer but which in most cases are simple regular identifiers that can be used as column names or table names when they are not used in some specific Sybase statements. In zend-parser.y, the same technic could be applied: you only need to define statement like I did (it only defines the IF/ELSE statements constructs), and then report all other statements that already are present in your existing "statement" rule into another rule (here named "statement_but_if"). Doing that you'll see that the generated parser is greatly reduced in size because you solve many shift/reduce conflicts otherwise only solved in too many rules by an extensive use of operator precedence... For better performance and for code size reduction, statement lists should also have their empty branch removed, by adding rules that match alternate forms where an existing rule are empty (today), and could simply not exist (if you make the change). There are many reasons to do it: - The parser complexity does not depend on the number of rules - A parser with nullable non terminal tokens generates much more states because the next look-ahead lexical token can cross several non-terminal nullable tokens, so this creates many reduce/reduce conflicts that forbids the extension of the syntax without many stormbraining kludges in the syntax. - This really reduces the total number of reductions and greatly enhance the syntax recognition and selectivity of the parser (and it allows a better recovery of syntax errors which otherwise can only be done at the top syntax level, which means that any syntax error cannot recover and aborts the scanner, and implies that very few information are available to help the language scripter to correct this error !). - By eliminating nullable non terminal tokens, you may divide the overall size of the generated parser often by 4 or dozens, because you will reduce the global number of parser states !! - A parser in which the forms of a syntax explicitly show when an optional member really exists can produce more complex code only when these optionnal members are there, and often can produce much simpler actions when these members are not specified in the source being parsed, because there are more rules and the generation decision is made at the parsing stage instead of the generation stages, eliminating many states variables, eliminating many sources of bugs due to the value of these "global" states variables, and improving the global speed of the generator, while not altering the speed of the parser. - While eliminating empty rules for a nullable token you'll see that some forms of expressions are simply illegal (because despite they are syntaxically correct with the intuitive simple syntax their semantics are always incorrect) and can be simply eliminated from the accepted syntax, instead of detecting them later by semantic rules, because the intuitive simple syntax is too laxist. Avoiding these unnecessary branches, you can eliminate many reduce/reduce conflicts, and divide the number of states in your parser (so you also reduce the parser code size!) - Eliminating nullable tokens in a grammar is not always easy because of the presence of generating actions which must be copied with all token variables ($1, $2, ...) being renumbered, and many assignments to $$ removed. It can sometimes be quite brainstorming. But the final value you get from this chalenge is really cost-effective: your language gains in abstraction, and gains extensitivity in areas which could have been impossible without generating many, many syntax conflicts. For example doing it allows you to create new operators, new forms of declarations, new contextual grammar forms such as when adding OO functionalities to an existing language... Note in the code below that for the "top_statement_list" (which may be empty), the simplest way to make it not nullable is to add a T_EOF token generated by the scanner. Also note that this grammar does not only use T_ELSEIF but simply uses T_ELSE T_IF as two separate tokens (this eliminates the Lexer kludge about comments and blanks between them, if you want to accept the form "else if" as equivalent to the PHP "elseif" keyword). ------------ cut here (begin 2) ------------- %nonassoc T_LOWER_THAN_ELSE /* make these 2 tokens first in that order */ %nonassoc T_ELSE /* ... other tokens for statements... */ %% /* Rules */ language: statement_list T_EOF | T_EOF ; statement_list: statement { ELS_FETCH(); HANDLE_INTERACTIVE(); } | statement_list { do_extended_info(CLS_C); } statement { ELS_FETCH(); HANDLE_INTERACTIVE(); } ; statement: if_condition_statement %prec T_LOWER_THAN_ELSE { do_if_end(CLS_C); } | if_condition_statement T_ELSE statement_but_if %prec T_ELSE { do_if_end(CLS_C); } | newif_condition_statement T_ENDIF ';' { do_if_end(CLS_C); } | newif_condition_statement T_ELSE ':' statement T_ENDIF ';' { do_if_end(CLS_C); } | statement_but_if ; if_condition_statement: T_IF '(' expr ')' { do_if_cond(&$3, &$4 CLS_CC); } statement { do_if_after_statement(&$4, 1 CLS_CC); } | if_condition_statement T_ELSEIF '(' expr ')' { do_if_cond(&$4, &$5 CLS_CC); } statement { do_if_after_statement(&$5, 0 CLS_CC); } /* accept also the "else if" form with separate tokens: */ | if_condition_statement T_ELSE T_IF '(' expr ')' { do_if_cond(&$5, &$6 CLS_CC); } statement { do_if_after_statement(&$6, 0 CLS_CC); } ; newif_condition_statement: /* here the ':' is required to force the detection of the "endif;" tokens */ T_IF '(' expr ')' ':' { do_if_cond(&$3, &$4 CLS_CC); } statement { do_if_after_statement(&$4, 1 CLS_CC); } /* elseif constructs normally require a ':' but this is not necessary */ | newif_condition_statement T_ELSEIF '(' expr ')' ':' { do_if_cond(&$4, &$5 CLS_CC); } statement { do_if_after_statement(&$5, 0 CLS_CC); } | newif_condition_statement T_ELSE T_IF '(' expr ')' ':' { do_if_cond(&$5, &$6 CLS_CC); } statement { do_if_after_statement(&$6, 0 CLS_CC); } /* possible (optionnal) acceptable syntaxes without the unnecessary ':' */ | newif_condition_statement T_ELSEIF '(' expr ')' { do_if_cond(&$4, &$5 CLS_CC); } statement { do_if_after_statement(&$5, 0 CLS_CC); } | newif_condition_statement T_ELSE T_IF '(' expr ')' { do_if_cond(&$5, &$6 CLS_CC); } statement { do_if_after_statement(&$6, 0 CLS_CC); } ; statement_but_if: '{' statement_list '}' | '{' '}' /* because now 'statement_list' rule can't be empty */ | T_WHILE '(' { $1.u.opline_num = get_next_op_number(CG(active_op_array)); } expr ')' { do_while_cond(&$4, &$5 CLS_CC); } while_statement { do_while_end(&$1, &$5 CLS_CC); } | T_DO { $1.u.opline_num = get_next_op_number(CG(active_op_array)); do_do_while_begin(CLS_C); } statement T_WHILE '(' expr ')' ';' { do_do_while_end(&$1, &$6 CLS_CC); } | T_FOR '(' for_expr ';' { do_free(&$3 CLS_CC); $4.u.opline_num = get_next_op_number(CG(active_op_array)); } for_expr ';' { do_for_cond(&$6, &$7 CLS_CC); } for_expr ')' { do_free(&$9 CLS_CC); do_for_before_statement(&$4, &$7 CLS_CC); } for_statement { do_for_end(&$7 CLS_CC); } | T_SWITCH '(' expr ')' { do_switch_cond(&$3 CLS_CC); } switch_case_list { do_switch_end(&$6 CLS_CC); } | T_BREAK ';' { do_brk_cont(ZEND_BRK, NULL CLS_CC); } /* | other statements ... */ ; /* and then replace all further reference to 'inner_statement_list' by simply 'statement_list', and add a rule without it because the new 'statement_list' can't be empty... for example, the rule: */ for_statement: statement | ':' inner_statement_list T_ENDFOR ';' ; /* will now become: */ for_statement: statement | ':' statement_list T_ENDFOR ';' | ':' T_ENDFOR ';' ; /* Note that the new forms for IF, WHILE, FOR (with a ':' which introduces a corresponding ENDIF or ENDWHILE or ENDFOR) could be also modified to accept unambiguous forms without the ':', where ENDIF, ENDWHILE and ENDFOR would still be valid. Many will see the ':' as superfluous, while they find the ENDing keyword useful. Additionally a new form of the DO statement may accept a 'statement_list' instead of a single 'statement' before the ending WHILE condition, e.g: "DO: statement1; statement2; WHILE(condition);" With a configurable option, enforced or relaxed by a test in the semantic parser actions, the ':' may also be made superfluous, and the form without it made acceptable. And there could be other styles of loop controls (which are possible with PHP and not in C because Zend language does not have a preprocessor): - "REPEAT" as an synonym for "DO" (a-la Pascal) - "UNTIL(condition) instead of "WHILE(!condition)" - "DO...LOOP;" instead of "DO...WHILE(TRUE);" or "WHILE(TRUE)...ENDWHILE;" - "BREAK IF(condition);" instead of "IF(condition): BREAK; ENDIF;" with the new style for IF, or "IF(condition) BREAK;" with the old style but which is plagged by a possible "ELSE" clause after it. - "CONTINUE IF(condition);" and "GOTO label IF(condition);", using the same idea about the new style for IF... */ ------------ cut here (end 2) -------------