parsing - 解决 LALR 歧义

Question

我最近对 ​​LALR 的研究足以写一篇 LALR generator ，并且我正在尝试为其构造一个 java 或 c# 风格的语法(其开头指定为 here )。

我知道编写解析器生成器需要额外的努力，就像重新发明轮子一样(为什么不使用 Antlr？)，但我的目标是引导一个业余爱好操作系统，它可以在不依赖第三方工具链的情况下自行编译。我的问题不在于生成器，而在于语法。

我在语句和表达式方面遇到了reduce/reduce 歧义。

我知道如何解决某些类型的歧义，例如 dangling-else，但这些对我来说并不直观，它们让我难住了。

解决这些问题的最佳方法是什么？另外，是否有可以用来帮助可视化解决方案的原型(prototype)设计工具？或者，我应该回到第一步并尝试为语法实现 GLR 解析器生成器吗？

这些声明是合法的:

Generic.List<int> myVar1 = x + 4, myVar2; // stmt -> var-decl ;
                                          // var-decl -> type-name var-decl-list

t = 99;                           // simple-stmt -> assign

i++;                              // simple-stmt -> incr-decr
                                  // incr-decr -> primary-expr ++

json.deserialize<list<int>>(obj); // simple-stmt -> call
                                  // call -> primary-expr ( params )
                                  // ...  -> primary-expr . basic-name ( params )
                                  // ...  -> basic-name . basic-name ( params )

设置方式如下:

basic-name : ident < type-list >
           | ident

nested-name : nested-name . basic-name
            | basic-name

basic-type : int | bool | ...

type-name : nested-name
          | basic-type

stmt : var-decl ;
     | simple-stmt ;
     | ...

var-decl : type-name var-decl-list

var-decl-list : var-decl-list , var-init
              | var-init

var-init : ident assign-op expression
         | ident

simple-stmt : assign
            | call
            | incr-decr

expr : assign-expr

assign-expr : assign
            | cond-expr

assign : unary-expr assign-op expr

...
rel-expr : rel-expr < shift-expr
         ...
         | shift-expr

...
unary-expr : unary-op primary-expr
           | primary-expr

unary-op : + - ! ~ ++ --  // Prefix operators
         | ( type-name )  // Conversion operator

primary-expr : call
             | primary-expr . basic-name
             | primary-expr ++
             | ( expr )
             ...
             | basic-name

call : primary-expr ( params )

incr-decr : primary-expr ++
          | -- primary-expr
          | ...

因此，当解析器等待语句时，*LR(k) 项集内核为 method-body -> { * stmts-opt }该状态的完整项目集如下所示:

method-body -> { * stmts-opt }
stmts-opt -> * stmts
stmts-opt -> *
stmts -> * stmts stmt
stmt -> * var-decl ;
stmt -> * simple-stmt ;
var-decl -> * type-name var-decl-list
simple-stmt -> * assign
simple-stmt -> * call
simple-stmt -> * incr-decr
type-name -> * nested-name
type-name -> * basic-type
nested-name -> * nested-name . basic-name
nested-name -> * basic-name
basic-name -> * ident < type-list >
basic-name -> * ident
assign -> * unary-expr assign-op expr
unary-expr -> * unary-op primary-expr
unary-expr -> * primary-expr
unary-op -> * ( typename )
unary-op -> * ! | ~ | ...
primary-expr -> * call
primary-expr -> * primary-expr . basic-name
primary-expr -> * primary-expr ++
primary-expr -> * basic-name
primary-expr -> * ( expr )
call -> * primary-expr ( params )
incr-decr -> * primary-expr ++
...

当标识符发生移位时，下一个状态是:

basic-name -> ident *
basic-name -> ident * < type-list >

被解析或减少，并将下一个状态带到:

nested-name -> basic-name *
primary-expr -> basic-name *

潜在的冲突。在父状态中，前瞻没有帮助，因为nested-name中有一个点。和primary-expr 。哦，太好了，让我们尝试通过嵌套名称来减少:

type-name -> nested-name *
nested-name -> nested-name * . basic-name

这里没什么可看的...现在，减少 primary-expr 怎么样？相反:

unary-expr -> primary-expr *
primary-expr -> primary-expr * . basic-name
primary-expr -> primary-expr * ++
call -> primary-expr * ( params )
incr-decr -> primary-expr * ++
...

现在当我们移动++ 时，我们得到:

primary-expr -> primary-expr ++ *
incr-decr -> primary-expr ++ *

...另一个归约-归约冲突。

