YACC|BISON：如何操作解析树？

Question

我的应用程序的目标是验证 SQL 代码，同时从该代码生成经过一些修改的格式化代码。
例如这个 where 子句：

其中
e.student_name= c.contact_name and ( c.address = " nefta" 或 c.address=" tozeur ") 和
e.age <18

我们将得到类似这样的格式化输出：

其中 e.student_name= c.contact_name
and (c.address=trim("nefta")
或 c.address=trim("tozeur") )
和 e.age <18

我希望我已经很好地解释了我的目标

---

问题是语法可能包含递归规则，这使得重写任务成为可能不可靠；例如，在我的 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" ->搜索条件
(c.address="nefta"或 c.address="tozeur")->search_condition
e.student_name= c.contact_name and (c.address="nefta"or c.address="tozeur")->搜索条件
...以及e.age<18->搜索条件

顺便说一句，您可以理解，由于顺序不同，因此很难通过每次归约触发的回调来重建输入流。

对于这个问题有什么帮助吗？

Answer 1

你的问题有点模糊，所以我猜你实际上在你的 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，手册中的“中缀表示法计算器：`calc'”部分有一个很好的示例。对于字符串和 C，您将必须添加一些内存处理。

Answer 2

Bison 擅长解析，并且在一些手动帮助下，擅长构建自定义语法树。之后，你就可以对这棵树做你想做的事情了。好消息是您可以做任何您想做的事情。坏消息是你仍然需要建造大量机器来完成你想做的事情。重新生成源代码的基本问题称为“漂亮打印”；请参阅我的关于如何漂亮打印的答案来了解如何做到这一点，包括词法语法的所有小错误（你不要丢失文字字符串中的转义符，对吧？）。您根本没有解决如何在树中找到您想要更改的构造，或者如何粉碎树来更改它。

如果您不想做所有这些，那么您真正想要的是一个 程序转换系统，它擅长解析，为你构建语法树（所以你不必考虑它，SQL是相当大的语法），会让你在SQL方面找到树中的模式你使用的语法到，在不了解树的形状的情况下进行树更改，并且最终可以通过 beautifulprint 重新生成有效的源文本，正如我在上面的答案链接中所描述的那样。 （程序转换系统本质上包括作为子例程的解析器）。

我们的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 元引号；里面的内容是带有 RSL 元变量“\f”的 SQL
和“\s”；外面的东西是 RSL 规则语法。规则说的是，
“对于显式命名为“c”的变量的任何条件，以及任何字段 f，
如果该字段与某个文字字符串进行相等比较，则替换
将“trim”的文字字符串应用于文字字符串”。

我省略了一些代码，基本上是说，“将此规则应用于整个树，并且不要在同一位置应用两次”。该“策略”是DMS 中内置的许多

规则之一是通过 DMS 将 SQL 解析器应用于元引用字符串来完成的，以生成带有元变量写入位置的“模式”语法树。然后，手边模式树与目标树进行匹配，占位符引用子树；右手树被拼接到左树匹配的位置，并且占位符子树被转移，因此，程序员看到了您熟悉和喜欢的表面语法；该工具适用于树木，因此它不会被文本混淆。

现在，我认为我的规则与您的意图并不完全匹配，但这部分是因为我无法猜测您的实际意图，如果不是的话，您可以编写其他规则。不是你什么 ；

这个规则纯粹是由语法驱动的 如果您希望将更复杂的条件应用于规则（例如，变量必须仅在您定义的某些范围内），则可以添加语义谓词（未显示），这会变得更混乱。但它比爬过 AST 的 C 代码要简单得多，也更容易阅读（注意你在这里没有看到 AST？）并试图弄清楚这一切。

解析和漂亮打印发生在规则应用之前和之后；实现所有这些需要很多机器，但是这些机器内置于 DMS 中（例如，它内置了比 Bison [但更强大] 的东西），并且对于 SQL 等预定义域，所有漂亮的打印工作都具有也已预先配置。

如果您想更好地了解使用 DMS 进行完整周期需要什么（定义您自己的语言解析器、定义漂亮的打印机、定义复杂的规则），这里有一个很好且完整的 使用 DMS 定义和符号简化微积分的示例。