FAQ
Edit report at http://pear.php.net/bugs/bug.php?id=18263&edit=1

ID: 18263
Comment by: wkampmann@gmail.com
Reported By: wkampmann at gmail dot com
Summary: Infinite loop on syntax error when using recursive
grammar rules
Status: Open
Type: Bug
Package: PHP_ParserGenerator
Package Version: 0.1.7
PHP Version: Irrelevant
Roadmap Versions:
New Comment:

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.


Previous Comments:
------------------------------------------------------------------------

[2011-02-11 13:40:05] wkampmann

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.

------------------------------------------------------------------------

Search Discussions

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
grouppear-bugs @
categoriesphp
postedFeb 11, '11 at 1:01p
activeFeb 11, '11 at 1:01p
posts1
users1
websitepear.php.net

1 user in discussion

Wkampmann: 1 post

People

Translate

site design / logo © 2022 Grokbase