时间戳

首页 > 解决方案 > JavaCC中，如何降低正则表达式的优先级？

compiler-construction - JavaCC中，如何降低正则表达式的优先级？

问题描述

让我用一个具体的例子来澄清我的问题：

首先，我有一个令牌：

<T_SELECT:"SELECT">

其次，我有一个正则表达式标记：

<T_TABLE_NAME:~[","]>

三、我有一个制作：

<T_SELECT> <T_TABLE_NAME> (","<T_TABLE_NAME>)*

Finnaly，我想解析这样的字符串：

SELECT TABLE1

我的问题是： JavaCC 最终以as代替，SELECT而不是 consume ！TABLE1SELECT TABLE1<T_TABLE_NAME>

显然我期待它会消耗殆尽SELECT，因为我已经定义了一个名为<T_SELECT: "SELECT">

我可以做些什么来告诉 JavaCC 使用我定义的确切字符串而不是正则表达式？

标签： compiler-constructionjavacc

解决方案

我假设您拥有的唯一词汇规则是这些

TOKEN { <T_SELECT:"SELECT"> }
TOKEN { <T_TABLE_NAME:~[","]> }
TOKEN { <T_COMMA: "," > }

第三条规则是隐含的，因为您的语法中有字符串“，”。我在这里明确表示。现在如果要解析的字符序列是

 "SELECT TABLE1" ,

该序列将按如下方式进行词法分析

  • 首先找到一个 T_SELECT。
  • 然后是 7 个 T_TABLE_NAME 令牌。
  • 然后是一个 EOF 令牌。

IE：

T_SELECT("SELECT")
T_TABLE_NAME(" ")
T_TABLE_NAME("T")
T_TABLE_NAME("A")
...
T_TABLE_NAME("1")
EOF

如果你的语法包含一条规则

void select() : {} {
    <T_SELECT>
    <T_TABLE_NAME>
    (<T_COMMA> <T_TABLE_NAME>)* 
}   ,

那么只有前两个令牌将被匹配。

如果你的语法包含一条规则

void select() : {} {
    <T_SELECT>
    <T_TABLE_NAME>
    (<T_COMMA> <T_TABLE_NAME>)* 
    <EOF>   // I added an <EOF>
}   ,

那么示例输入有语法错误，解析器将抛出异常。对于第三个标记，解析器期望 aT_COMMA或 an EOF，但它得到 a T_TABLE_NAME。

我将做更多的假设。

  • 首先，我将假设表名可以包含 0 个或多个字符，而不是 OP 中的 1 个字符。
  • 其次，我将假设表名不能包含换行符或换行符。否则，除了点击文件末尾之外，将无法终止SELECT查询。
  • 第三，我将假设换行符或文件结尾会终止每个SELECT查询。
  • 第四，我将假设SELECT关键字仅在表名之前使用。

这些可能是不正确的假设，但我需要做出一些假设才能理解这个问题。

作为第一个更改，我将允许表名是任意长度。我将禁止在表名和逗号中使用换行符。我会制作一个新的令牌来处理任何换行符。现在的词法规则

TOKEN { <T_SELECT:"SELECT"> }
TOKEN { <T_TABLE_NAME: (~[",","\n","\r"])* > }
TOKEN { <T_COMMA: "," > }
TOKEN { <T_NEWLINE: ("\n" | "\n\r" | "\r") > }

现在会发生什么？再次假设输入字符串是

"SELECT TABLE1"    ,

有一个匹配规则的长度为 6 的前缀

<T_SELECT:"SELECT">

并且有几个（实际上是 14 个）前缀与规则匹配

<T_TABLE_NAME: (~[",","\n","\r"])* >

由于两个规则都匹配长度为 6 的前缀，所以总共有 14 个前缀可以被至少一个规则匹配。

在这 14 个前缀中，词法分析器总是选择最长的。这是最大咀嚼规则。因此令牌的序列将是

T_TABLE_NAME("SELECT TABLE1") EOF

没有办法关闭最大量规则。你赢不了这场比赛。你必须作弊。

作弊的方法是退出比赛。将T_TABLE_NAME规则移动到不同的词法状态。

您想在词法分析器看到 SELECT 关键字后切换状态。

像这样编写您的词法分析器规则：

TOKEN : { <T_SELECT: "SELECT"> : S_TABLE_NAME } 

<S_TABLE_NAME> TOKEN :
    { <T_TABLE_NAME:(~[",","\n","\r"])*> : S_TABLE_NAME 
    | <T_COMMA: "," } : S_TABLE_NAME
    | <T_NEWLINE: ("\n" | "\n\r" | "\r") : DEFAULT }

现在您的生产将是

void Select() : {} 
{ <T_SELECT>
  <T_TABLE_NAME>
  ( <T_COMMA> <T_TABLE_NAME>)*
  ( <T_NEWLINE> )? 
  <EOF>
}

如果输入是

 "SELECT ABC, DEF\n"    ,

它的词法如下

State          Token Produced
------------------------------
DEFAULT        T_SELECT("SELECT")
S_TABLE_NAME   T_TABLE_NAME( " ABC" )
S_TABLE_NAME   T_COMMA( "," )
S_TABLE_NAME   T_TABLE_NAME( " DEF" )
S_TABLE_NAME   T_NEWLINE( "\n" )
DEFAULT        EOF.

它会毫无错误地解析。

推荐阅读