javacc-LOOKAHEAD MiniTutorial 翻译

       本文翻译自\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个部分,至少指定一个部分,如果同时出现多个部分,则使用逗号分隔。

 

 

 

 






 

 

 

javacc-LOOKAHEAD MiniTutorial 翻译,布布扣,bubuko.com

javacc-LOOKAHEAD MiniTutorial 翻译

上一篇:C/C++笔试忍法帖01——系统篇


下一篇:C/C++笔试忍法帖04——C/C++语法特性篇