Неясно, как спецификация производства yacc/bison может вызвать переполнение стека

Question

Это не домашнее задание, но оно из книги. Я дал следующую грамматику:

%{ 
#include <stdio.h> 
#include <ctype.h> 

int yylex(); 
int yyerror(); 
%} 

%% 

command : exp '\n' { printf("%d\n", $1); exit(0); } 
     | error '\n' 
      { 
      yyerrok; 
      printf("reenter expression: "); 
      } 
      command 
     ; 

exp : exp '+' term { $$ = $1 + $3; } 
    | exp '-' term { $$ = $1 - $3; } 
    | term { $$ = $1; } 
    ; 

term : term '*' factor { $$ = $1 * $3; } 
    | factor { $$ = $1; } 
    ; 

factor : NUMBER { $$ = $1; } 
     | '(' exp ')' { $$ = $2; } 
     ; 

%% 

int main() { 
    return yyparse(); 
} 

int yylex() { 
    int c; 

    /* eliminate blanks*/ 
    while((c = getchar()) == ' '); 

    if (isdigit(c)) { 
    ungetc(c, stdin); 
    scanf("%d\n", &yylval); 
    return (NUMBER); 
    } 

    /* makes the parse stop */ 
    if (c == '\n') return 0; 

    return (c); 
} 

int yyerror(char * s) { 
    fprintf(stderr, "%s\n", s); 
    return 0; 
} /* allows for printing of an error message */ 

Вот задача:

The simple error recovery technique suggested for the calculator program is flawed in that it could cause stack overflow after many errors. Rewrite it to remove this problem.

Я не могу понять, как может произойти переполнение стека. Учитывая, что начальное производство является единственным, у которого есть токен ошибки, не будет ли yacc/bison всплывать все элементы в стеке и до перезапуска?

Answer 1

Если у вас есть сомнения, самое простое - использовать зубров.

Я немного изменил программу, чтобы избежать ошибок. Во-первых, поскольку новая программа опирается на токены '\n', я удалил строку if (c == '\n') return 0;, которая подавила бы отправку '\n'. Во-вторых, я исправил scanf("%d\n", &yylval); до scanf("%d", &yylval);. Нет причин проглатывать пробелы после номера, особенно, если пробел, следующий за номером, является символом новой строки. (Тем не менее, scanf модели не различают различные виды пробелов, поэтому шаблон "%d\n" имеет точно такую ​​же семантику, как "%d ". Ни один из тех, кто будет правильным.)

Затем я добавил строку yydebug = 1; в верхней части main и поставил опцию -t («трассировка») для бизона, когда я построил калькулятор. Это заставляет парсер показывать свой прогресс в деталях, поскольку он обрабатывает входные данные.

Это помогает получить таблицу состояний таблицы, чтобы увидеть, что происходит. Вы можете сделать это с помощью опции bison -v. Однако я оставлю это для читателей.

Затем я запустил программу и намеренно набран ошибку синтаксиса:

./error 
Starting parse 
Entering state 0 
Reading a token: 2++3 

Трассировщик имеет уже два выходных линий, но после того, как я даю ему некоторый входной сигнал, след идет изливая.

Во-первых, анализатор поглощает НОМЕР 2 и оператор +: (Примечание:. nterm ниже способом зубра сказать «не-терминал», в то время как token является «терминал»; стек показывает только государственные номера)

Next token is token NUMBER() 
Shifting token NUMBER() 
Entering state 2 
Reducing stack by rule 9 (line 25): 
    $1 = token NUMBER() 
-> $$ = nterm factor() 
Stack now 0 
Entering state 7 
Reducing stack by rule 8 (line 22): 
    $1 = nterm factor() 
-> $$ = nterm term() 
Stack now 0 
Entering state 6 
Reading a token: Next token is token '+'() 
Reducing stack by rule 6 (line 18): 
    $1 = nterm term() 
-> $$ = nterm exp() 
Stack now 0 
Entering state 5 
Next token is token '+'() 
Shifting token '+'() 
Entering state 12 

Пока что так хорошо. Состояние 12 - это то место, где мы добираемся после того, как увидели +; вот его определение:.

State 12 

    4 exp: exp '+' . term 
    7 term: . term '*' factor 
    8  | . factor 
    9 factor: . NUMBER 
    10  | . '(' exp ')' 

    NUMBER shift, and go to state 2 
    '('  shift, and go to state 3 

    term go to state 17 
    factor go to state 7 

(По умолчанию бизон не загромождать таблицу состояний с неосновными элементами я добавил -r itemset, чтобы получить полную НИКАКИЕ гарантии, но это было бы достаточно легко сделать закрытие вручную.)

