2

我正在尝试使用 Menhir 为正则表达式语言编写解析器。在我修改它以消除歧义之前，我想要的语法看起来有点像下面的例子。请注意，“排序/连接”是隐式的，并且没有与该操作关联的标记。

%token LPAREN RPAREN
%token CHAR STAR PIPE
%token EOF

%start <unit> parse

%%

parse: re EOF {()}

re:
  | LPAREN re RPAREN {()}  (* Grouping *)
  | CHAR             {()}  (* Single character *)
  | re STAR          {()}  (* Kleene star *)
  | re re            {()}  (* Sequencing / Concatenation *)
  | re PIPE re       {()}  (* Alternation *)

如果我有连接的标记，我将能够通过使用优先声明来消除歧义

%token LPAREN RPAREN
%token CHAR STAR PIPE
%token CONCAT
%token EOF

%left PIPE
%left CONCAT
%nonassoc STAR

%start <unit> parse

%%

parse: re EOF {()}

re:
  | LPAREN re RPAREN   {()}  (* Grouping *)
  | CHAR               {()}  (* Single character *)
  | re STAR            {()}  (* Kleene star *)
  | re CONCAT re       {()}  (* Sequencing / Concatenation *)
  | re PIPE re         {()}  (* Alternation *)

但是，如果没有连接规则中的 CONCAT 令牌，我将无法正常工作。我尝试使用%prec声明，但仍然存在一些移位/减少冲突。

%token LPAREN RPAREN
%token CHAR STAR PIPE
%token CONCAT
%token EOF

%left PIPE
%left CONCAT
%nonassoc STAR

%start <unit> parse

%%

parse: re EOF {()}

re:
  | LPAREN re RPAREN   {()}  (* Grouping *)
  | CHAR               {()}  (* Single character *)
  | re STAR            {()}  (* Kleene star *)
  | re re %prec CONCAT {()}  (* Sequencing / Concatenation *)
  | re PIPE re         {()}  (* Alternation *)

我认为这可能是因为 menhir 无法判断排序应该是左关联的，但我不能 100% 确定这是否是问题的原因。

到目前为止，我能找到的唯一解决方案是将re规则分解为一堆不同的规则，这些规则使优先级和关联性明确：

%token LPAREN RPAREN
%token CHAR STAR PIPE
%token EOF

%start <unit> parse

%%

parse: re EOF {()}

re: re3 {()}

re0:
  | LPAREN re RPAREN {()}  (* Grouping *)
  | CHAR             {()}  (* Single character *)

re1:
  | re0              {()}
  | re0 STAR         {()}  (* Kleene star *)

re2:
  | re1              {()}
  | re2 re1          {()}  (* Sequencing / Concatenation *)

re3:
  | re2              {()}
  | re3 PIPE re2     {()}  (* Alternation *)

尽管最后一个示例运行良好，但我真的很好奇是否可以仅通过使用优先级和关联性声明来消除所有歧义和冲突，而无需重写语法。

4

1 回答 1

3

嗯，首先，这不完全是 Menhir 的问题，而是 Menhir 接受的那种语法问题，它位于LR(1)集合中。如果您提供的语法不需要优先注释，则该语法被视为SLR(1)的子集LR(1)。

您的最后一个示例有效，因为您对每个优先级都有产品（例如解析表达式语法，本质上是明确的），并且绝对不是一种糟糕的编写方式；一些现代编译器使用这种表示法来处理更复杂的语言。

为了理解你的问题，让我们首先要求 Menhir 向我们解释冲突发生在哪里：

menhir --explain parser.mly

它将生成一个parser.conflicts文件，其中解释了它可以在哪些状态下采取行动，减少和转移：

...
** In state 8, looking ahead at STAR, shifting is permitted
** because of the following sub-derivation:

re re
   re . STAR

** In state 8, looking ahead at STAR, reducing production
** re -> re re
** is permitted because of the following sub-derivation:

re STAR // lookahead token appears
re re .

** Conflict (shift/reduce) in state 7.
** Tokens involved: STAR PIPE LPAREN CHAR
** The following explanations concentrate on token STAR.
** This state is reached from parse after reading:

re PIPE re

** The derivations that appear below have the following common factor:
** (The question mark symbol (?) represents the spot where the derivations begin to differ.)

parse
re EOF
(?)

语法对于 真的是模棱两可的LR(1)，所以：

CHAR CHAR STAR

可以计算为：

  • (CHAR CHAR) STAR
  • CHAR (CHAR STAR)

另一种在没有冲突的情况下重写语法的方法是通过以下方式进行连接list：

re:
| term PIPE re
| term { } (* Left associativity *)

term:
| list(base STAR* { }) { } (* Concatenation is taken by list *)

base:
| CHAR
| LPAREN re RPAREN { }
于 2018-04-10T14:15:05.440 回答