Package home | Report new bug | New search | Development Roadmap Status: Open | Feedback | All | Closed Since Version 0.1.7

Bug #18263 Infinite loop on syntax error when using recursive grammar rules
Submitted: 2011-02-11 18:40 UTC
From: wkampmann Assigned:
Status: Open Package: PHP_ParserGenerator (version 0.1.7)
PHP Version: Irrelevant OS:
Roadmaps: (Not assigned)    
Subscription  


 [2011-02-11 18:40 UTC] wkampmann (Wouter Kampmann)
Description: ------------ When using recursive grammar rules like the expression rules in the provided grammar excerpt, the generated parser enters an infinite loop if a syntax error is made within the recursive elements. This is due to the functions yy_is_expected_token and yy_get_expected_tokens as shown in code excerpts (1) and (2). Test script: --------------- ========= GRAMMAR EXCERPT ========= expr(A) ::= LPAREN expr_0(B) RPAREN. expr(A) ::= expr_0(B). expr_0(A) ::= expr_1(B) AND expr_1(C). expr_0(A) ::= expr_1(B) OR expr_1(C). expr_0(A) ::= expr_1(B). expr_1(A) ::= expr_2(B) LESS_THAN_EQ expr_2(C). expr_1(A) ::= expr_2(B) GREATER_THAN_EQ expr_2(C). expr_1(A) ::= expr_2(B) LESS_THAN expr_2(C). expr_1(A) ::= expr_2(B) GREATER_THAN expr_2(C). expr_1(A) ::= expr_2(B) EQ expr_2(C). expr_1(A) ::= expr_2(B). expr_2(A) ::= expr_3(B) PLUS expr_3(C). expr_2(A) ::= expr_3(B) MINUS expr_3(C). expr_2(A) ::= expr_3(B). expr_3(A) ::= expr_4(B) MUL expr_4(C). expr_3(A) ::= expr_4(B) DIV expr_4(C). expr_3(A) ::= expr_4(B). expr_4(A) ::= NOT expr_5(B). expr_4(A) ::= MINUS expr_5(B). expr_4(A) ::= PLUS expr_5(B). expr_4(A) ::= expr_5(B). expr_5(A) ::= variable(B). expr_5(A) ::= expr(B). // << RECURSION ========= GENERATED PARSER CODE (1) ========= function yy_get_expected_tokens (..) { [...] do { $yyact = $this->yy_find_shift_action($token); if ($yyact >= self::YYNSTATE && $yyact < self::YYNSTATE + self::YYNRULE) { // reduce action $done = 0; // <<<< RESETS $done, SHOULD BE OUTSIDE OUTER DO LOOP do { if ($done++ == 100) { // <<<< NEVER REACHES 100 AS A RESULT $this->yyidx = $yyidx; $this->yystack = $stack; // too much recursion prevents proper detection // so give up return array_unique($expected); } [...] if ($nextstate < self::YYNSTATE) { // we need to shift a non-terminal $this->yyidx++; $x = new MQLParseryyStackEntry; $x->stateno = $nextstate; $x->major = self::$yyRuleInfo[$yyruleno]['lhs']; $this->yystack[$this->yyidx] = $x; continue 2; // <<<< JUMPS TO OUTER DO LOOP } [...] } [...] } [...] } ========= GENERATED PARSER CODE (2) ========= function yy_is_expected_token($token) { [...] do { $yyact = $this->yy_find_shift_action($token); if ($yyact >= self::YYNSTATE && $yyact < self::YYNSTATE + self::YYNRULE) { // reduce action $done = 0; // <<<< RESETS $done, SHOULD BE OUTSIDE OUTER DO LOOP do { if ($done++ == 100) { // <<<< NEVER REACHES 100 AS A RESULT $this->yyidx = $yyidx; $this->yystack = $stack; // too much recursion prevents proper detection // so give up return true; // <<<< SHOULD RETURN FALSE } [...] if ($nextstate < self::YYNSTATE) { // we need to shift a non-terminal $this->yyidx++; $x = new MQLParseryyStackEntry; $x->stateno = $nextstate; $x->major = self::$yyRuleInfo[$yyruleno]['lhs']; $this->yystack[$this->yyidx] = $x; continue 2; // <<<< JUMPS TO OUTER DO LOOP } } while (true); } break; } while (true); $this->yyidx = $yyidx; $this->yystack = $stack; return true; } Expected result: ---------------- The parser should report a syntax error. Actual result: -------------- Infinite loop.

Comments

 [2011-02-11 19:04 UTC] wkampmann (Wouter Kampmann)
This bug can be easily fixed by placing $done = 0; outside the outer do loops and making yy_is_expected_token return false (see generated code excerpts). The file that needs editing is Lempar.php.