Поскольку в этом состоянии мы ищем правый операнд +, действительны только те, которые могут начать выражение: NUMBER и (.Но это не то, что мы имеем:

Reading a token: Next token is token '+'() 
syntax error 

ОК, мы в штате 12, и если вы посмотрите на приведенном выше описании состояния, вы увидите, что error не в упреждающей выборке установлен либо. Итак:

Error: popping token '+'() 
Stack now 0 5 

Это ставит нас в штате 5, который является, где оператор Ожидалось:

State 5 

    1 command: exp . '\n' 
    4 exp: exp . '+' term 
    5 | exp . '-' term 

    '\n' shift, and go to state 11 
    '+' shift, and go to state 12 
    '-' shift, and go to state 13 

Так что государство не имеет переход на error либо. Onwards.

Error: popping nterm exp() 
Stack now 0 

ОК, назад к началу. Государство 0 делает имеют error переход:

error shift, and go to state 1 

Итак, теперь мы можем переложить error маркер и введите состояние 1, как указано в таблице переходов:

Shifting token error() 
Entering state 1 

Теперь нам нужно синхронизировать ввод, пропуская входные токены, пока мы не перейдем к токену новой строки. (Обратите внимание, что зубр на самом деле появляется и толкает маркер ошибки в то время как он это делает. Постарайтесь не допустить, что отвлекает вас.)

Next token is token '+'() 
Error: discarding token '+'() 
Error: popping token error() 
Stack now 0 
Shifting token error() 
Entering state 1 
Reading a token: Next token is token NUMBER() 
Error: discarding token NUMBER() 
Error: popping token error() 
Stack now 0 
Shifting token error() 
Entering state 1 
Reading a token: Next token is token '\n'() 
Shifting token '\n'() 
Entering state 8 

Правильно, мы обнаружили символ новой строки. Состояние 5 - command: error '\n' . $@1 command. $@1 - это название маркера (пустая постановка), в которое бизон вставлен вместо действия среднего правила (MRA). Состояние 8 уменьшит этот маркер, заставив MRA запустить, что потребует большего ввода. Обратите внимание, что на этом этапе восстановление ошибок завершено. Сейчас мы находимся в совершенно нормальном состоянии, а стек отражает тот факт, что у нас есть, для того, начало (состояние 0), в error маркер (состояние 1) и новой строки маркер (состояние 8):

Reducing stack by rule 2 (line 13): 
-> $$ = nterm $@1() 
Stack now 0 1 8 
Entering state 15 
Reading a token: Try again: 

После MRA уменьшается, то соответствующее действие от государства 8 берется и мы переходим к государству 15 (чтобы избежать путаницы, я вышел из неосновных элементов):

State 15 

    3 command: error '\n' $@1 . command 

    error shift, and go to state 1 
    NUMBER shift, and go to state 2 
    '('  shift, and go to state 3 

Итак, теперь мы готовы для анализа новой команды, как и ожидалось. Но мы еще не сократили производство ошибок; он все еще находится в стеке, потому что его нельзя уменьшить до тех пор, пока не уменьшится command после точки. И мы еще не начали на нем.

Но важно отметить, что государство 15 имеет, имеет переход на error, как вы можете видеть из таблицы состояний страны. Он имеет этот переход, поскольку закрытие включает в себя две постановки для command:

1 command: . exp '\n' 
    3  | . error '\n' $@1 command 

, а также для постановки exp, term и factor, которые также являются частью крышки.

Итак, что произойдет, если мы введем еще одну ошибку?Стек будет возвращен к этой точке (0 1 8 15), новый токен error будет вставлен в стек (0 1 8 15 1), маркеры будут отброшены до тех пор, пока новая линия не будет сдвинута (0 1 8 15 1 8) и новая MRA ($@1, как звонки зубров он) будет уменьшен в стек (0 1 8 15 1 8 15), и в этот момент мы готовы начать разбор еще одной попытки.

Надеюсь, вы увидите, где это происходит.

Обратите внимание, что это действительно не отличается от эффекта любого другого праворекурсивного производства. Если бы грамматика попыталась принять ряд выражений:

prog: exp '\n' 
    | exp '\n' { printf("%d\n", $1); } prog 

вы увидите ту же стек накапливанию, поэтому правая рекурсия не рекомендуются. (А также потому, что вы в конечном итоге вставки СВП, чтобы не видеть результаты в обратном порядке, как стек снижается до prog в конце всех входных данных.)

command go to state 20 
    exp  go to state 5 
    term  go to state 6 
    factor go to state 7