Python PLY Yacc - Разбор деления комплексных чисел

В вашей программе не хватает одного:

precedence = (
    ('left', 'DIVIDE'),
)

Без этого Ply генерирует конфликт сдвига-уменьшения при генерации синтаксического анализатора из-за производственного

expression : expression DIVIDE expression

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

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

мы, вероятно, должны попытаться представить все возможные варианты использования. И один из них должен сразу прийти в голову: 4i2 (без подробных сведений о том, какой оператор вы выбираете для представления возведения в степень).

Неправильная грамматика слитного числа и воображаемого будет видеть это как квадрат 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

и, кроме того, он имеет тот же приоритет и ассоциативность, что и деление или явное умножение.

Но это оставляет нам проблему: как вы можете поместить оператор в таблицу приоритетов, когда оператора нет? И короткий ответ: вы не можете. Есть некоторые уловки, которые более или менее работают, но, безусловно, самая простая и удобочитаемая альтернатива - написать грамматику так, чтобы приоритет был явным.

Я не буду больше вдаваться в этот стиль, потому что он был забит до смерти в другом месте, и у вас не будет проблем с поиском примеров по всему Интернету (большинство из которых используют нетерминалы, называемые 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

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

Еще одна удача: в стандартной алгебраической нотации оператор возведения в степень является правоассоциативным, а также более плотно привязан к левой части, чем унарный минус, так что -24 оценивается как -16 (-(24)), а не 16 ((-2)4).

Когда мы сложим все вместе, модификация, разрешающая унарный минус, оказывается почти тривиальной. Мы вставляем унарный минус в иерархию приоритета, которой он логически принадлежит, на том же уровне, что и возведение в степень. [См. Примечание 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 )

Примечания

1. Вы найдете много грамматик, которые настаивают на отдельных уровнях приоритета, но если вы немного задумаетесь, вы увидите, что, поскольку возведение в степень является правоассоциативным, оно может иметь общий уровень приоритета с унарным минусом. Если это неясно, это, вероятно, дополнительное свидетельство того факта, что объявления приоритета имеют тенденцию создавать путаницу, за исключением очень простых случаев использования.