Блог

У меня возникли некоторые проблемы с созданием Bison оператора как такового: <- = постфиксный оператор идентификации с низким приоритетом для принудительной оценки того, что находится слева первым, например 1 2<-*3 (эквивалентно (1 2)*3 ), а также -> префиксного оператора, который делает то же самое, но справа.

Мне не удалось заставить синтаксис работать должным образом и протестировать его с использованием Python - not False , что привело к синтаксической ошибке (в Python - имеет больший приоритет, чем not ). Однако это не проблема в C или C , где - и ! / not имеют одинаковый приоритет.

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

Почему связывание префиксных или постфиксных операторов с разными прецедентами является проблемой при синтаксическом анализе и как реализовать операторы <- и -> , сохраняя при этом операторы с более высоким приоритетом, такие как ! , NOT , и т.д.?

Обязательный зубр (этот шаблон повторяется для всех операторов, где copy имеет больший приоритет, чем post_unary ):

 post_unary:
    copy
|   post_unary "  "
|   post_unary "--"
|   post_unary '!'
;
 

Операторы цепочки в этой категории, например x ! -- ! , прекрасно работают синтаксически.

Хорошо, позвольте мне предложить возможную ошибочную грамматику, основанную на вашем наброске:

 low_postfix:
    mid_infix
|   low_postfix "<-"
mid_infix:
    high_postfix
|   mid_infix ' ' high_postfix
high_postfix:
    term
|   high_postfix "  "
term:
    ID
    '(' expr ')'
 

Должно быть ясно, просто глядя на те произведения, которые var <- не являются частью языка. Единственные вещи, которые можно использовать в качестве операнда , — это term s и другие приложения . var <- не является ни тем, ни другим.

С другой стороны, var <- это нормально, потому что операндом to <- может быть a mid_infix , который может быть a high_postfix , который является приложением оператора.

Если намерение состояло в том, чтобы разрешить обе эти постфиксные последовательности, то эта грамматика неверна.

Версия этого каскада присутствует в грамматике Python (хотя и с использованием префиксных операторов), поэтому not - False она в порядке, но - not False является синтаксической ошибкой. Я не хочу называть это ошибкой, потому что это могло быть сделано намеренно. (На самом деле, ни одно из этих выражений не имеет особого смысла.) Мы могли бы не согласиться с ценностью такого намерения, но не в отношении SO, которая предпочитает избегать самоуверенных дискуссий.

Обратите внимание, что то, что мы могли бы назвать «строгим приоритетом» в этой грамматике и грамматике Python, никоим образом не ограничивается комбинациями унарных операторов. Вот еще один, который вы, вероятно, никогда не пробовали:

 $ python3 -c 'print(41   not False)'
  File "<string>", line 1
    print(41   not False)
                 ^
SyntaxError: invalid syntax
 

Итак, как мы можем это исправить?

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

С другой стороны, это очень просто сделать с объявлениями приоритета bison/yacc. Мы просто перечисляем операторы по порядку, и генератор синтаксического анализатора соответствующим образом устраняет все неоднозначности. [См. Примечание 1 ниже]

Вот грамматика, аналогичная приведенной выше, с объявлениями приоритета. (Я оставил действия на месте на случай, если вы захотите поиграть с ним, хотя это ни в коем случае не воспроизводимый пример; инфраструктура, на которую он опирается, намного больше, чем сама грамматика, и мало полезна кому-либо, кроме меня. Поэтому вам придется определить три функции и заполнить некоторые объявления типа bison. Или просто удалите функции AST и используйте свои собственные.)

 %left ','
%precedence "<-"                                                        
%precedence "->" 
%left ' '
%left '*'                                                               
%precedence NEG
%right "  " '('
%%
expr: expr ',' expr                { $ = make_binop(OP_LIST, $1, $3); }
    | "<-" expr                    { $ = make_unop(OP_LARR, $2); }
    | expr "->"                    { $ = make_unop(OP_RARR, $1); }
    | expr ' ' expr                { $ = make_binop(OP_ADD, $1, $3); }
    | expr '*' expr                { $ = make_binop(OP_MUL, $1, $3); }
    | '-' expr          %prec NEG  { $ = make_unop(OP_NEG, $2); }
    | expr '(' expr ')' %prec '('  { $ = make_binop(OP_CALL, $1, $3); }
    | "  " expr                    { $ = make_unop(OP_PREINC, $2); }
    | expr "  "                    { $ = make_unop(OP_POSTINC, $1); }
    | VALUE                        { $ = make_ident($1); }
    | '(' expr ')'                 { $ = $2; }
 

Пара заметок:

