В вашей программе отсутствует одна вещь:
precedence = (
('left', 'DIVIDE'),
)
Без этого Ply генерирует конфликт сдвига-уменьшения при генерации синтаксического анализатора из-за производства
expression : expression DIVIDE expression
I отметим, что только потому, что рассматриваемая проблема имеет приоритет оператора, хотя рассматриваемый оператор невидим: неявный оператор умножения, воплощенный в производстве:
expression : NUMBER IMAGINE
Второе производство не вызывает никаких конфликтов синтаксического анализа даже без объявления приоритета, но это потому, что он не является достаточно общим для фактического анализа полезных выражений. Рассмотрим, к примеру, ваш пример
42i/4i
Как вы говорите, ваш синтаксический анализатор интерпретирует это как
[expression: [expression: 42 i]
/
[expression: 4 i] ]
Но вы хотите, чтобы это интерпретировалось как:
[expression: [expression: [expression: 42 i]
/
[expression: 4]
i]
]
Но очевидно, что самый внешний expression не может быть сгенерирован из вашей грамматики, потому что ваша грамматика требует, чтобы левый оператор неявного умножения был NUMBER, и в этом анализе он явно равен expression.
Прежде чем просто добавить производство
expression : expression IMAGINE
, нам, вероятно, следует попытаться представить все возможные варианты использования. И один из них должен сразу же прийти на ум: 4i<sup>2</sup> (опуская детали того, какой оператор вы выбрали для возведения в степень).
Неправильная грамматика "слитно-числовое" будет рассматривать это как квадрат 4i (т.е. -16), но общепринятый синтаксический анализ в четыре раза больше квадрата i (т.е. -4). Это соответствовало бы синтаксическому анализу
[expression: [expression: 4]
[expression: [expression: i]
POWER
[expression: 2]]]
, в котором правый аргумент неявного умножения - не воображаемое, а выражение.
Итак, ваша первая задача - решить, каким будет общее неявное умножение в вашем языке. Все ли следующие действительны? (Некоторые требуют, чтобы ваш лексер сбрасывал пробелы)
4i
i4
(4*5)i
4(7+i)
(4+i)(7-i)
i i
4 i
4 7
Возможно, вы подозреваете пару последних, но я рискну предположить, что большинство из них не вызовет никакого удивления. Позже мы можем посмотреть, как отклонить регистр двух последовательных чисел, если это необходимо, но кажется, что наиболее разумное правило неявного умножения, по крайней мере, похоже на самое общее:
expression : expression expression
и, более того, что он имеет тот же приоритет и ассоциативность, что и деление или явное умножение.
Но это оставляет нас с проблемой: как вы можете поместить оператор в таблицу приоритетов, когда нет оператора? И короткий ответ, вы не можете. Есть несколько трюков, которые более или менее работают, но далеко и далеко простейшим и наиболее читаемым альтернатива написать грамматику так, что приоритет является явным.
1046 * Я не буду go в этот стиль больше, потому что он был забит до смерти в другом месте, и у вас не будет проблем с поиском примеров по всему inte rnet (большинство из которых используют нетерминалы с именами
term и
factor, которые я здесь не использую, потому что я думаю, что их значения достаточно неясны, что многие люди возвращают их назад). Я просто напишу грамматику в стиле PLY с функциями действий.
И еще одно замечание о функциях действий: Ply позволяет комбинировать два производства с одним и тем же действием. Это удобно, но это не значит, что вы должны делать что-то вроде этого:
def p_additive(p):
""" additive : additive '+' multiplicative
additive : additive '-' multiplicative
multiplicative : multiplicative '*' value
multiplicative : multiplicative '/' value
...
"""
if p[2] == '+' then:
p[0] = p[1] + p[3]
else if p[2] == '-' then:
p[0] = p[1] - p[3]}
else if p[2] == '*' then:
p[0] = p[1] * p[3]}
else if p[2] == '/' then:
p[0] = p[1] / p[3]}
Чтобы увидеть, насколько это глупо, рассмотрим процесс, благодаря которому парсер туда попал. Во-первых, синтаксический анализатор выяснил, какая продукция была подобрана. Предположим, что производство было expression : additive '-' multiplicative. Затем он просматривает соответствие между продукцией и функциями и находит вышеуказанную функцию (которая является точно той же самой функцией, которую он нашел бы, если бы в производстве использовался любой другой бинарный оператор). Таким образом, она вызывает эту функцию, и в этот момент информация о том, какое производство соответствует, фактически была потеряна.
Это означает, что первое, что должна сделать функция, это выяснить, какое производство было сокращено, что уже было вычислено. вне. И он продолжает это делать, сравнивая операторов по одному с теми, о которых он знает, что является полной тратой циклов.
Надеюсь, этого достаточно, чтобы объяснить, почему в следующей грамматике не используются такие функции, как который. Если вы пишете функцию действия синтаксического анализатора Ply, и вы обнаруживаете, что используете оператор if, чтобы проверить, какое из произведений было сопоставлено, вам следует немедленно подумать об использовании двух (или более) различных функций действия. (Если действия имеют общие характеристики, рассмотрите возможность их выделения в подфункцию. Вероятно, результат будет более читабельным и более понятным.)
Примечание: здесь я использую комплексные числа Python. Независимо от причины, по которой вы этого не сделали, это никак не влияет на упражнение по синтаксическому анализу, за исключением добавления к коду синтаксического анализатора.
import ply.lex as lex
import ply.yacc as yacc
### Lexer
# This lexer uses literal character tokens wherever possible. They're
# easier, faster, and more readable.
# (https://www.dabeaz.com/ply/ply.html#ply_nn11)
literals = '()+-*/^i'
t_ignore = ' \t'
tokens = ( 'NUMBER', )
def t_NUMBER(t):
"(?:\d+(?:\.\d*)?|\.\d+)(?:[Ee][+-]?\d+)?"
t.value = float(t.value)
return t
def t_error(t):
print("Illegal character '%s'" % t.value[0])
t.lexer.skip(1)
### Parser
# Use this function for any unit production which just passes
# its value through.
def p_unit(p):
""" expression : additive
additive : multiplicative
multiplicative : exponential
exponential : value
value : NUMBER
"""
p[0] = p[1]
def p_plus(p):
""" additive : additive '+' multiplicative """
p[0] = p[1] + p[3]
def p_minus(p):
""" additive : additive '-' multiplicative """
p[0] = p[1] - p[3]
# Compare this production with the next one.
def p_implicit_times(p):
""" multiplicative : multiplicative exponential """
p[0] = p[1] * p[2]
def p_times(p):
""" multiplicative : multiplicative '*' exponential """
p[0] = p[1] * p[3]
# TODO: catch errors
def p_divide(p):
""" multiplicative : multiplicative '/' exponential """
p[0] = p[1] / p[3]
# This one is right-associative.
# TODO: catch errors
def p_power(p):
""" exponential : value '^' exponential """
p[0] = p[1] ** p[3]
def p_i(p):
""" value : 'i' """
p[0] = 1J # Python's way of writing 0+1i
def p_paren(p):
""" value : '(' expression ')' """
p[0] = p[2]
def p_error(t):
print("Syntax error at " + str(t))
### Very simple driver
import sys
lexer = lex.lex()
parser = yacc.yacc()
while True:
try:
print(parser.parse(input('> ')))
except EOFError:
break
except:
print(sys.exc_info()[1])
Может быть полезно взглянуть на грамматику, которую я извлечено из parser.out:
Rule 1 expression -> additive
Rule 2 additive -> multiplicative
Rule 3 multiplicative -> exponential
Rule 4 exponential -> value
Rule 5 value -> NUMBER
Rule 6 additive -> additive + multiplicative
Rule 7 additive -> additive - multiplicative
Rule 8 multiplicative -> multiplicative exponential
Rule 9 multiplicative -> multiplicative * exponential
Rule 10 multiplicative -> multiplicative / exponential
Rule 11 exponential -> value ^ exponential
Rule 12 value -> i
Rule 13 value -> ( expression )
Хорошо, теперь давайте рассмотрим один важный случай, когда нам нужно изменить грамматику для неявного умножения, чтобы избежать конфликта. Проблема в безобидном выражении 4 - 2. Теперь предположим, что в нашей грамматике реализован унарный минус (чего нет в вышеуказанной грамматике) В этом случае было бы два способа анализа выражения: как вычитание и как неявное произведение двух подвыражений: 4 и -2.
Очевидно, что вторая интерпретация неверна, и это означает, что мы не можем допустить, чтобы унарное выражение было вторым аргументом неявного умножения.
К счастью, мы уже отказались от попытки использовать объявления приоритетов для устранения неоднозначности нашей грамматики. Если бы мы пытались выяснить, как изменить
expression : expression expression
, чтобы второе выражение не могло начинаться с унарного оператора минус, у нас были бы большие проблемы.
Как другой Удар удачи, в стандартном обозначении алгебры c оператор возведения в степень является ассоциативно правым и также более тесно связывается слева, чем унарный минус, так что -2<sup>4</sup> оценивается как -16 (-(2<sup>4</sup>)), а не 16 (* 1083) *. Мы вставляем унарный минус в иерархию приоритетов, где он логически принадлежит, на том же уровне, что и возведение в степень. [См. Примечание 1] Но нам нужно сделать одно исключение, чтобы неявное произведение умножения не могло иметь унарное выражение минус в качестве правого аргумента. Чтобы сделать это, нам нужно разделить уровень на две части, например:
Rule 1 expression -> additive
Rule 2 additive -> multiplicative
Rule 3 multiplicative -> unary
Rule 4 unary -> exponential
Rule 5 exponential -> value
Rule 6 value -> NUMBER
Rule 7 additive -> additive + multiplicative
Rule 8 additive -> additive - multiplicative
Rule 9 multiplicative -> multiplicative exponential
Rule 10 multiplicative -> multiplicative * unary
Rule 11 multiplicative -> multiplicative / unary
Rule 12 unary -> - unary
Rule 13 exponential -> value ^ unary
Rule 14 value -> i
Rule 15 value -> ( expression )
Заметки
- Вы найдете много грамматик, которые настаивают на отдельном приоритете уровней, но если немного подумать об этом, вы увидите, что, поскольку возведение в степень является ассоциативным справа, оно может разделить уровень приоритета с унарным минусом. Если это неясно, это, вероятно, дополнительное доказательство того факта, что объявления предшествования имеют тенденцию создавать путаницу, за исключением очень простых случаев использования.