Бизон: конкретное количество рекурсий?
Я пишу парсер с 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}}
(Я знаю, что, вероятно, выглядит смешно)
В противном случае, есть ли другой способ обойти эту проблему?
Любой вклад будет высоко ценится. Заранее спасибо.
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 ∪ ω) ≠ ∅
,