javacc之路2--- LOOCAHEAD

什么是前瞻？

解析器的工作是读取输入流并确定输入流是否符合语法。
这种最一般形式的确定可能非常耗时。
示例 1

void Input() :
{}
{
  "a" BC() "c"
}

void BC() :
{}
{
  "b" [ "c" ]
}
1
2
3
4
5
6
7
8
9
10
11

在这个简单的例子中，很明显恰好有两个字符串符合上面的语法，即：
abc
abcc

执行这种匹配的一般方法是根据字符串遍历语法如下（这里我们使用abc作为输入字符串）：

1. 这里只有一个选择——第一个输入字符必须是a，既然确实如此，我们就可以了。
2. 我们现在继续处理非终结符 BC。同样，下一个输入字符只有一个选择——它必须是b。输入也匹配这个，所以我们仍然可以。
3. 我们现在来到语法中的一个选择点。我们可以进入[…]并匹配它，也可以完全忽略它。我们决定进去。所以下一个输入字符必须是c. 我们又好了。
4. 现在我们已经完成了非终结符 BC 并返回到非终结符 Input。现在语法说下一个字符必须是另一个c。但是没有更多的输入字符，所以我们遇到了问题。
5. 当我们在一般情况下遇到这样的问题时，我们会得出结论，我们可能在某个地方做出了错误的选择。在这种情况下，我们在步骤 [3] 中做出了错误的选择。所以我们回溯到步骤 [3] 并做出另一个选择并尝试。这个过程称为回溯。
6. 我们现在已经回溯并做出了我们本可以在步骤 [3] 中做出的另一个选择——即忽略[…]. 现在我们已经完成了 non-terminal BC 并返回到 non-terminal Input。现在语法说下一个字符必须是另一个c。下一个输入字符是 c，所以我们现在可以了。
7. 我们意识到我们已经成功地到达了语法的结尾（非终结符的结尾Input）。这意味着我们已经成功地将字符串abc与语法匹配。

正如上面的示例所示，将输入与语法匹配的一般问题可能会导致大量回溯并做出新的选择，这会消耗大量时间。花费的时间量也可以是语法编写方式的函数。请注意，可以编写许多文法来涵盖同一组输入 - 或相同的语言，即对于相同的输入语言可以有多个等价的文法。

与之前的语法相比，以下语法将加快对同一语言的解析：

void Input() :
{}
{
  "a" "b" "c" [ "c" ]
}
1
2
3
4
5

由于解析器必须一直回溯到开头，因此以下语法会进一步减慢它的速度：

void Input() :
{}
{
  "a" "b" "c" "c"
|
  "a" "b" "c"
}
1
2
3
4
5
6
7

我们甚至可以有一个如下所示的语法：

void Input() :
{}
{
  "a" ( BC1() | BC2() )
}

void BC1() :
{}
{
  "b" "c" "c"
}

