解决 LALR 歧义

Question

我最近对 LALR 有了足够的了解，足以写一篇 LALR generator, and I'm trying to construct a java- or c#-style grammar for it (the beginnings of which are specified here)。

我知道编写解析器生成器需要额外的努力，就像重新发明轮子一样（为什么不用 Antlr？），但我的目标是 bootstrap 一个可以编译的爱好 [=70=]本身而不依赖于第三方工具链。我的问题不在于生成器，而在于语法。

我运行陷入 reduce/reduce 语句和表达式的歧义。

我知道如何解决某些类型的歧义，例如 dangling-else，但是这几个对我来说并不直观，它们让我很困惑。

解决这些问题的最佳方法是什么？另外，是否有原型设计工具可用于帮助可视化解决方案？或者，我应该回到第一个问题并尝试为语法实现一个 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

你的 post 中有几个问题，这使得它不太适合 SO。但我会尝试提供关于每一个的一些想法。在我看来，您遇到了三个问题：

区分表达式语句和不是语句的表达式。
在不与表达式语句中的字段访问表达式冲突的情况下解析声明中的分层命名类型
区分使用 < 作为比较运算符和模板括号。

1。区分表达式语句和不是语句的表达式。

据我了解，希望只允许具有（或可能具有）某种副作用的语句表达式：赋值、增量突变和子例程调用.粗略地说，这对应于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 非终结符：

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

但在 Java 中，这行不通。它需要创建不派生 ConditionalExpression 的附加非终结符，正是为了让 Assignment 成为 Statement 和 AssignmentExpression 成为 Expression.

2。在不与表达式语句中的字段访问表达式冲突的情况下解析声明中的分层命名类型

和上面类似，这里需要把其他形式的字段访问表达式的层级名称（必须以basic-name开头），可能以任何（其他）[=26=开头].前者可以是类型名称或初级表达式；后者只能是类型名称。为了做出这种区分，我们需要拆分 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) 解析器中实现它。

解决 LALR 歧义

Resolving LALR Ambiguities

parsing

compiler-construction

grammar

lalr

ambiguous-grammar

1。区分表达式语句和不是语句的表达式。

2。在不与表达式语句中的字段访问表达式冲突的情况下解析声明中的分层命名类型

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

解决 LALR 歧义

Resolving LALR Ambiguities

parsing

compiler-construction

grammar

lalr

ambiguous-grammar

1。区分表达式语句和不是语句的表达式。

2。在不与表达式语句中的字段访问表达式冲突的情况下解析声明中的分层命名类型

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

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