Flex/Bison: связанный список, разделенный запятыми?

У меня есть следующая грамматика для списка, разделенного запятыми, по крайней мере с одним элементом:

column_expression_list:
    column_expression {
        $$ = LinkedList_New();
        LinkedListItem *item = LinkedListItem_New($1);
        LinkedList_add($$, item);
    }
    |
    column_expression_list T_COMMA column_expression {
        LinkedListItem *item = LinkedListItem_New($3);
        LinkedList_add($1, item);
    }
;

Всегда ли column_expression_list в конечном итоге превращается в column_expression, и поэтому каждый элемент связанного списка всегда будет безопасно добавляться в связанный список?

Если нет, то какая правильная грамматика для этого?


c linked-list flex-lexer bison
person Elliot Chance    schedule 06.02.2013    source источник
comment
Это выглядит нормально для меня. Хотя лично я бы использовал правую рекурсию в списке (column_expression T_COMMA column_expression_list).   -  person Some programmer dude    schedule 06.02.2013
comment
@JoachimPileborg ваше предложение приводит к сбою. Есть ли преимущество в производительности при таком подходе?   -  person Elliot Chance    schedule 06.02.2013
comment
Ну, вы должны переключить $1 и $3, конечно. В противном случае единственная разница заключается в том, где будет добавлен узел column_expression, в начале или в конце.   -  person Some programmer dude    schedule 06.02.2013

Ответы (1)


arrow_upward
1
arrow_downward

Ваша грамматика в порядке: нет другого способа построить column_expression_list, кроме первого из ваших двух правил, поскольку второе требует, чтобы одно из них уже было «распознано». Конечно, если у вас есть другие правила в отношении column_expression_list, все может быть по-другому.

Вы правы, предпочитая левую рекурсию правой рекурсии в случае парсеров LR: они экономят место, а в случае интерактивных парсеров ведут себя так, как вы хотите. См. http://www.gnu.org/software/bison/manual/html_node/Recursion.html, например.

person akim    schedule 08.02.2013