Бизон: конкретное количество рекурсий?

Question

Я пишу парсер с flex и bison уже несколько недель и остановился из-за двойной рекурсии, определения которой схожи для первых нескольких правил. Бизон всегда выбирает неправильный путь на одном конкретном этапе и падает, потому что грамматика не подходит. Код бизона выглядит примерно так:

set : 
TOKEN_    /* token */
QString
QString
Integer  /* number of descrs (see below) */
M_op     /*'M' optional*/
alts;

а также

alts  :
alt | alts alt ;

alt   :
QString
pName_op   /* empty | TOKEN1 QString */
deVal_op    /* empty | TOKEN2 Integer */
descrs
;

а также

descrs  :   
descr | descrs descr ;
descr :
QString
QString_op   /* optional qstring */
Integer
D_op         /* optional 'D' */

Бизон остается в descrs рекурсия и никогда не выходит из нее, чтобы перейти к следующему alt, Однако целое число, которое читается в начальном блоке, говорит нам, сколько экземпляров descr собираются приехать. Итак, мой вопрос заключается в следующем:

Есть ли способ подготовить бизона для определенного числа случаев рекурсии, чтобы он мог выйти из этой рекурсии и войти в рекурсию "выше"? Я могу получить доступ к этому целому числу в коде C, но я не знаю синтаксис для указанного перемещения, что-то вроде descrs : {for (int i=0;i<n;++i){descr}} (Я знаю, что, вероятно, выглядит смешно)

В противном случае, есть ли другой способ обойти эту проблему?

Любой вклад будет высоко ценится. Заранее спасибо.

Answer 1

Не зависящая от контекста грамматика не может зависеть от семантической информации. Тем не менее, это именно то, что вы ищете: вы хотите, чтобы значение числового токена учитывалось в синтаксисе выражения.

Как запрос, это не является неразумным или аморальным; это просто вне досягаемости контекстно-свободных грамматик. А также bison предназначен для создания парсеров для контекстно-свободных грамматик. Так что это просто не правильный инструмент для этой проблемы.

Сказав это, можно использовать зубров таким образом, если вы используете достаточно свежую версию bison который включает в себя поддержку грамматик GLR. Поддержка GLR в Bison включает возможность использования семантических предикатов для управления анализом. (Подробности см. В руководстве для зубров.) Решение, основанное на этом механизме, возможно и, вероятно, не слишком сложно.

Гораздо проще - если грамматика позволяет это сделать - использовать синтаксический анализатор сверху вниз. Разбор числа, а затем это число descr Например, в парсере с рекурсивным спуском s будет тривиальным.

Либеральное использование FOO_op нетерминалы в грамматике предполагают, что синтаксический анализ сверху вниз не будет проблематичным, но невозможно сказать наверняка, не видя всей грамматики. Искусственные нетерминалы (например, FOO_op) часто вызывают конфликты смещения-уменьшения в языках LR(1), потому что они заставляют принять немедленное решение смещения / уменьшения. На языке LR(1) выдается форма: A → ω B? χ будет обычно отображаться как пара производств A → ω B χ; A → ω χ, а не замена Bop → B | ε; A → ω Bop χ, чтобы избежать создания конфликтов с другими произведениями формы C → ω ζ где FIRST(ζ) ∩ FIRST(B ∪ ω) ≠ ∅,