| 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) | ||
[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.