Приоритет операторов в грамматике БНФ

Я делаю домашнее задание, где я даю некоторую грамматику BNF:

<assign> -> <id> = <expr>
<id> -> A | B | C
<expr> -> <expr> + <term>
      | <term>
<term> -> <term> * <factor>
      | <factor>
<factor> -> ( <expr> )
      | <id>

и вопрос:

«Перепишите эту грамматику так, чтобы оператор + был правоассоциативным и имел приоритет над оператором *».

Одноклассник предложил просто поменять местами операторы + и *, и тогда + будет иметь приоритет и получит правильную ассоциацию, однако я не думаю, что это правильно, поскольку вопрос рекурсивный.

Мой вопрос: получает ли оператор + приоритет и правильную ассоциацию, просто переключая его с оператором *? У меня две мысли: удалить рекурсию и сделать то, что предлагает мой одноклассник, или поставить оператор + в состояние, при котором он должен быть окружен ( и ) для работы.

Может быть, я слишком много думаю об этом?


syntax operator-precedence bnf
person Ryan Tibbetts    schedule 18.02.2015    source источник
comment
замена + и * в грамматике явно поменяет приоритет, но сделать их правоассоциативными — это отдельный шаг   -  person Mooing Duck    schedule 18.02.2015
comment
@MooningDuck Позвольте мне просто сфотографировать это, чтобы я мог сказать, что сказал вам об этом моему другу ... Хорошо, сделано. Итак, теперь, ссылаясь на правую ассоциацию, смогу ли я просто сделать оператор сложения рекурсивно в скобках и вырезать умножение в этой точке? Я считаю, что это было бы правильным объединением. Бывший. A = B * (C + (C + (C + C)))   -  person Ryan Tibbetts    schedule 18.02.2015
comment
Ассоциативность (мне кажется) связана с видом рекурсии. Как вы можете видеть в вашем примере, и expr, и term являются леворекурсивными и имеют левоассоциативность. Возможно, изменение типа рекурсии, используемого в интересующем вас производстве, также меняет его ассоциативность.   -  person Branco Medeiros    schedule 19.02.2015

Ответы (1)


arrow_upward
2
arrow_downward

Поменяв местами + и * в грамматике, вы явно поменяете приоритет, но сделать их правоассоциативными — это отдельный шаг, так что это несложно.

Однако для ассоциативности «Право против левого» мне трудно понять ваши предложения, но оба они кажутся неверными.

Если мы возьмем пример ввода A = A + B + C, то ваша грамматика разберет его следующим образом:

assign: <id> = <expr>
    id: A
    expr: <expr> + <term>
        expr: <expr> + <term>
            expr: <expr> + <term>
                expr: <term>
                term: <factor>
                    factor: <id>
                         id: A
            term: <factor>
                factor: <id>
                    id: B
        term: <factor>
            factor: <id>
                id: C

Или, если вы предпочитаете то же самое в скобках:

(A) = ((((A))+(B))+(C))

Обратите внимание, что самый внутренний и, таким образом, первый оцениваемый + является самым дальним слева. Таким образом, ваша грамматика имеет левую ассоциативность. Вам нужно изменить expr и term так, чтобы первым оцениваемым был самый дальний справа, чтобы грамматика имела правильную ассоциативность. Круглые скобки обеспечивают способ «отменить» любую ассоциативность, которую имеет грамматика, но в остальном они на самом деле не связаны с ассоциативностью.

person Mooing Duck    schedule 18.02.2015