Как бороться с унарным минусом и возведением в степень в парсере выражений - PullRequest
Новая
       17

Как бороться с унарным минусом и возведением в степень в парсере выражений

0 голосов
/ 04 декабря 2018

Я знаю, что возведение в степень имеет более высокий приоритет, чем унарный минус.Однако, если я создаю синтаксический анализатор выражений, основанный на этом, я все еще не могу разобрать выражения как 2-3.Чтобы разобраться с этим, я обнаружил, что мне также нужно добавить унарную обработку минусов к правилу производства факторов, которое на один приоритет выше, чем возведение в степень.Это то, как обычно обрабатываются унарный минус и возведение в степень?Я не нашел ничего в Интернете или в книгах, которые говорят об этой конкретной ситуации.Мне было интересно, помогают ли вам возведение в степень и унарные операторы с равным приоритетом?

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

factor        = '(' expression ')' | variable | number | '-' factor
power         = factor { '^' factor } 
unaryTerm     = ['-' | '+'] power
term          = unaryTerm { factorOp unaryTerm }
expression    = term { termOp term }

 termOp        = '+' | '-'
 factorOp      = '*' | '/'

1 Ответ

0 голосов
/ 04 декабря 2018

Если у вас нет необычных требований, то и унарный минус, и возведение в степень в одном и том же нетерминале будут работать нормально, потому что возведение в степень является ассоциативным справа: (синтаксис Yacc / bison) 

atom: ID
    | '(' expr ')'
factor
    : atom
    | '-' factor
    | atom '^' factor
term: factor
    | term '*' factor
expr: term
    | expr '+' term
    | expr '-' term

Действительно, возведение в степеньдля того, чтобы этот синтаксис был значимым, фактически требуется быть ассоциативным по праву.Рассмотрим альтернативу с левоассоциативным оператором.

Допустим, у нас есть два оператора, ⊕ и ≀, причем left остается ассоциативным и связывает более тесно, чем ≀, так что ≀ a ⊕ b равно ≀(a ⊕ b).

Поскольку left остается ассоциативным, мы ожидаем, что a ⊕ b ⊕ c будет проанализирован как (a ⊕ b) ⊕ c.Но тогда мы получаем странность.a ⊕ ≀ b ⊕ c совпадает с (a ⊕ ≀b) ⊕ c) или a ⊕ ≀(b ⊕ c))?Оба варианта, кажется, нарушают простые шаблоны.[Примечание 1]

Конечно, однозначная грамматика могла бы быть написана для каждого случая, но какой из них был бы менее удивительным для программиста, который просто шел по таблице приоритетов?Наиболее вероятным результатом было бы требование стиля, что выражения всегда должны быть заключены в круглые скобки, даже если круглые скобки являются избыточными.(Руководства по стилю C полны таких рекомендаций, и многие компиляторы будут упрекать вас за использование правильных, но «не интуитивных» выражений.)

Примечания:

  1. Если вы используете приоритетдекларации, вы получите a ⊕ ≀(b ⊕ c)), что может быть или не быть интуитивным, в зависимости от вашей интуиции.
...