让我们尝试移动 (而不是 ident :

primary-expr -> ( * expr )
unary-op -> ( * type-name )
expr -> * assign-expr
assign-expr -> * assign
assign-expr -> * cond-expr
assign -> * unary-expr assign-op expr
unary-expr -> * unary-op primary-expr
unary-expr -> * primary-expr
unary-op -> * ( typename )
unary-op -> * ! | ~ | ...
primary-expr -> * call
primary-expr -> * primary-expr . basic-name
primary-expr -> * primary-expr ++
primary-expr -> * basic-name
primary-expr -> * ( expr )
call -> * primary-expr ( params )
cond-expr -> * ...
...
rel-expr -> * rel-expr < shift-expr
rel-expr -> * shift-expr
...
type-name -> * nested-name
type-name -> * basic-type
nested-name -> * nested-name . basic-name
nested-name -> * basic-name
basic-name -> * ident < type-list >
basic-name -> * ident

转移 ident 时出现同样的问题或(入栈。

这些只是我到目前为止遇到的。自 basic-name优先于rel-expr ，我假设类似 x < n将被解释为 basic-name -> ident < type-list * ，如果它实际上是一个关系表达式，则会出错。

我的大脑已经达到了我真正需要帮助的地步。

Answer 1

您的帖子中有一些问题，这使得它对于 SO 来说并不理想。但我会尝试对每一项提出一些想法。在我看来，您面临三个问题:

1. 区分表达式语句和非语句表达式。

2. 解析声明中的分层命名类型，而不与表达式语句中的字段访问表达式发生冲突

3. 区分使用 < 作为比较运算符和模板括号。

<小时/>

1。区分表达式语句和非语句表达式。

据我了解，我们的愿望是只允许具有(或可能具有)某种副作用的 as 语句:赋值、增量突变和子例程调用。粗略地说，这对应于Java，其语法包括:

StatementExpression:
  Assignment
  PreIncrementExpression
  PreDecrementExpression
  PostIncrementExpression
  PostDecrementExpression
  MethodInvocation
  ClassInstanceCreationExpression

为 StatementExpression 列出的每个替代方案也出现在 Expression 的派生树中的某个位置，它们已从列表中分解出来的可能性。这是一个非常简洁的示例:

Expression:
  LambdaExpression
  AssignmentExpression

AssignmentExpression:
  ConditionalExpression
  Assignment

Assignment:
  LeftHandSide AssignmentOperator Expression

...

UnaryExpression:
  PreIncrementExpression
  + UnaryExpression
  UnaryExpressionNotPlusMinus

PreIncrementExpression:
  ++ UnaryExpression

UnaryExpressionNotPlusMinus:
  PostfixExpression
  ~ UnaryExpression

PostfixExpression:
  Primary
  ExpressionName
  PostIncrementExpression

PostIncrementExpress:
  PostfixExpression ++

请注意 ExpressionStatement 右侧使用的非终结符在每个优先级上的特殊情况。在 C++ 语法中，不限制哪些表达式可以是语句，因此不需要单独的赋值非终结符:

assignment-expression:
  conditional-expression
  logical-or-expression assignment-operator initializer-clause

但在 Java 中，这是行不通的。它需要创建不派生 ConditionalExpression 的附加非终结符，正是为了允许 Assignment 成为 Statement 和 赋值表达式是一个表达式。

2。解析声明中的分层命名类型，而不与表达式语句中的字段访问表达式发生冲突

与上面类似，这里有必要从其他形式的字段访问表达式中放置分层名称(必须以 basic-name 开头)，该表达式可能以任何(其他)主表达式。前者可以是类型名称或主表达式；后者只能是类型名称。为了做出这种区分，我们需要拆分 primary-expr 产生式:

primary-expr : field-access-expr
             | nested-name

non-field-access-expr:
               call
             | post-increment-expression  // was primary-expr ++
             | ( expr )
             ...

field-access-expr :
               non-field-access-expr
             | field-access-expr . basic-name

3。区分使用 < 作为比较运算符和模板括号。

与其他两个问题不同，这个问题实际上可能是语言中的歧义。例如，在 C++ 中，模板括号肯定是不明确的；它们只能通过知道(或被告知)特定名称是否是模板名称来解决。另一方面，在 Java 中，有时要求类型参数位于通用名称之前，从而解决了歧义。例如:

ConstructorDeclarator:
  [TypeParameters] SimpleTypeName ( [FormalParameterList] )

或

MethodInvocation:
  Primary . [TypeArguments] Identifier ( [ArgumentList] )

在 C# 中，还有一个不同的规则，它需要查看 > 后面的字符，该字符可能与开头的 < 匹配。该算法在 C# 手册的 §7.6.4.2 中有描述；我不知道如何在 LALR(1) 解析器中实现它。