本文翻译自\javacc-5.0\doc\lookahead.html章节。
上文：http://blog.csdn.net/chaofanwei/article/details/25541065
1、LOOKAHEAD是什么
lookahead就是当语法分析器从词法分析器里取token时，需要取多少个才能让分析器正确的走下去。
例一
void Input() :
{}
{
"a" BC() "c"
}
void BC() :
{}
{
"b" [ "c" ]
}
在这个语法中，只能匹配“abc”和“abcc”。
假设我们现在把“abc”当成输入字符，来看javacc是如何工作的。
1、第一个字符是‘a’，这里没什么疑问，匹配“a”
2、读取下一个字符‘b’，毫无疑问进入BC(),刚好匹配‘b’
3、读取下一个自称‘c’，在这一步，我们看到了一个选择点，即是匹配[‘c‘]呢，还是跳出BC()，匹配最后一个‘c’。这里假定我们选择了[...],那么继续往下走。
4、因为现在我们已经跳出了BC(),但是Input说现在还需要一个‘c’，但我们已经没有字符了，因此宣告失败。
5、在遇到这种问题时，就说明我们在前面的选择点的地方可能选择了一个错误的决定，因此需要回溯到[...]
6、这个时候我们就应该选择Input里面的‘c’，这时候才能正确执行。
2、javacc里面的选择点
可以将javacc中choice point归结为以下几类：
l . 由选择算子 | 引入的冲突，
2. 由可省略算子 [] 或 ？引入的冲突
3. 由重复算子 * 引入的冲突
4. 由重复算子 + 引入的冲突
3、默认的选择点算法
看语法：
TOKEN [IGNORE_CASE] :
{
<ID: (["a"-"z"])+>
}
void basic_expr() :
{}
{
<ID> "(" expr() ")" // Choice 1
|
"(" expr() ")" // Choice 2
|
"new" <ID> // Choice 3
}
if (next token is "(") {
choose Choice 2
} else if (next token is "new") {
choose Choice 3
} else if (next token is <ID>) {
choose Choice 1
} else {
produce an error message
}
上面语法是没有什么冲突的，假如改成如下语法：
void basic_expr() :
{}
{
<ID> "(" expr() ")" // Choice 1
|
"(" expr() ")" // Choice 2
|
"new" <ID> // Choice 3
|
<ID> "." <ID> // Choice 4
}
就会报如下冲突信息：
arning: Choice conflict involving two expansions at
line 25, column 3 and line 31, column 3 respectively.
A common prefix is: <ID>
Consider using a lookahead of 2 for earlier expansion.
意思就是说在默认的选择算法在这种情况下不能正确执行，因为1和4都是以ID开头的，这就是我们上面说的左因子。
4、选择点冲突解决算法
1.修改语法，使之成为LL(1)语法。
2.只要将LOOKAHEAD=k写到Options块中即可,javacc产生的分析器就可以分析LL(K)语法生成的语言
采用第一种方法的好处是效率非常高，易于维护。采用第二种方法的好处是语法更加直观，但是却不易维护。有时候采用第一种方法是无法解决冲突的，第二种方法是唯一的选择。
5、设置全局LOOKAHEAD
全局的lookahead是在jj文件中的options中指定的，可以指定为非负整数，javacc自动生成LL(K)算法。这种方法是不提倡的，因为这会在每个选择点都进行LL(K)算法，即多向前看k个token，但大部分选择点都是一个（默认）就可以了。
假定这时把lookahead设置成2，那么在上面的3中的第二个文法就会变成:
当下来的两个token是<ID> 和"("时，那么选择点1，
如果下来的两个token是<ID> and "."时，那么就选择点4。
这样就能让上面的语法正常执行。
6、设置局部LOOKAHEAD
可以通过设置局部的lookahea方法，使语法分析器只在需要的时候向前看K个字符，别的情况下只用看一个就可以了，这种情况下，效率自然比通过全局设置好。
可以把上面语法改下：
void basic_expr() :
{}
{
LOOKAHEAD(2)
<ID> "(" expr() ")" // Choice 1
|
"(" expr() ")" // Choice 2
|
"new" <ID> // Choice 3
|
<ID> "." <ID> // Choice 4
}
通过以上设置，只使第一个选择点使用LOOKAHEAD(2)。这种情况下工作逻辑如下：
if (next 2 tokens are <ID> 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 <ID>) {
choose Choice 4
} else {
produce an error message
}
7、语法上的LOOKAHEAD
看语法：
void TypeDeclaration() :
{}
{
ClassDeclaration()
|
InterfaceDeclaration()
}
这里假定ClassDeclaration定义为在class的前面可以出现无数多次的public，final，而InterfaceDeclaration的定义也是前面可以出现出现无数多次的public，final。那么问题就出现了，因为当分析器在工作时，并不知道到底有多少个public或者fianl，也就不知道到底需要向前看多不个token，才能确定到底是选择ClassDeclaration还是InterfaceDeclaration。
显然简单的方法就是向前看无数多个，如下：
void TypeDeclaration() :
{}
{
LOOKAHEAD(2147483647)
ClassDeclaration()
|
InterfaceDeclaration()
}
但这样显示是不合理的，合理的做法应该是下面的方法：
void TypeDeclaration() :
{}
{
LOOKAHEAD(ClassDeclaration())
ClassDeclaration()
|
InterfaceDeclaration()
}
意思就是说，还是一直向前看，如果ClassDeclaration()能够匹配成功，则就用ClassDeclaration()，否则的话进入InterfaceDeclaration()。即：
if (the tokens from the input stream match ClassDeclaration) {
choose ClassDeclaration()
} else if (next token matches InterfaceDeclaration) {
choose InterfaceDeclaration()
} else {
produce an error message
}
当然还有一种优化的方法，见下：
void TypeDeclaration() :
{}
{
LOOKAHEAD( ( "abstract" | "final" | "public" )* "class" )
ClassDeclaration()
|
InterfaceDeclaration()
}
工作过程就是：
if (the nest set of tokens from the input stream are a sequence of
"abstract"s, "final"s, and "public"s followed by a "class") {
choose ClassDeclaration()
} else if (next token matches InterfaceDeclaration) {
choose InterfaceDeclaration()
} else {
produce an error message
}
即如果下面的一些列token匹配( "abstract" | "final" | "public" )* "class"，那么就选择ClassDeclaration()，否则选择InterfaceDeclaration()。
当然还有一种更加优化的方法，见下：
void TypeDeclaration() :
{}
{
LOOKAHEAD(10, ( "abstract" | "final" | "public" )* "class" )
ClassDeclaration()
|
InterfaceDeclaration()
}
在这种情况下，具体的工作过程就是，这时lookahead最多向前看10个token，如果超过10token后，还匹配( "abstract" | "final" | "public" )* "class"的话，那么就进入选择点ClassDeclaration()。
其实当不设置10的时候，默认的值就是最大值，即2147483647。
8、语义上的LOOKAHEAD
看语法：
void Input() :
{}
{
"a" BC() "c"
}
void BC() :
{}
{
"b" [ "c" ]
}
为了解决上面说到的回溯问题，我们可以使用如下的语法：
void BC() :
{}
{
"b"
[ LOOKAHEAD( { getToken(1).kind == C && getToken(2).kind != C } )
<C:"c">
]
}
意思就是：
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.
}
首先把‘c’封装成一个label C，便于我们在lookahead里面引用它，即如果下来的第一个token是C和第二个不是C，那么选择[..],否则跳出BC。
其实上面的改写还可以使用下面的形式：
void BC() :
{}
{
"b"
[ LOOKAHEAD( "c", { getToken(2).kind != C } )
<C:"c">
]
}
即同时使用语法和语义上的lookahead。第一个c为语法上的lookahead，第二个为语义上面的lookahead。
9、LOOKAHEAD结构总结
通用的格式为：
LOOKAHEAD( amount,
expansion,
{ boolean_expression }
)
amount：即设置向前看的token个数；
expansion：即指定的语法上的lookahead，
boolean_expression：即指定的语义上的lookahead。
格式中的3个部分，至少指定一个部分，如果同时出现多个部分，则使用逗号分隔。