Связь между грамматикой и операторной ассоциативностью

Question

В некоторых книгах / статьях / статьях компилятора говорится о разработке грамматики и отношении ассоциативности ее оператора.Я большой поклонник нисходящего, особенно рекурсивного спуска, синтаксических анализаторов и до сих пор большинства (если не всех) написанных мной компиляторов, использующих следующую грамматику выражений:

Expr   ::= Term { ( "+" | "-" ) Term }
Term   ::= Factor { ( "*" | "/" ) Factor }
Factor ::= INTEGER | "(" Expr ")"

, которая является представлением EBNFэтого BNF:

Expr  ::= Term Expr'
Expr' ::= ( "+" | "-" ) Term Expr' | ε
Term  ::= Factor Term'
Term' ::= ( "*" | "/" ) Factor Term' | ε
Factor = INTEGER | "(" Expr ")"

Согласно тому, что я прочитал, некоторые считают эту грамматику «неправильной» из-за изменения ассоциативности операторов (слева направо для этих 4 операторов), что подтверждается растущим деревом разборанаправо, а не налево.Для синтаксического анализатора, реализованного с помощью грамматики атрибутов, это может быть истиной, поскольку значение l-атрибута требует, чтобы это значение сначала создавалось, а затем передавалось дочерним узлам.однако, при реализации с помощью обычного синтаксического анализатора с рекурсивным спуском, мне решать, нужно ли сначала создать этот узел, затем передать его дочерним узлам (сверху вниз) или разрешить сначала создавать дочерние узлы, а затем добавить возвращенное значение в качестве дочерних элементов этого узла (передано).в конструкторе этого узла) (снизу вверх).Здесь должно быть что-то, по чему я скучаю, потому что я не согласен с утверждением, что эта грамматика является «неправильной», и эта грамматика использовалась во многих языках, особенно.Виртские.Обычно (или все?) Чтение, которое говорит, что способствует LR-анализу вместо LL.

Answer 1

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

Грамматика вашей реализации:

Expr  ::= Term Expr'
Expr' ::= ( "+" | "-" ) Term Expr' | ε
Term  ::= Factor Term'
Term' ::= ( "*" | "/" ) Factor Term' | ε
Factor ::= INTEGER | "(" Expr ")"

должен сделать это неловко;если вы реализуете рекурсивный спуск, подпрограмма Expr не имеет доступа к «левому потомку» и поэтому не может построить дерево.Вы всегда можете исправить это, передавая кусочки (в данном случае передавая части дерева вверх по рекурсии), но это просто кажется неловким.Вместо этого вы могли бы выбрать это в качестве грамматики:

Expr  ::= Term  ( ("+"|"-") Term )*;
Term  ::= Factor ( ( "*" | "/" ) Factor )* ;
Factor ::= INTEGER | "(" Expr ")"

, что так же просто (проще?) Кодировать рекурсивное спускание, но теперь вы можете без проблем формировать деревья, которые вам нужны.

Это не на самом деле дает вам ассоциативность;это только формирует деревья так, чтобы это могло быть позволено.Ассоциативность означает, что дерево (+ (+ ab) c) означает то же самое, что и (+ a (+ bc));на самом деле это семантическое свойство (конечно, оно не работает для "-", но грамматика в том виде, в котором она изложена, не может различаться).

У нас есть инструмент ( DMS Software Reengineering Toolkit ), которыйвключает в себя парсеры и переписывание терминов (с использованием преобразований источник-источник), в которых ассоциативность явно выражена.Мы написали бы вашу грамматику:

Expr  ::= Term ;
[Associative Commutative] Expr  ::= Expr "+" Term ;
Expr  ::= Expr "-" Term ;
Term  ::= Factor ;
[Associative Commutative] Term  ::= Term "*" Factor ;
Term  ::= Term "/" Factor ;
Factor ::= INTEGER ;
Factor ::= "(" Expr ")" ;

Грамматика кажется более длинной и неуклюжей, но на самом деле она позволяет нам выделять особые случаи и отмечать их по мере необходимости.В частности, теперь мы можем отличать операторы, которые являются ассоциативными, от операторов, которые не являются, и пометить их соответственно.С этой семантической маркировкой наш механизм переписывания деревьев автоматически учитывает ассоциативность и коммутативность.Вы можете увидеть полный пример таких правил DMS, которые используются для символического упрощения алгебры средней школы с использованием явных правил перезаписи над типовой грамматикой выражений, которые не должны учитывать такие семантические свойства.Это встроено в механизм перезаписи.

Answer 2

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

E ::= E + E | E - E | E * E | E / E | Int | (E)

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

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

Expr ::= Term + Term | Term - Term | Term
Term ::= Factor * Factor | Factor / Factor | Factor
Factor ::= INTEGER | (Expr)

В противном случае невозможно получить правильные предложения, начиная с начального символа (в этом случае Expr).Например, как бы вы получили «1 * 2» без этих дополнительных производств?

Expr -> Term
     -> Factor * Factor
     -> 1 * Factor
     -> 1 * 2

Мы можем видеть, что другие грамматики обрабатывают это немного по-другому:

Expr -> Term Expr'
     -> Factor Term' Expr'
     -> 1 Term' Expr'
     -> 1 * Factor Term' Expr'
     -> 1 * 2 Term' Expr'
     -> 1 * 2 ε Expr'
     -> 1 * 2 ε ε
      = 1 * 2

, ноэто дает тот же эффект.

Ваш анализатор на самом деле неассоциативен.Чтобы увидеть это, спросите, как будет проанализирован E + E + E, и обнаружите, что это невозможно.В зависимости от того, что потребляется + первым, мы получаем E с одной стороны и E + E с другой, но затем мы пытаемся проанализировать E + E как Term, что невозможно.Эквивалентно, подумайте о том, чтобы извлечь это выражение из начального символа, опять же, это невозможно.

Expr -> Term + Term
     -> ? (can't get another + in here)

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

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