Lemon Parser пропускает вещи (или мое недоразумение)
Обновлено с дополнительной информацией
У меня проблема с анализом простого массива элементов с помощью Lemon.
Может кто-нибудь просветить меня ??
Я пытаюсь проанализировать эту строку «[0 0 612 792] [100 200]» с определением mygrammar, и анализатор всегда пропускает первый элемент массива и дублирует последний … любая идея ??
Файл грамматики
%token_type { char* }
%include {
#include <assert.h>
}
%parse_accept { printf("The parser has completed successfully.\n"); }
%syntax_error { fprintf(stderr, "Syntax Error\n"); }
%parse_failure { fprintf(stderr, "Parse failure\n"); }
%start_symbol program
array_value ::= INT_LITERAL(A). {printf("Av: %s\n", A);}
array_value_list ::=.
array_value_list ::= array_value_list array_value.
array_declaration ::= LBRACKET array_value_list RBRACKET.
array_list ::= array_declaration.
array_list ::= array_list array_declaration.
program ::= array_list END_TOKEN.
Я использую re2c для получения токенов, и код, который вызывает синтаксический анализатор для каждого токена:
while(token = scan(&scanner, buff_end)) {
// Send strings to the parser with NAME tokens
if(token == INT_LITERAL) {
name_length = scanner.cur - scanner.top;
strncpy(name_str, scanner.top, name_length);
name_str[name_length] = '\0';
//printf("Token:Pre: %s\tName: %s\n", tokenStr(token),name_str);
Parse(parser, token, name_str);
}
else {
//printf("Token: %s\n", tokenStr(token));
Parse(parser, token, 0);
}
// Execute Parse for the last time
if(token == END_TOKEN) {
Parse(parser, 0, NULL);
break;
}
}
Для входной строки «[0 -100 612 792] [100 200]» вывод:
Av: -100
Av: 612
Av: 792
Av: 792
Av: 200
Av: 200
Как вы можете заметить, первый элемент не появляется, а последний дублируется.
Грамматика из лимона это:
State 0:
array_declaration ::= * LBRACKET array_value_list RBRACKET
array_list ::= * array_declaration
array_list ::= * array_list array_declaration
program ::= * array_list END_TOKEN
LBRACKET shift 3
array_declaration shift 1 /* because array_declaration==array_list */
array_list shift 1
program accept
State 1:
array_declaration ::= * LBRACKET array_value_list RBRACKET
array_list ::= array_list * array_declaration
program ::= array_list * END_TOKEN
LBRACKET shift 3
END_TOKEN shift 4
array_declaration shift-reduce 5 array_list ::= array_list array_declaration
State 2:
array_value ::= * INT_LITERAL
array_value_list ::= array_value_list * array_value
array_declaration ::= LBRACKET array_value_list * RBRACKET
INT_LITERAL shift-reduce 0 array_value ::= INT_LITERAL
RBRACKET shift-reduce 3 array_declaration ::= LBRACKET array_value_list RBRACKET
array_value shift-reduce 2 array_value_list ::= array_value_list array_value
State 3:
(1) array_value_list ::= *
array_value_list ::= * array_value_list array_value
array_declaration ::= LBRACKET * array_value_list RBRACKET
array_value_list shift 2
{default} reduce 1 array_value_list ::=
State 4:
(6) program ::= array_list END_TOKEN *
$ reduce 6 program ::= array_list END_TOKEN
----------------------------------------------------
Symbols:
0: $:
1: INT_LITERAL
2: LBRACKET
3: RBRACKET
4: END_TOKEN
5: error:
6: array_value: INT_LITERAL
7: array_value_list: <lambda> INT_LITERAL
8: array_declaration: LBRACKET
9: array_list: LBRACKET
10: program: LBRACKET
И выходная трассировка для образца строки:
T__Input 'LBRACKET'
T__Shift 'LBRACKET', go to state 3
T__Return. Stack=[LBRACKET]
T__Input 'INT_LITERAL'
T__Reduce [array_value_list ::=], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'INT_LITERAL'
T__Return. Stack=[LBRACKET array_value_list INT_LITERAL]
T__Input 'INT_LITERAL'
T__Reduce [array_value ::= INT_LITERAL], go to state 2.
T__Shift 'array_value'
T__Reduce [array_value_list ::= array_value_list array_value], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'INT_LITERAL'
T__Return. Stack=[LBRACKET array_value_list INT_LITERAL]
T__Input 'INT_LITERAL'
T__Reduce [array_value ::= INT_LITERAL], go to state 2.
T__Shift 'array_value'
T__Reduce [array_value_list ::= array_value_list array_value], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'INT_LITERAL'
T__Return. Stack=[LBRACKET array_value_list INT_LITERAL]
T__Input 'INT_LITERAL'
T__Reduce [array_value ::= INT_LITERAL], go to state 2.
T__Shift 'array_value'
T__Reduce [array_value_list ::= array_value_list array_value], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'INT_LITERAL'
T__Return. Stack=[LBRACKET array_value_list INT_LITERAL]
T__Input 'RBRACKET'
T__Reduce [array_value ::= INT_LITERAL], go to state 2.
T__Shift 'array_value'
T__Reduce [array_value_list ::= array_value_list array_value], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'RBRACKET'
T__Return. Stack=[LBRACKET array_value_list RBRACKET]
T__Input 'LBRACKET'
T__Reduce [array_declaration ::= LBRACKET array_value_list RBRACKET], go to state 0.
T__Shift 'array_declaration', go to state 1
T__Shift 'LBRACKET', go to state 3
T__Return. Stack=[array_declaration LBRACKET]
T__Input 'INT_LITERAL'
T__Reduce [array_value_list ::=], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'INT_LITERAL'
T__Return. Stack=[array_declaration LBRACKET array_value_list INT_LITERAL]
T__Input 'INT_LITERAL'
T__Reduce [array_value ::= INT_LITERAL], go to state 2.
T__Shift 'array_value'
T__Reduce [array_value_list ::= array_value_list array_value], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'INT_LITERAL'
T__Return. Stack=[array_declaration LBRACKET array_value_list INT_LITERAL]
T__Input 'RBRACKET'
T__Reduce [array_value ::= INT_LITERAL], go to state 2.
T__Shift 'array_value'
T__Reduce [array_value_list ::= array_value_list array_value], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'RBRACKET'
T__Return. Stack=[array_declaration LBRACKET array_value_list RBRACKET]
T__Input 'END_TOKEN'
T__Reduce [array_declaration ::= LBRACKET array_value_list RBRACKET], go to state 1.
T__Shift 'array_declaration'
T__Reduce [array_list ::= array_list array_declaration], go to state 0.
T__Shift 'array_list', go to state 1
T__Shift 'END_TOKEN', go to state 4
T__Return. Stack=[array_list END_TOKEN]
T__Input '$'
T__Reduce [program ::= array_list END_TOKEN], go to state 0.
T__Accept!
T__Return. Stack=]
Я застрял на этой ошибке, и я почти уверен, что это концептуальная ошибка, которую я не понимаю. Любая помощь приветствуется.
Спасибо
Решение
Вы не показываете определение name_str в коде вашего сканера, но кажется вероятным, что это массив char, В этом случае вы рискуете переполнить буфер, поскольку никогда не проверяете, name_length меньше размера буфера; кроме того, вы могли бы также использовать memcpy вместо strncpy потому что вы уже знаете, что в строке, которую вы копируете, нет символа NUL. Но ни одна из этих вещей на самом деле не является проблемой: проблема в том, что вы копируете каждый токен в один и тот же буфер.
То, что вы передаете парсеру адрес строки, заканчивающейся NUL. Парсер не копирует строку; он просто хранит адрес как семантическое значение токена. Другими словами, парсер предполагает, что он владеет переданная строка токена, по крайней мере, пока анализ не завершится.
Но на самом деле символьный буфер (name_str) принадлежит сканеру, и после того, как он вставил токен в анализатор, он предполагает, что он свободен делать то, что он будет делать с символьным буфером. Который должен перезаписать буфер следующим токеном.
В отличие от бизона, лимон не уменьшается сразу же, когда взгляд не имеет значения. бизон уменьшился бы INT_LITERAL в array_value как только он увидел буквальный, потому что сокращение не зависит от прогнозирования. Но у лимона всегда есть жетон предвкушения, поэтому он не уменьшает INT_LITERAL в array_value пока он не получил следующий токен. К сожалению, если следующий токен также INT_LITERALследующий токен будет перезаписывать буфер символов до того, как произойдет сокращение, поэтому действие сокращения выведет строку в следующий маркер. Если следующий токен ], тогда буфер символов не будет перезаписан сканером, поэтому в этом случае будет напечатан текущий токен, хотя он уже был напечатан сокращением предыдущего токена.
Как правило, сканер не может знать, как долго парсер будет требовать значения токена. Для этой проблемной среды существует только две разумные политики владения:
- Сканер сохраняет право собственности. Парсер должен сделать копию, если ему нужно сохранить значение.
- Сканер передает владение парсеру, который должен явно освободить токен, когда это будет сделано с ним.
Первая политика является более чистой, поскольку она не требует двух компонентов для согласования протокола управления ресурсами. Но маловероятно, что генератор синтаксического анализа будет включать какой-либо механизм, который позволил бы реализовать эту политику, поскольку для этого потребовалось бы предпринять некоторые действия в верхней части функции синтаксического анализатора.
Так что вам нужно использовать вторую политику; сканер должен сделать копию строки токена во вновь выделенной памяти и передать эту память вместе с ее владельцем парсеру, чтобы он (в конце концов) освободил копию. Это тот же протокол, который используется большинством функционирующих парсеров бизонов по той же причине, и различные ошибки, которые возникают, когда копия не сделана, являются, вероятно, наиболее распространенными неясными ошибками бизонов.
Конечно, в этом простом случае вы можете избежать проблем с управлением памятью, если сканер преобразует строку в целое число.
Другие решения
Парсер Lemon не может быть сгенерирован из предоставленного вами определения парсера. Это позволяет терминальный элемент array_value рекурсивного списка array_value_list быть пустым. Парсер может уменьшить это правило бесконечное количество раз и сообщает о конфликте при разборе.
Чтобы разрешить конфликт, переключитесь на концепцию правила пустого списка вместо пустого элемента. Вот рекомендуемое определение списка из левой рекурсии из лимон документация:
list ::= .
list ::= list element.
Применение этого шаблона к вашему парсеру дает следующий результат:
array_value ::= INT_LITERAL(A). {printf("Array value: %s\n", A);}
array_value_list ::= .
array_value_list ::= array_value_list array_value.
init_array ::=. {printf("Init Array\n");}
end_array ::=. {printf("End Array\n");}
array_declaration ::= init_array LBRACKET array_value_list RBRACKET end_array.
array_list ::= array_declaration.
array_list ::= array_list array_declaration.
program ::= array_list END_TOKEN.