Это легко выполнимо с помощью PLY (или любого другого генератора, похожего на yacc), но важно иметь некоторое представление о природе того, что вы пытаетесь проанализировать.
Интуитивно, такая строка продолжения, как* 2 - 3 должен быть проанализирован, как если бы он был записан как <prev> * 2 - 3, где <prev> - нетерминал, который каким-то образом представляет предыдущее значение.
Для простого случая мы могли бы просто определить
expression : '$'
, так что предыдущее значение представлено явным токеном $.Тогда остальная часть грамматики просто сработает.
Конечно, предполагается, что пользователю не нужно вводить $ (хотя, на самом деле, они могут найти его полезным. См. Ниже.)вместо этого нам нужен
expression: prev
, где нетерминал prev должен представлять пустую последовательность токенов.Нет проблем с тем, что нетерминал будет представлен нулевыми входными токенами, но, очевидно, нам нужно ограничить обстоятельства, при которых это может произойти.Поэтому мы не можем просто добавить:
prev :
к грамматике, потому что это приведет к проблеме, с которой вы уже столкнулись: она делает 2**4 действительным, как если бы это было 2*<prev>*4.
Очевидно, мы хотим, чтобы грамматика производила только пустые <prev> в самом начале оператора.Осталось только выяснить, как это сделать.
Давайте предположим, что у нас есть два вида expression: один вид допускает пустую левую часть, а другой нет.Как бы мы определили эти два нетерминала?
Второе - это просто обычное определение:
expression : expression '+' expression
expression : expression '-' expression
expression : expression '*' expression
expression : expression '/' expression
expression : '-' atom # See note below
expression : atom
atom : NUMBER
atom : '(' expression ')'
(я выделил atom постановок по причинам, которые будут рассмотрены ниже).
А как насчет выражений, левый операнд которых может быть неявным?Они очень похожи:
expr_cont : expr_cont '+' expression
expr_cont : expr_cont '-' expression
expr_cont : expr_cont '*' expression
expr_cont : expr_cont '/' expression
expr_cont : atom
Но есть еще один случай:
expr_cont :
В первых четырех постановках мы говорим, что в expr_cont с оператором,правый операнд должен быть обычным expression, но левый операнд может быть выражением с неявным левым операндом.В последнем производстве мы допускаем неявный левый операнд (но только для этого вида выражения).Явные левые операнды - числа и выражения в скобках - одинаковы, поэтому мы можем использовать созданный выше нетерминал atom.
Примечание об унарном минусе: В исходной грамматике унарный минус допускался только в скобках, и его приоритет был неправильным.Первоначальное производство было:
expression: '(' '-' expression ')' %prec UMINUS
В этом производстве объявление приоритета совершенно бессмысленно, потому что само производство никогда не бывает неоднозначным.(Он однозначно окружен круглыми скобками, поэтому его необходимо уменьшить, когда встречаются закрывающие круглые скобки.) Применение унарного минуса в скобках также однозначно, но неверно: производство эффективно указывает, что унарный минус применяется ко всему выражениюзаключены в круглые скобки, так что (-4 - 2) будет иметь значение -2 (- (4-2)), а не ожидаемое -6.
Простое исправление, примененное в приведенной выше грамматике, явно указывает, что операнд в унарномминус atom, а не expression.Следовательно, -4 - 2 должен быть проанализирован как (-4) - 2, поскольку 4 - 2 не может быть atom.Однако это исправление устраняет требование, чтобы выражения, начинающиеся с унарного минуса, были заключены в скобки.
Тот факт, что унарный минус производится только в expression, а не expr_cont, означает, что выражения продолжения начинаются со знака минусбудет проанализирован как таковой, что было предположительно намерением ограничения.
Теперь реализация проста:
precedence = (
('left', '+', '-'),
('left', '*', '/'),
)
# We can use the same function for all unit productions which pass
# through the semantic value of the right-hand symbol.
# (A unit production is one whose right-hand side has a single symbol.)
def p_unit(p):
'''statement : expr_cont
expression : atom
expr_cont : atom
atom : NUMBER
'''
p[0] = p[1]
# Personally, I would write this as four functions, one for each operator,
# rather than executing the chain of if statements every time.
def p_expression_binop(p):
'''expression : expression '+' expression
| expression '-' expression
| expression '*' expression
| expression '/' expression
expr_cont : expr_cont '+' expression
| expr_cont '-' expression
| expr_cont '*' expression
| expr_cont '/' expression
'''
if p[2] == '+':
p[0] = p[1] + p[3]
elif p[2] == '-':
p[0] = p[1] - p[3]
elif p[2] == '*':
p[0] = p[1] * p[3]
elif p[2] == '/':
p[0] = p[1] / p[3]
def p_expression_uminus(p):
'''expresion : '-' atom
'''
p[0] = -p[2]
def p_atom_group(p):
'''atom : '(' expression ')'
'''
p[0] = p[2]
def p_expr_previous(p):
'''expr_cont :
'''
p[0] = r # "previous" would be a better variable name than r
Как упоминалось выше, могут быть случаи, когда пользователю будет удобно иметь явный способ написания "предыдущего значения". Предположим, например, что они хотели увидеть результат <prev>²+1. Или предположим, что они просто хотели переопределить арифметический приоритет по умолчанию для вычисления (<prev> - 3) * 2. И то, и другое можно легко обеспечить, допустив использование, скажем, $ в качестве явного токена «предыдущего значения». После добавления его в список литералов потребуется изменить только последнюю функцию парсера:
def p_expr_previous(p):
'''expr_cont :
| '$'
expression : '$'
'''
p[0] = r # "previous" would still be a better variable name than r