Skip to main content
 首页 » 编程设计

python之解决开关 block 中默认标签的移位/减少冲突

2025年04月02日9dflying

我正在使用 PLY 为 Unrealscript 编写解析器,并且(希望)遇到了我设置的解析规则中的最后一个歧义。

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

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

当然,还有 default switch 的案例标签声明:
switch (i) { 
    case 0: 
        break; 
    default: 
        break; 
} 

遇到 default 时解析有歧义它认为是 case 内的标签的语句 block 。这是一个遇到解析错误的示例文件:

输入
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] 

任何有关如何解决此冲突的帮助或指导将不胜感激!先感谢您。

请您参考如下方法:

您在这里所拥有的是一个简单的移位/减少冲突(使用 token 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可能以 token DEFAULT 开头, 和 case也可以从 token DEFAULT 开始.现在,假设我们在解析中达到了以下几点:
switch ( <expression> ) { <cases> case <expression> : <statements> 

所以我们在 switch 中间复合语句;我们见过 case 0:我们正在制定一份声明 list 。当前状态包括项目(还有一些;我只包括相关的):
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 ] .

现在假设下一个 token 是默认的。如果默认值后跟 =,我们可以查看语句的开头。或者我们可以查看一个新的 case 子句,如果默认值后跟 :。但我们看不到 future 的两种代币,只有一种;下一个 token 是默认的,这就是我们所知道的。

但我们需要做出决定:
  • 如果默认值是语句的开头,我们可以移动它(第 5 项)。然后当我们看到 = 时,我们会将默认值减少为 lvalue并继续解析assign .
  • 如果默认是一个case的开头,我们需要减少CASE expression COLON statements至case (第 2 项)。然后我们将减少 cases case至cases在我们最终改变默认值之前。然后我们将移动 : 并继续 DEFAULT COLON statements .

  • 与大多数 LR 解析器生成器一样,PLY 解决了移位/减少冲突以支持移位,因此它将始终采用上述两个选项中的第一个。如果它看到 : 而不是 =,它将报告语法错误。

    所以我们所拥有的只是 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-header s 或 statement s,其中第一个是 case-header .

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

    从好的方面来说,它具有不强制解析器决定案例原因何时终止的优点。 (文法不再有 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 与 switch 有着相同的设计决策。语句为 C,其中 case从句实际上并没有定义任何真正意义上的 block 。它只是一个可以跳转到的标签,并有条件地跳转到下一个标签。

    但实际上修复解析树并不是特别复杂,因为每次减少到 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', [])