Разрешение конфликта сдвига / уменьшения для метки по умолчанию в блоке переключателей

Question

Я пишу парсер для Unrealscript, используя PLY, и столкнулся (надеюсь) с одной из последних неясностей в правилах парсинга, которые я установил.

Unrealscript имеет ключевое слово, default, который используется по-разному в зависимости от контекста. В обычной строке вы можете использовать default вот так:

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

Существует также, конечно, default этикетка для случая 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]

Буду очень признателен за любую помощь или руководство о том, как решить этот конфликт! Заранее спасибо.

Answer 1

Здесь у вас есть простой конфликт сдвига / уменьшения (с токеном default как ожидание) решается как сдвиг.

Давайте сведем все это к гораздо меньшему, если не минимальному примеру. Вот грамматика, частично основанная на той, что в репозитории Github, на которую указывает OP (но она должна быть автономной):

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 ],

Теперь предположим, что следующий токен используется по умолчанию. Мы могли бы посмотреть на начало оператора, если по умолчанию следует символ =. Или мы могли бы посмотреть на новое предложение case, если по умолчанию следует :. Но мы не можем видеть два жетона в будущее, только один; следующий токен по умолчанию, и это все, что мы знаем.

Но нам нужно принять решение:

• Если по умолчанию это начало оператора, мы можем просто сдвинуть его (пункт 5). Затем, когда мы увидим =, мы снизим значение по умолчанию до lvalue и продолжать разбирать assign,

• Если по умолчанию это начало дела, нам нужно уменьшить 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 с или statement с, где первый 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 разделяет то же дизайнерское решение о switch заявления как C, в котором 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', [])