2

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

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

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

当然，还有语句的defaultcase 标签switch：

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

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

输入

class Example extends Object;

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

解析规则

以下是冲突的规则：

所有规则都可以在 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]

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

4

1 回答 1

2

您在这里所拥有的是一个简单的移位/减少冲突（将令牌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

这里的关键是 astatement可能以 token 开头DEFAULT，而 acase也可能以 token 开头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 expression COLON statements到case（第 2 项）。然后，我们将减少cases case到cases最终转移default. 然后我们将移动:并继续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-headers要么是statements，其中第一个是 a 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 与 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', [])
于 2016-10-01T22:10:35.163 回答