Правило грамматики для математических выражений (без левой рекурсии)

Я пытаюсь выяснить правила грамматики для любого математического выражения.

Я использую EBNF (статья вики, ссылка на которую приведена ниже) для получения правил синтаксиса.

Мне удалось придумать одно, которое какое-то время работало, но правило грамматики не работает с onScreenTime + (((count) - 1) * 0.9).

Правило следующее:

math ::= MINUS? LPAREN math RPAREN
       | mathOperand (mathRhs)+

mathRhs ::= mathOperator mathRhsGroup
          | mathOperator mathOperand mathRhs?

mathRhsGroup ::= MINUS? LPAREN mathOperand (mathRhs | (mathOperator mathOperand))+ RPAREN

Вы можете с уверенностью предположить, что mathOperand являются положительными или отрицательными числами или переменными. Вы также можете предположить, что mathOperator обозначает любой математический оператор, такой как + или -.

Кроме того, LPAREN и RPAREN — это '(' и ')' соответственно.

EBNF: https://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form

РЕДАКТИРОВАТЬ Забыл упомянуть, что это не удается (count) - 1. Он говорит, что ожидается RPAREN вместо - 1.

РЕДАКТИРОВАТЬ 2 Мой пересмотренный EBNF теперь выглядит так:

number ::= NUMBER_LITERAL //positive integer

mathExp ::= term_ ((PLUS | MINUS) term_)* // * is zero-or-more.

private term_ ::= factor_ ((ASTERISK | FSLASH) factor_)*

private factor_ ::= PLUS factor_
                  | MINUS factor_
                  | primary_

private primary_ ::= number
                   | IDENTIFIER
                   | LPAREN mathExp RPAREN

syntax expression ebnf grammar
person Kayler Renslow    schedule 05.01.2016    source источник

Ответы (2)


arrow_upward
4
arrow_downward

Взгляните на грамматику выражений любого языка программирования:

expression
    : term
    | expression '+' term
    | expression '-' term
    ;

term
    : factor
    | term '*' factor
    | term '/' factor
    | term '%' factor
    ;

factor
    : primary
    | '-' factor
    | '+' factor
    ;

primary
    : IDENTIFIER
    | INTEGER
    | FLOATING_POINT_LITERAL
    | '(' expression ')'
    ;

Возведение в степень слева в качестве упражнения для читателя: обратите внимание, что оператор возведения в степень является правоассоциативным. Это в нотации yacc. NB. Вы используете EBNF, а не BNF.

EDIT Моя нелеворекурсивная EBNF не так сильна, как моя yacc, но чтобы исключить левые рекурсии, вам нужна схема, например:

expression
    ::= term ((PLUS|MINUS) term)*
term
    ::= factor ((FSLASH|ASTERISK) factor)*

и т. д., где * означает «ноль или более». Мои комментарии по этому поводу ниже в основном неверны и должны быть проигнорированы.

person user207421    schedule 05.01.2016
comment
Это великолепно, и я вижу, как это работает, но, к сожалению, мой генератор не поддерживает левую рекурсию. Как я могу изменить это так, чтобы не было левой рекурсии? - person Kayler Renslow; 05.01.2016
comment
Просто измените его на expression: term '+' term и т. д. - person user207421; 05.01.2016
comment
Однако это не позволяет использовать все выражения. Например, 2 * (3 * 3) + 1 + 1 не работает. - person Kayler Renslow; 05.01.2016
comment
Не получается как? Как вы реализуете эту грамматику? - person user207421; 06.01.2016
comment
Я делаю собственный языковой плагин для Intellij IDE. По сути, я набираю грамматику и нажимаю кнопку, чтобы сгенерировать код синтаксического анализатора. Затем код синтаксического анализатора создает AST. Парсер сообщает мне, где он ожидает определенные токены, как компилятор Java. - person Kayler Renslow; 06.01.2016
comment
Ну, вам придется предоставить больше информации, чем это. Для начала вам придется показать мне, как выглядит ваш EBNF. Вы сами видите, что это правильная грамматика: вы найдете ее в языковых спецификациях для Algol, Pascal, C, C++, Java и кто знает где еще. Я использовал его много раз. Вы можете попробовать сделать его правильным-рекурсивным, если не возражаете против неправильной ассоциативности. - person user207421; 06.01.2016
comment
number ::= (MINUS)? NUMBER_LITERAL неправильно для начала. Приведенная выше грамматика уже обрабатывает унарный минус и плюс. Просто сделай так, как я. Не размещайте материалы, относящиеся к вашему вопросу, на внешних веб-сайтах. - person user207421; 06.01.2016
comment
К сожалению, все предложенные вами способы не работают. В моей грамматике не допускается левая рекурсия, поэтому ваш первый ответ не работает. Я заменил части, где была левая рекурсия, на то, что вы предложили, и это не сработало на 100% (например, 1 + 1 + 1 не работает), поэтому ваше второе предложение не работает. Мне нужно правило выражения нелевой рекурсии. Может, стоит перенести обсуждение в чат? - person Kayler Renslow; 06.01.2016
comment
К сожалению, вы изобрели number правило, которое я вам не дал, и в результате оно не работает. Попробуйте мой способ. - person user207421; 06.01.2016
comment
Я использую number::= NUMBER_LITERAL NUMBER_LITERAL — строго положительные целые числа. 1+1+1 по-прежнему не работает. На втором + он говорит, что ожидает '*', '/' или ';' - person Kayler Renslow; 06.01.2016
comment
Вам нужны правила повторения, чтобы заменить отсутствующие рекурсии, например. expression ::= term (PLUS term)+. - person user207421; 06.01.2016
comment
Я добавил правила повторения, и вы можете увидеть, что у меня есть в моем вопросе, в разделе EDIT 2. 1 + 1 + 1 теперь проходит, а 1 * 1/1 + 2 — нет (ожидается '*','-','+',';' на '/'). Выполнение (PLUS factor_)+ вместо PLUS factor_ вместе с минусом не дало никакого эффекта. - person Kayler Renslow; 06.01.2016
comment
Edit работает для каждого выражения, которое я ему добавляю. Но по какой-то причине я могу сделать 1+++++++++++1 или 1++1 или 1------1. Я обновил исправленное редактирование в своем вопросе. - person Kayler Renslow; 07.01.2016
comment
Причина в том, что это совершенно законно математически. Если 1 допустимо, то допустимо и +1, а значит, допустимо и ++1. Если вы не хотите разрешать это, измените правило factor соответствующим образом. - person user207421; 07.01.2016

arrow_upward
0
arrow_downward

Вы можете взглянуть на грамматику выражений языков, которые обычно реализуются с помощью синтаксических анализаторов рекурсивного спуска, для которых необходимы грамматики LL (1), не допускающие левой рекурсии. Большинство, если не все языки Вирта попадают в эту группу. Ниже приведен пример из грамматики классической Модулы-2. Ссылки EBNF показаны рядом с каждым правилом.

http://modula-2.info/m2pim/pmwiki.php/SyntaxDiagrams/PIM4NonTerminals#expression

person trijezdci    schedule 09.01.2016