YACC | BISON: Как мне манипулировать деревом разбора? - PullRequest
Новая
       62

YACC | BISON: Как мне манипулировать деревом разбора?

3 голосов
/ 11 января 2012

Цель моего приложения - проверить SQL-код и в то же время сгенерировать из этого кода отформатированный код с некоторой модификацией.Например, это где предложение:

гдеe.student_name = c.contact_name и (c.address = "nefta" или c.address = "tozeur") ивозраст <18</p>

у нас будет в виде отформатированного вывода что-то вроде этого:

где e.student_name = c.contact_nameи (c.address = trim ("nefta")или c.address = trim ("tozeur"))и e.age <18</p>

Надеюсь, я хорошо объяснил свою цель

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

search_condition         : search_condition OR search_condition{clbck_or}
                         | search_condition AND search_condition{clbck_and}
                         | NOT search_condition {clbck_not}
                         | '(' search_condition ')'{clbck__}
                         | predicate {clbck_pre}
                         ;

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

% осталось ИЛИ
% осталось И
% осталось НЕ

Итак, вернемся к последнему примеру;мое предложение, где будет использовано таким образом:

c.address = "nefta" или c.address = "tozeur" -> search_condition(c.address = "nefta" или c.address = "tozeur") -> search_conditione.student_name = c.contact_name и (c.address = "nefta" или c.address = "tozeur") -> условие поиска... и e.age <18-> search_condition

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

Любая помощь для этой проблемы?

Ответы [ 2 ]

2 голосов
/ 12 января 2012

Ваш вопрос немного расплывчатый, поэтому я предполагаю, что вы на самом деле печатаете в своем clbck_or () и т. Д. "Общий" способ, на который ссылался wildplasser, - это использовать "семантические значения" я е. (Непроверенные): 

search_condition         : search_condition OR search_condition{$$ = clbck_or($1, $3);}
                         | search_condition AND search_condition{$$ = clbck_and($1, $3);}
                         | NOT search_condition {$$ = clbck_not($2);}
                         | '(' search_condition ')'{$$ = clbck__($2);}
                         | predicate {$$ = clbck_pre($1);}
                         ;

Если вы используете Bison, в руководстве есть прекрасный пример в разделе «Калькулятор обозначений Infix:« calc »». Со строками и C вам придется добавить немного обработки памяти.

1 голос
/ 12 января 2012

Бизон хорош в разборе, и с некоторой ручной помощью, хорош в построении собственного синтаксического дерева.После этого вам решать, что вы хотите с деревом.Хорошая новость в том, что вы можете делать все, что захотите.Плохая новость заключается в том, что вам все равно придется создавать множество механизмов, чтобы делать то, что вы хотите.Ваша основная проблема восстановления исходного кода называется «prettyprinting»;см. мой SO ответ о том, как довольно распечатать , чтобы понять, что нужно для этого, включая все peccadillos лексического синтаксиса (вы не потеряете escape-символы в своих строковых строках, верно?).Вы вообще не задались вопросом, как найти конструкцию, которую вы хотите изменить в дереве, или как разбить дерево, чтобы изменить его.

Если вы не хотите делать все это,тогда вам действительно нужна система преобразования программ , которая хороша в разборе, построении синтаксического дерева для вас (так что вам не нужно об этом думать, SQL - довольно большая грамматика), позволитвы находите шаблоны в дереве с точки зрения используемого вами синтаксиса SQL, вносите изменения в дерево, не зная много о форме дерева, и, наконец, можете восстановить действительный исходный текст с помощью prettyprint, как я описал в моей ссылке на ответ выше.(Системы преобразования программ по существу включают в себя синтаксический анализатор в качестве подпрограммы.)

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

 domain SQL;

 rule trim_c_members(f: identifier, s: string):condition->condition
 = " c.\f = \s " ->  " c.\f = trim(\s) ";

Это синтаксис языка (мета) правил DMS для описания перезаписи на ("домен")SQL-кодУ правила есть имя (потому что в сложном приложении есть много правил), и это как синтаксические заполнители "f" и "s";он переписывает только условия в коде.Кавычки являются мета-кавычками RSL;внутри есть SQL с метавариями RSL "\ f" и "\ s";вещи вне синтаксиса правила RSL.Правило гласит: «для любого условия в переменной, явно названной« c », с любым полем f, если это поле сравнивается по равенству с некоторой литеральной строкой, то замените литеральную строку на« trim », примененную к литеральной строке».

Я пропустил некоторый код, который в основном говорит: «Примени это правило ко всему дереву и не применяй его дважды в одном и том же месте».Эта «стратегия» является одной из многих встроенных в DMS.

Существует вопрос о том, как работает правило.это достигается с помощью DMS, применяющей синтаксический анализатор SQL к строкам мета-кавычек, для создания синтаксических деревьев «шаблонов» с заполнителями, в которые записываются мета-переменные.Затем дерево шаблонов левой стороны сопоставляется с целевым деревом, а заполнитель ссылается на поддеревья;правое дерево объединяется в том месте, где левое дерево совпадает, а поддерево перемещается.Итак, вы, программист, видите поверхностный синтаксис, который вы знаете и любите;инструмент работает с деревьями, поэтому его не смущает текст.

Так вот, я не думаю, что мое правило точно соответствует вашим намерениям, но это отчасти потому, что я не могу угадать ваши настоящие намерения.Вы можете написать другие правила, если это не то, что вы хотели.

Это правило основано исключительно на синтаксисе;Можно добавить семантический предикат (не показан), если вы хотите, чтобы к правилу применялись более сложные условия (например, переменные должны быть единицами только в определенных областях, которые вы определяете), и это становится более беспорядочным.Но это намного проще и намного проще для чтения, чем код C, который поднимается по AST (заметьте, что вы не видели AST здесь?) И пытается все это выяснить.

Анализ и симпатичная печать происходят раньшеи после применения правила;для реализации всего этого требуется много механизмов, но этот механизм встроен в DMS (например, он имеет нечто вроде [но более мощного], чем встроенный Bison), а для предопределенных доменов, таких как SQL, все симпатичные печатные работы имеютбыл предварительно настроен тоже.

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

...