void BC2() :
{}
{
  "b" "c" [ "c" ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这种语法可以通过两种方式匹配abcc，因此被认为是有歧义的。

避免回溯

对于大多数包含解析器的系统来说，这种回溯带来的性能损失是不可接受的。因此，大多数解析器不会以这种一般方式回溯——或者根本不回溯。相反，他们根据有限的信息在选择点做出决定，然后做出承诺。

由 JavaCC 生成的解析器根据对输入流中更前面的标记的一些探索在选择点做出决定，并且一旦他们做出这样的决定，他们就会承诺它 - 即一旦做出决定就不会执行回溯。

在输入流中进一步探索标记的过程被称为展望输入流——因此我们使用了这个术语LOOKAHEAD。

由于其中一些决定可能是在信息不完善的情况下做出的，因此您需要了解一些相关知识LOOKAHEAD才能正确使用语法。注意 JavaCC 会在这些情况下警告您。

使选择决定正常工作的两种方式是：

修改语法使其更简单。
在更复杂的选择点插入提示以帮助解析器做出正确的选择。

JavaCC 语法中的选择点

JavaCC中有4种选择点：

扩张 描述

( exp1 \| exp2 \| ... )

生成的解析器必须以某种方式确定选择 等中的哪一个exp1来exp2继续解析。
1

( exp )?

生成的解析器必须以某种方式确定是选择exp还是继续超越( exp )?而不选择exp。注意：( exp )?也可以写成[ exp ].

( exp )*

生成的解析器必须做与前一种情况相同的事情，而且，在每次成功匹配exp（if expwas chosen）完成后，必须再次进行这种选择确定。

( exp )+

这在本质上类似于之前强制首先匹配到 的情况exp。 请记住，出现在尖括号内的令牌token <...>也有选择点。但是这些选择是以不同的方式做出的，并且是不同教程的主题。

默认选择确定算法

默认选择确定算法向前看输入流中的 1 个标记，并使用它来帮助在选择点做出选择。以下示例将完整描述默认算法。

示例 2
考虑以下语法：

void basic_expr() :
{}
{
   "(" expr() ")"	// Choice 1
|
  "(" expr() ")"	// Choice 2
|
  "new" 		// Choice 3
}
1
2
3
4
5
6
7
8
9

选择确定算法的工作原理如下：

if (next token is ) {
  // choose Choice 1
} else if (next token is "(") {
  // choose Choice 2
} else if (next token is "new") {
  // choose Choice 3
} else {
  // produce an error message
}
1
2
3
4
5
6
7
8
9

在上面的例子中，语法已经被编写成默认选择确定算法做正确的事情。另一件需要注意的事情是，选择确定算法以从上到下的顺序工作——如果Choice 1被选中，其他选择甚至都不会被考虑。LOOKAHEAD虽然这在本例中不是问题（性能除外），但当局部歧义需要插入提示时，它会变得很重要。

示例 3
考虑修改后的语法：

void basic_expr() :
{}
{
   "(" expr() ")"	// Choice 1
|
  "(" expr() ")"	// Choice 2
|
  "new" 		// Choice 3
|
   "." 		// Choice 4
}
1
2
3
4
5
6
7
8
9
10
11

那么默认算法将始终选择Choice 1下一个输入标记是什么时候，即使后面的标记是 a也永远不会选择。Choice 4.

您可以尝试在输入上运行示例 3id1.id2生成的解析器。它会抱怨.它在期待 a 时遇到了 a (。

注意当您构建解析器时，它会给您以下警告消息：

Warning: Choice conflict involving two expansions at
line 25, column 3 and line 31, column 3 respectively.
A common prefix is:
Consider using a lookahead of 2 for earlier expansion.
JavaCC 检测到语法中可能导致默认先行算法执行奇怪操作的情况。生成的解析器仍将使用默认的先行算法工作，但它可能无法达到您的预期。

例 4
现在考虑以下语法：

void identifier_list() :
{}
{
   ( ","  )*
}
1
2
3
4
5

假设第一个已经匹配并且解析器已经到达选择点（(…)*构造）。以下是选择确定算法的工作原理：

while (next token is ",") {
  choose the nested expansion (i.e. go into the (...)* construct)
	consume the "," token
	if (next token is ) {
    consume it, otherwise report error
  }
}
1
2
3
4
5
6
7

在上面的示例中，请注意选择确定算法不会超越(…)*构造来做出决定。

例 5
假设在同一个文法中有另一个产生式如下：

void funny_list() :
{}
{
  identifier_list() "," 
}
1
2
3
4
5

当默认算法在进行选择时，如果下一个标记是( “,” )*，它将始终进入(…)*构造,。identifier_list即使在被调用时它也会这样做，并且在isfunny_list之后的标记。直觉上，在这种情况下正确的做法是跳过构造并返回到.,(…)*funny_list

作为一个具体的例子，假设您的输入是id1, id2, 5，解析器会抱怨5它在期望.

注意当您构建解析器时，它会给您以下警告消息：

Warning: Choice conflict in (…)* construct at line 25, column 8.
Expansion nested within construct and expansion following construct
have common prefixes, one of which is: “,”
Consider using a lookahead of 2 or more for nested expansion.
JavaCC 检测到语法中可能导致默认先行算法执行奇怪操作的情况。生成的解析器仍将使用默认的先行算法工作，但它可能无法达到您的预期。

我们在上面的示例中展示了两种选择点的示例 -exp1 | exp2 | …和(exp)*。其他两种类型的选择点(exp)+和(exp)?行为相似，(exp)*因此没有必要提供进一步的使用示例。

前瞻规范

多令牌 LOOKAHEAD 规范

到目前为止，我们已经描述了生成的解析器的默认先行算法。在大多数情况下，默认算法工作得很好。在它无法正常工作的情况下，JavaCC 会为您提供如上所示的警告消息。如果你有一个语法通过 JavaCC 而没有产生任何警告，那么这个语法就是一个LL(1)语法。本质上，LL(1)语法是那些最多使用LOOKAHEAD.

当您收到这些警告消息时，您可以执行以下两项操作之一。

选项 1 - 语法修改
您可以修改语法以使警告消息消失。也就是说，您可以尝试LL(1)通过对其进行一些更改来构建语法。

例 6
下面的语法展示了你如何改变示例 3来制作它LL(1)：

void basic_expr() :
{}
{
   ( "(" expr() ")" | "."  )
|
  "(" expr() ")"
|
  "new" 
}
1
2
3
4
5
6
7
8
9

我们在这里所做的是将第四个选择重构为第一个选择。请注意我们如何将它们共同的第一个标记放在括号外，然后在括号内我们还有另一个选择，现在可以通过仅查看输入流中的一个标记并将其与(和进行比较来执行.。这种修改语法以生成语法的过程LL(1)称为左因子分解。

例 7
以下语法显示了如何更改示例 5使其成为LL(1)：

void funny_list() :
{}
{
   "," (  "," )* 
}
1
2
3
4
5

注意：这个变化有点剧烈。

选项 2 - 解析器提示
LL(1)您可以为生成的解析器提供一些提示，以在警告消息引起您注意的非情况下帮助它解决问题。

所有这些提示都是通过将全局LOOKAHEAD值设置为更大的值或使用LOOKAHEAD(…)构造来提供本地提示来指定的。

必须做出设计决策以确定是否Option 1或Option 2是否是正确的选择。选择的唯一好处Option 1是它可以让你的语法表现得更好。JavaCC 生成的解析器可以LL(1)比其他构造更快地处理构造。然而，选择的好处Option 2是你有一个更简单的语法——一个更容易开发和维护的语法，并且专注于人性化而不是机器友好性。

有时Option 2是唯一的选择——尤其是在存在用户操作的情况下。

假设示例 3包含如下所示的操作：

void basic_expr() :
{}
{
  { initMethodTables(); }  "(" expr() ")"
|
  "(" expr() ")"
|
  "new" 
|
  { initObjectTables(); }  "." 
}
1
2
3
4
5
6
7
8
9
10
11

由于动作不同，不能进行左因式分解。

设置全局 LOOKAHEAD 规范

您可以通过命令行或语法文件开头的选项部分中的选项来设置全局LOOKAHEAD规范。LOOKAHEAD此选项的值是一个整数，它是在做出选择决策时要向前看的标记数。您可能已经猜到了，此选项的默认值为1- ，它派生了上​​述默认LOOKAHEAD算法。

假设您将此选项的值设置为2。然后由此LOOKAHEAD派生的算法在做出选择决定之前会查看两个标记（而不是一个标记）。因此，在示例 3中，Choice 1只有当接下来的两个标记是和时才会被采用，而只有当接下来的两个标记是和(时Choice 4才会被采用.。因此，解析器现在可以为示例 3正常工作。类似地，示例 5(…)*的问题也消失了，因为解析器仅在接下来的两个标记是,和时才进入构造。

通过将全局设置LOOKAHEAD为2解析算法，本质上变成了LL(2). 由于您可以将全局设置LOOKAHEAD为任何值，因此由 JavaCC 生成的解析器称为LL(k)解析器。

设置本地 LOOKAHEAD 规范

您还可以设置LOOKAHEAD仅影响特定选择点的本地规范。这样一来，大部分语法都可以保留下来LL(1)，从而表现得更好，同时又获得了LL(k)语法的灵活性。

例 8
以下是如何使用 local 修改示例 3LOOKAHEAD以修复选择歧义问题：

void basic_expr() :
{}
{
  LOOKAHEAD(2)
   "(" expr() ")"	// Choice 1
|
  "(" expr() ")"	// Choice 2
|
  "new" 		// Choice 3
|
   "." 		// Choice 4
}
1
2
3
4
5
6
7
8
9
10
11
12

只有第一个选择（下面翻译中的第一个条件）受LOOKAHEAD规范影响。所有其他人继续使用单个令牌LOOKAHEAD：

if (next 2 tokens are  and "(" ) {
  // choose Choice 1
} else if (next token is "(") {
  // choose Choice 2
} else if (next token is "new") {
  // choose Choice 3
} else if (next token is ) {
  // choose Choice 4
} else {
  // produce an error message
}
1
2
3
4
5
6
7
8
9
10
11

例 9
同样，示例5可以修改如下：

void identifier_list() :
{}
{
   ( LOOKAHEAD(2) ","  )*
}
1
2
3
4
5

注意LOOKAHEAD规范必须出现在(…)正在做出选择的内部。该构造的翻译如下所示（在第一个被消耗后）：

while (next 2 tokens are "," and ) {
  choose the nested expansion (i.e., go into the (...)* construct)
  consume the "," token
  consume the  token
}
1
2
3
4
5

我们强烈建议您不要修改全局 LOOKAHEAD 默认值。

大多数语法都是 dominantly LL(1)，因此将整个语法转换为LL(k)以促进语法的某些部分不是LL(1). 如果您的语法和正在解析的输入文件非常小，那么这没关系。

您还应该记住，当 JavaCC 在选择点检测到歧义时打印的警告消息（例如前面显示的两条消息）只是告诉您指定的选择点不是LL(1). JavaCC 不验证您本地LOOKAHEAD规范的正确性——它假定您知道自己在做什么。

例 10
JavaCC 无法验证 local 的正确性，LOOKAHEAD如以下if语句示例所示：

void IfStm() :
{}
{
 "if" C() S() [ "else" S() ]
}

void S() :
{}
{
  ...
|
  IfStm()
}
1
2
3
4
5
6
7
8
9
10
11
12
13

这个例子就是著名的悬挂 else问题。如果你有一个看起来像这样的程序：

if C1 if C2 S1 else S2
else S2可以绑定到两个if语句中的任何一个。标准解释是它绑定到内部if语句（最接近它的那个）。默认选择确定算法恰好做了正确的事情，但它仍然打印以下警告消息：

Warning: Choice conflict in […] construct at line 25, column 15.
Expansion nested within construct and expansion following construct
have common prefixes, one of which is: “else”
Consider using a lookahead of 2 or more for nested expansion.
要抑制警告消息，您可以简单地告诉 JavaCC 您知道自己在做什么，如下所示：

void IfStm() :
{}
{
 "if" C() S() [ LOOKAHEAD(1) "else" S() ]
}
1
2
3
4
5

要在此类情况下强制LOOKAHEAD进行歧义检查，请将选项设置FORCE_LA_CHECK为true。

句法前瞻

考虑以下取自 Java 语法的产生式：

void TypeDeclaration() :
{}
{
  ClassDeclaration()
|
  InterfaceDeclaration()
}
1
2
3
4
5
6
7

在句法级别，ClassDeclaration可以以任意数量的abstract、final和public语句开头。虽然随后的语义检查会为同一修饰符的多次使用产生错误消息，但在解析完全结束之前不会发生这种情况。同样，InterfaceDeclaration可以以任意数量的abstractandpublic语句开头。

如果输入流中的下一个标记是大量abstract语句（比如 100 个）后跟interface怎么办？很明显，固定数量的LOOKAHEAD（例如LOOKAHEAD(100)）是不够的。人们可以争辩说，这是一种非常奇怪的情况，它不能保证任何合理的错误信息，并且在某些病态情况下做出错误的选择是可以的。

但是假设有人想对此进行精确说明。这里的解决方案是将 设置LOOKAHEAD为无穷大——也就是说，对标记的数量设置无限LOOKAHEAD。一种方法是使用非常大的整数值（例如可能的最大整数），如下所示：

void TypeDeclaration() :
{}
{
  LOOKAHEAD(2147483647)
  ClassDeclaration()
|
  InterfaceDeclaration()
}
1
2
3
4
5
6
7
8

用syntactic 也可以达到同样的效果LOOKAHEAD。在 syntacticLOOKAHEAD中，您指定一个扩展来尝试它，如果成功，则进行以下选择。

上面的例子可以使用语法重写LOOKAHEAD如下：

void TypeDeclaration() :
{}
{
  LOOKAHEAD(ClassDeclaration())
  ClassDeclaration()
|
  InterfaceDeclaration()
}
1
2
3
4
5
6
7
8

从本质上讲，这是在说：

if (the tokens from the input stream match ClassDeclaration) {
  // choose ClassDeclaration()
} else if (next token matches InterfaceDeclaration) {
  // choose InterfaceDeclaration()
} else {
  // produce an error message
}
1
2
3
4
5
6
7

上述句法LOOKAHEAD规范的问题在于LOOKAHEAD计算花费了太多时间，并做了很多不必要的检查。在这种情况下，LOOKAHEAD一旦class遇到令牌就可以停止计算，但是规范强制继续计算直到达到类声明的末尾，这是相当耗时的。

这个问题可以通过在句法LOOKAHEAD规范中放置一个较短的扩展来尝试解决，如下例所示：

void TypeDeclaration() :
{}
{
  LOOKAHEAD( ( "abstract" | "final" | "public" )* "class" )
  ClassDeclaration()
|
  InterfaceDeclaration()
}
1
2
3
4
5
6
7
8

从本质上讲，这是在说：

if (the next set of tokens from the input stream are a sequence of
  "abstract", "final", and "public" followed by a "class") {
  // choose ClassDeclaration()
} else if (next token matches InterfaceDeclaration) {
  // choose InterfaceDeclaration()
} else {
  // produce an error message
}
1
2
3
4
5
6
7
8

通过这样做，您可以让选择确定算法在看到时立即停止，class即尽早做出决定。

您可以在语法前瞻期间限制要消耗的令牌数量，如下所示：

void TypeDeclaration() :
{}
{
  LOOKAHEAD(10, ( "abstract" | "final" | "public" )* "class" )
  ClassDeclaration()
|
  InterfaceDeclaration()
}
1
2
3
4
5
6
7
8

在这种情况下，LOOKAHEAD不允许超出10令牌范围的确定。如果达到这个限制，仍然匹配成功( “abstract” | “final” | “public” )* “class”，ClassDeclaration则被选中。

如果未指定此类限制，则默认为最大整数值 ( 2147483647)。

语义前瞻

让我们回到示例 1：

void Input() :
{}
{
  "a" BC() "c"
}

void BC() :
{}
{
  "b" [ "c" ]
}
1
2
3
4
5
6
7
8
9
10
11

让我们假设有一个很好的理由以这种方式编写语法（也许是嵌入动作的方式）。如前所述，此语法识别两个字符串abc和abcc。这里的问题是默认LL(1)算法[ “c” ]每次看到 a 时都会选择 the c，因此abc永远不会匹配。c我们需要指定只有当下一个标记是 a并且紧随其后的标记不是 a 时才必须进行此选择c。这是一个否定的陈述——一个不能用句法来表达的陈述LOOKAHEAD。

LOOKAHEAD为此，我们可以使用语义。使用 semantic LOOKAHEAD，您可以指定任意布尔表达式，其评估决定在选择点采取哪个选择。

上面的示例可以使用语义进行检测，LOOKAHEAD如下所示：

void BC() :
{}
{
  "b"
  [ LOOKAHEAD( { getToken(1).kind == C && getToken(2).kind != C } )
    
  ]
}
1
2
3
4
5
6
7
8

首先，我们给 tokenc一个标签C，这样我们就可以从语义上引用它LOOKAHEAD。布尔表达式本质上说明了所需的属性。

因此，选择确定决定是：

if (next token is "c" and following token is not "c") {
  // choose the nested expansion (i.e., go into the [...] construct)
} else {
  // go beyond the [...] construct without entering it.
}
1
2
3
4
5

可以重写此示例以结合句法和语义LOOKAHEAD，如下所示：

void BC() :
{}
{
  "b"
  [ LOOKAHEAD( "c", { getToken(2).kind != C } )
    
  ]
}
1
2
3
4
5
6
7
8

c使用句法识别第一个LOOKAHEAD，使用语义识别第二个不存在LOOKAHEAD。

LOOKAHEAD的一般结构

LOOKAHEAD在前面的部分中，我们几乎涵盖了各个方面。我们现在将LOOKAHEAD在 JavaCC 中提供正式的语言参考。

规范的一般结构LOOKAHEAD是：

LOOKAHEAD ( amount, expansion, { boolean_expression } )
amount指定标记的数量，LOOKAHEAD指定expansion用于执行句法的扩展LOOKAHEAD，并且boolean_expression是用于语义的表达式LOOKAHEAD。

三个条目中至少有一个必须存在。如果存在多个，则用逗号分隔。

每个实体的默认值定义如下：

amount:

• if expansion is present, this defaults to 2147483647.
• otherwise (boolean_expression must be present then) this defaults to 0.
  注意当amountis时0，不执行句法LOOKAHEAD。另外，amount不影响语义LOOKAHEAD。

expansion:

• defaults to the expansion being considered.
  boolean_expression:
• defaults to true.