在自上而下的解析器中处理分支

Question

我有一个用JavaCC实现的自上而下的解析器。 因此，我正在利用向我展示的访客模式来行走 AST。

如果我忽略控制流，我就解决了整个问题。 我在控制流方面遇到的问题是如何管理分支以及它们指向的位置。 具体来说，在 IR 生成中，这是我的情况：

// This is just to make my example explicit.
honorary_source_statement()
if (expression()) {
statements...
} else if(expression'()) {
statements...'
} else {
statements...''
}
// This just to make my example explicit.
honorary_sink_statement()
statements()...'''

我可以将我的honorary_source_statement()与领先的if联系起来. 我可以将if语句中的所有语句都绑定到它们需要去的地方。 我还可以将所有后续分支绑定在一起：

• if是真的去statements...
• if的假去else if
• else如果真的去statements...'
• else if的假去else
• else去statements...''

以上适用于 if 语句的 n 嵌套。

我遇到的问题是接受statements...、statements...'和statements...''的最后指令，并将其与honorary_sink_statement()联系起来，它们各自的失败。 我通读了阿佩尔书、龙书和劳登书。 他们都只是挥挥手，并没有深入管理的细节。

我正在构建一个混合 IR。 所以它是结构性的，因为它是图形形式，它使用修改后的 3 地址 IR。

我甚至尝试跳过一个步骤并使用基本块来表示这一点，但问题仍然存在：如何将接收器绑定到分支中的最终直通指令。

下面提供了我的JavaCC的相关部分。

void Statement() :
{}
{
LOOKAHEAD(AssignmentInstruction())
AssignmentInstruction()
/* omitted rest of statements for brevity */
|   BranchStatement()
|   FunctionInvoke()
}
void BranchStatement() :
{}
{
<IF> <LPAREN> Expression() <RPAREN> <LBRACE> Statement() <RBRACE>
(<ELSE_IF> <LPAREN> Expression() <RPAREN> <LBRACE> Statement()<RBRACE>)*
(<ELSE> <LBRACE> Statement() <RBRACE>)?
}

这给我留下了一个访客结构：

/**
* f0 -> IfStatement()
* f1 -> ( ElseIfStatement() )*
* f2 -> ( ElseStatement() )?
*/
@Override
public BSVisitor visit(BranchInstruction n) {
n.f0.accept(this);
if(n.f1.present()) {
n.f1.accept(this);
}
if(n.f2.present()) {
n.f2.accept(this);
}
}
/**
* f0 -> <IF>
* f1 -> <LPAREN>
* f2 -> Expression()
* f3 -> <RPAREN>
* f4 -> <LBRACE>
* f5 -> Statement()
* f6 -> <RBRACE>
*/
@Override
public BSVisitor visit(IfStatement n) {
// parse it!
}
/**
* f0 -> <ELSE_IF>
* f1 -> <LPAREN>
* f2 -> Expression()
* f3 -> <RPAREN>
* f4 -> <LBRACE>
* f5 -> Statement()
* f6 -> <RBRACE>
*/
@Override
public BSVisitor visit(ElseIfStatement n) {
// parse it!
}
/**
* f0 -> <ELSE>
* f1 -> <LBRACE>
* f2 -> Statement()
* f3 -> <RBRACE>
*/
@Override
public BSVisitor visit(ElseStatement n) {
// parse it!
}

Answer 1

我不确定我是否完全理解了这个问题，但无论如何我都会尝试回答它。

首先，我会以不同的方式构建 AST。例如，如果我们代表会更好，

if( condition0 ) { statement1 }
elseif( condition1 ) {statement2}
elseif( condition2 ) { statement3 }
else { statement4 }

有这样的树

IF -+-- Condition0
|
+-- Statement1
|
+-- IF -+-- Condition1
|
+-- Statement2
|
+-- IF -+-- Condition2
|
+-- Statement3
|
+-- Statement4

如果没有 ELSE，只需将最终语句设为 SKIP 语句，即不执行任何操作的语句。

我假设您的 IR 是某种控制流图，由一堆由一堆边缘连接的节点组成。如果可以在目标节点之前创建边，则会有所帮助。

现在假设您有语句的访问者，这些语句将一组边(尚未定位)作为输入，并生成一组边(尚未定位)。 SKIP 语句的访问者将采用一组边并返回相同的一组边。 赋值语句的访问者将获取一组边，生成一个节点，将所有这些边定位到该节点，然后生成离开该节点的单个边，并输出一组仅包含该边的边。

还假设条件的访问者采用一组尚未定位的边，并返回两组尚未定位的边 - 一组用于条件为真时，另一组用于条件为假时。

IF的访客看起来像这样

visit( IF(c, s, t), S)
(A, B) := visit( c, S )
T := visit(s, A )
U := visit(t, B )
output T union U

您的示例代码在一行中有三个语句，您可以使用顺序组合节点在 AST 中表示这些语句，该节点恰好需要 2 个子级，如下所示

SEQCOMP -+-- statement0
|
+-- SEQCOMP -+-- statement1
|
+-- statement2

然后

visit( SEQCOMP(s, t), S)
T := visit(s, S )
U := visit(t, T )
output U

或者，您可以表示一个包含三个语句的块，其中包含具有可变数量的子节点的单个节点：

BLOCK -+-- statement0
|
+-- statement1
|
+-- statement2

而访客

visit( BLOCK( ss ), S)
var T := S
for t in ss
T := visit(t, T )
output T