Законы Де Моргана с yacc

Question

A имеют простую грамматику, написанную в yacc, которая строит дерево из логических выражений, состоящих из подвыражений, и AND (&), OR (||) и NOT (!) Операторов. Здесь я не буду предоставлять грамматику, потому что в ней нет ничего особенного, и она похожа на бесчисленные примеры учебников YACC.

Однако мне нужно проанализировать эти логические выражения, чтобы все круглые скобки были расширены для оператора NOT в соответствии с законами Де Моргана. Например, мне нужно лечить выражение:

!((A && B) || C)) 

в

(!A || !B) && !C 

Можно ли осуществить это путем изменения существующей грамматике YACC?

Answer 1

Это можно сделать в случае действия уменьшения YACC для оператора не (!) При строительстве АСТ. Вы можете написать любой код в семантическом действии. Вместо «слепо» сборки узла дерева для не из его дочернего элемента (обычный код, который вы найдете в таком сокращающем действии), вы можете написать код, который проверил бы ребенка, чтобы узнать, была ли у него требуемая форма, и если поэтому построим древообразное дерево де Моргана каждого. Код, чтобы сделать это немного грязно, потому что он должен лезть вверх и вниз по дереву, сопоставляя узлы и переставляя поддеревья, но его просто yuck и неплохо. Обратите внимание, что закон Де Моргана, возможно, применим к детям, имеющим форму как (A & & B) || C) и (A || B & & C)), поэтому вы должны обрабатывать два основных подсекции.

Я согласен с Len; вы обычно не делали бы этого в парсере. Его цель - настроить вас на более сложные действия, и если DeMorganizing не будет единственной целью, вам понадобится другой код для обработки AST в разных случаях, после того, как разборок завершен, так почему бы не оставить всю обработку до тех пор, пока она не появится?

Следуя этой идее, мой recent SO answer on eliminating configured-dead code упрощает символическую логическую логику; он показывает один из способов преобразования логических логических АСТ с использованием преобразований источника в источник с использованием шаблонов. Такой подход позволяет избежать инкубирования/взлома кода yucky tree. Должно быть очевидно, как писать читаемый превращает, что реализует закон Моргана с этой техникой (и на самом деле мы сделали сына в прошлом).

Answer 2

Это не то, что вы должны делать в самой грамматике yacc; вы должны выполнить пост-обработку AST своих конструкций грамматики для выполнения таких сокращений.

Ваша грамматика должна быть получения AST из своего рода, вы хотите, чтобы ходить структуры и искать что-то, которая соответствует форме !((A && B)|| C) и преобразовать его в месте, чтобы (!A || !B) && C.

Если вам нужны дополнительные рекомендации, возможно, вам будет полезно добавить дополнительную информацию или задать больше вопросов.

Edit: вы должны обеспечить свою грамматику, если вы хотите какой-либо помощи с этим вообще. Это звучит как домашнее задание, поэтому я надеюсь, что это не единственная причина, по которой вы не предоставляете код. Помогите нам помочь вам. Мы не знаем, что вы делаете в действиях вашей грамматики, так как мы можем догадаться, что мы можем сделать для вас?