Разбор с круглыми скобками и различными типами выражений

Question

Я сейчас пользуюсь happy для синтаксического анализа языка, но я не думаю, что синтаксический анализатор уместен, за исключением того, что я говорю, что это анализатор LALR. Вот небольшой отрывок из грамматики:

ArithExpr -> ArithExpr + ArithExpr
ArithExpr -> ( ArithExpr )
ArithExpr -> ...

BoolExpr -> ArithExpr == ArithExpr
BoolExpr -> ( BoolExpr )
BoolExpr -> ...

Проблема в том, что я получаю конфликты "уменьшай-уменьшай". Я думаю, что проблема возникает, когда я пытаюсь разобрать что-то вроде следующего:

( ( 2 + 3 ) == ( 4 + 5 ) ) 

Есть только один способ разобрать это выражение, но проблема в том, что, я думаю, даже при первых скобках у парсера возникнут некоторые проблемы. Я думаю, что причина в том, что парсер не знает, сталкивается ли он с ArithExpr или BoolExpr в будущем, и поскольку у него есть только один знак внимания, он должен сделать произвольный выбор, который может быть неправильным.

Есть ли способ переписать грамматику, чтобы принять этот язык? Или я должен просто разбирать оба ArithExpr а также BoolExpr как одна униформа Expr и иметь дело с реальными типами во время проверки типов?

Answer 1

Вы должны просто разобрать Expr и делать проверку типов во время семантического анализа. В противном случае вам действительно будет трудно иметь дело с выражениями в скобках (вы не можете сказать, к какому типу они относятся, пока не слишком поздно) или с логическими значениями первого класса (переменная может иметь логическое значение, нет?).

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