正在解决开关块中默认标签的 shift/reduce 冲突

Question

我正在使用 PLY 为 Unrealscript 编写一个解析器，并且我已经运行进入（希望如此）我设置的解析规则中的最后一个歧义。

Unrealscript 有一个关键字，default，根据上下文使用不同。在常规语句行中，您可以像这样使用 default：

default.SomeValue = 3;  // sets the "default" class property to 3

当然，switch 语句也有 default case 标签：

switch (i) {
    case 0:
        break;
    default:
        break;
}

当在它认为是 case 的语句块中遇到 default 标签时，解析中存在歧义。这是运行出现解析错误的示例文件：

输入

class Example extends Object;

function Test() {
    switch (A) {
        case 0:
            default.SomeValue = 3;    // OK
        default:                      // ERROR: Expected "default.IDENTIFIER"
            break;
    }
}

解析规则

以下是有冲突的规则：

可以完整查看所有规则on GitHub。

`default`

def p_default(p):
    'default : DEFAULT PERIOD identifier'
    p[0] = ('default', p[3])

`switch`

def p_switch_statement(p):
    'switch_statement : SWITCH LPAREN expression RPAREN LCURLY switch_cases RCURLY'
    p[0] = ('switch_statement', p[3], p[6])


def p_switch_case_1(p):
    'switch_case : CASE primary COLON statements_or_empty'
    p[0] = ('switch_case', p[2], p[4])


def p_switch_case_2(p):
    'switch_case : DEFAULT COLON statements_or_empty'
    p[0] = ('default_case', p[3])


def p_switch_cases_1(p):
    'switch_cases : switch_cases switch_case'
    p[0] = p[1] + [p[2]]


def p_switch_cases_2(p):
    'switch_cases : switch_case'
    p[0] = [p[1]]


def p_switch_cases_or_empty(p):
    '''switch_cases_or_empty : switch_cases
                             | empty'''
    p[0] = p[1]

任何有关如何解决此冲突的帮助或指导将不胜感激！提前谢谢你。

Answer 1

你这里有一个简单的 shift/reduce 冲突（标记 default 作为前瞻）被解决为一个班次。

让我们将这一切缩小到一个更小的例子，如果不是最小的话。这是语法，部分基于 OP 中指向的 Github 存储库中的语法（但旨在自包含）：

statements: statements statement |
statement : assign SEMICOLON
          | switch
assign    : lvalue EQUALS expression
switch    : SWITCH LPAREN expression RPAREN LCURLY cases RCURLY
cases     : cases case | 
case      : CASE expression COLON statements
          | DEFAULT COLON statements
expression: ID | INT
lvalue    : ID | DEFAULT

这里的关键是 statement 可能以标记 DEFAULT 开头，而 case 也可能以标记 DEFAULT 开头。现在，假设我们在解析中到达了以下点：

switch ( <expression> ) { <cases> case <expression> : <statements>

所以我们正处于 switch 复合语句的中间；我们已经看到 case 0: 并且我们正在处理一个语句列表。当前状态包括项目（还有几个；我只包括相关的）：

1. statements: statements · statement
2. case      : CASE expression COLON statements ·
3. statement : · assign SEMICOLON
4. assign    : · lvalue EQUALS expression
5. lvalue    : · DEFAULT

项目 2 的前瞻集是 [ RCURLY, DEFAULT, ID ]。

现在假设下一个标记是 default。如果 default 后跟 =，我们可以查看语句的开头。或者我们可以查看一个新的 case 子句，如果 default 后跟 :。但是我们看不到未来的两个标志，只有一个；下一个标记是 default，这就是我们所知道的。

但我们需要做出决定：

如果 default 是语句的开头，我们可以将其移动（第 5 项）。然后当我们看到 = 时，我们将 default 减少到 lvalue 并继续解析 assign.
如果 default 是 case 的开头，我们需要将 CASE expression COLON statements 减少到 case（第 2 项）。然后，在我们最终改变 默认值 之前，我们会将 cases case 减少到 cases。然后我们将移动 : 并继续 DEFAULT COLON statements.

与大多数 LR 解析器生成器一样，PLY 解决了 shift/reduce 有利于移位的冲突，因此它将始终采用上述两个选项中的第一个。如果它随后看到 : 而不是 =，它将报告语法错误。

所以我们所拥有的只是 LR(2) 文法的另一个例子。 LR(2) 文法总是可以重写为 LR(1) 文法，但重写后的文法往往又丑又臃肿。这是一种可能的解决方案，它可能比大多数解决方案都没有那么难看。

使用 EBNF 运算符 |、* 和 +（交替、可选重复和重复）的开关主体是：

switch-body -> (("case" expression | "default") ":" statement*)+

或者，让它不那么麻烦：

case-header -> ("case" expression | "default") ":"
switch-body -> (case-header statement*)+

从接受字符串的角度来看，和

完全一样

switch-body -> case-header (case-header | statement)*

换句话说，一系列事物要么是 case-headers 要么是 statements，其中第一个是 case-header.

这种写规则的方式不能生成正确的解析树；它将 switch 语句的结构简化为语句和 case 标签的集合。但它确实识别完全相同的语言。

从好的方面来说，它具有不强制解析器决定案例原因何时终止的优点。（文法不再有case子句。）所以它是一个简单的LR(1)文法：

switch       : SWITCH LPAREN expression RPAREN LCURLY switch_body RCURLY
switch_body  : case_header
             | switch_body statement
             | switch_body case_header
case_header  : CASE expr COLON
             | DEFAULT COLON

现在，我们可以证明生成的解析树实际上是准确的。 Unrealscript 与 C 共享有关 switch 语句的相同设计决策，其中 case 子句实际上并未定义任何真正意义上的块。它只是一个可以跳转到的标签，并且有条件地跳转到下一个标签。

但是在我们进行的过程中修复解析树实际上并不是特别复杂，因为每次减少到 switch_body 都清楚地表明我们正在添加什么。如果我们要添加一个 case-header，我们可以将一个新列表附加到 case 子句的累积列表中；如果它是一个语句，我们将该语句附加到最后一个 case 子句的末尾。

所以我们可以把上面的规则在PLY中写成大致如下：

def p_switch_body_1(p):
    ''' switch_body  : case_header '''
    p[0] = [p[1]]

def p_switch_body_2(p):
    ''' switch_body  : switch_body statement '''
    # Append the statement to the list which is the last element of
    # the tuple which is the last element of the list which is the
    # semantic value of symbol 1, the switch_body.
    p[1][-1][-1].append(p[2])
    p[0] = p[1]

def p_switch_body_3(p):
    ''' switch_body  : switch_body case_header '''
    # Add the new case header (symbol 2), whose statement list
    # is initially empty, to the list of switch clauses.
    p[1].append(p[2])
    p[0] = p[1]

def p_case_header_1(p):
    ''' case_header  : CASE expr COLON '''
    p[0] = ('switch_case', p[2], [])

def p_case_header_2(p):
    ''' case_header  : DEFAULT COLON '''
    p[0] = ('default_case', [])

正在解决开关块中默认标签的 shift/reduce 冲突

Resolving shift/reduce conflict for default label in switch block

python

lalr

ply

unrealscript

输入

解析规则

`default`

`switch`