1. Я использовал %prec NEG унарное производство минус, чтобы отделить это производство от производства вычитания. Я также использовал %prec объявление для изменения приоритета производства вызова (по умолчанию будет ')' ), хотя в данном конкретном случае это необязательно. Однако его необходимо внести '(' в список приоритетов. ( является символом заголовка, который используется при сравнении приоритетов.
2. Для многих унарных операторов я использовал %precedence объявление зубра в списке приоритетов, а не %right или %left . На самом деле, такой вещи, как ассоциативность с унарными операторами , не существует, поэтому я думаю, что она более самодокументирована в использовании %precedence , что не разрешает конфликты, связанные с сокращениями и сдвигами на одном и том же уровне приоритета. Однако, несмотря на то, что между унарными операторами нет такой вещи , как ассоциативность, природа алгоритма разрешения приоритета заключается в том, что вы можете поместить префиксные операторы и постфиксные операторы на один и тот же уровень приоритета и выбрать, имеют ли постфиксные или префиксные операторы приоритет, используя %right или %left , соответственно. %right это почти всегда правильно. Я сделал это с помощью , потому что я был немного ленив к тому времени, когда дошел до этого момента.

Это действительно «работает» (я думаю). Это, безусловно, решает все конфликты; бизон с радостью выдает синтаксический анализатор без предупреждений. И тесты, которые я пробовал, работали, по крайней мере, так, как я ожидал:

 ? a  ->
=> [-> [  /post a]]
? a->  
=> [  /post [-> a]]
? 3*f(a) 2
=> [  [* 3 [CALL f a]] 2]
? 3*f(a)-> 2
=> [  [-> [* 3 [CALL f a]]] 2]
? 2 <-f(a)*3
=> [  2 [<- [* [CALL f a] 3]]]
? 2 <-f(a)*3->
=> [  2 [<- [-> [* [CALL f a] 3]]]]
 

Но есть некоторые выражения, в которых приоритет оператора, хотя и «правильный», может быть нелегко объяснить начинающему пользователю. Например, хотя операторы со стрелками выглядят как круглые скобки, они не группируются таким образом. Кроме того, решение о том, какой из двух операторов имеет более высокий приоритет, кажется мне совершенно произвольным (и действительно, я мог бы сделать это иначе, чем вы ожидали). Считать:

 ? <-2*f(a)-> 3
=> [<- [  [-> [* 2 [CALL f a]]] 3]]
? <-2 f(a)->*3
=> [<- [* [-> [  2 [CALL f a]]] 3]]
? 2 <-f(a)->*3
=> [  2 [<- [* [-> [CALL f a]] 3]]]
 

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

 ? 2 f(a)*3
=> [  2 [* [CALL f a] 3]]
? 2 f(a)->*3
=> [* [-> [  2 [CALL f a]]] 3]
 

Если таково ваше намерение, прекрасно. Это твой язык.

Обратите внимание, что существуют проблемы приоритета операторов, которые не так просто решить, просто перечисляя операторы в порядке приоритета. Иногда двоичному оператору было бы удобно иметь разную силу привязки с левой и правой сторон.

Классическим (но, возможно, спорным) случаем является оператор присваивания, если это оператор. Назначение должно ассоциироваться справа (потому что разбор a = b = 0 как (a = b) = 0 был бы нелепым), и обычно ожидается, что оно с жадностью примет как можно больше справа. Если бы назначение имело последовательный приоритет, то оно также принимало бы как можно больше слева, что кажется немного странным, по крайней мере, мне. Если a = 2 b = 7 имеет смысл, моя интуиция говорит, что его значение должно быть a = (2 (b 7)) [Примечание 2]. Это потребовало бы дифференцированного приоритета, что немного сложно, но не неслыханно. C решает эту проблему, ограничивая левую часть операторов присваивания (синтаксическими) значениями, которые не могут быть выражениями двоичных операторов. Но в C это действительно означает a = ((2 b) = 7) , что семантически допустимо , если 2 b оно было перегружено функцией, возвращающей ссылку.

Примечания

1. Объявления приоритета на самом деле не добавляют никакой мощности генератору синтаксического анализатора. Языки, для которых он может создавать синтаксический анализатор, являются точно такими же языками; он создает одну и ту же машину для синтаксического анализа (автомат pushdown); и, по крайней мере, теоретически возможно взять этот автомат pushdown и перепроектировать грамматику из него. (На практике грамматики, создаваемые этим процессом, обычно чудовищны. Но они существуют.)

   Все, что делают объявления приоритета,-это разрешают конфликты синтаксического анализа (обычно в неоднозначной грамматике) в соответствии с некоторыми правилами, предоставленными пользователем. Поэтому стоит спросить, насколько проще с объявлениями о приоритете, чем писать однозначную грамматику.

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

   Но когда мы пишем грамматику, мы должны явно указать, какие конструкции возможны в каждой точке грамматики, что мы обычно делаем, определяя группу нетерминалов, каждый из которых соответствует некоторому состоянию синтаксического анализа. Однозначная грамматика для выражений уже разделила нетерминал expression на каскадную серию нетерминалов, по одному для каждого значения приоритета оператора. Но унарные операторы не имеют одинаковой силы привязки с обеих сторон (поскольку, как отмечалось выше, одна сторона унарного оператора не может принимать операнд). Это означает, что двоичный оператор вполне может принимать унарный оператор для одного из своих операндов и не может принимать тот же унарный оператор для другого своего операнда. Что, в свою очередь, означает, что нам нужно снова разделить все наши нетерминалы, в зависимости от того, появляется ли нетерминал слева или справа от двоичного оператора.

   Это большая работа, и очень легко ошибиться. Если вам повезет, ошибка приведет к конфликту синтаксического анализа; но в равной степени это может привести к тому, что грамматика не сможет распознать конкретную конструкцию, которую вы никогда бы не подумали попробовать, но которую какой-нибудь разгневанный пользователь языка считает абсолютной необходимостью. (Например 41 not False )

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