2017-02-23 2 views
0

В настоящее время я пишу грамматику LALR (1), подобную Visual Basic, и сталкиваюсь с этим конкретным конфликтом смены/сокращения, о котором я не знаю, как правильно его решить.Сдвиг/уменьшение LALR (1) конфликт из-за круглых скобок

проблемные части грамматики (смотрите EDIT 1 и EDIT 2 разъяснений):

Expression 
    : IndexExpression 
    | /* other expressions */ 

IndexExpression 
    : MemberExpression 
    | MemberExpression '(' ArgumentList ')' 

MemberExpression 
    : ParenthesizedExpression 
    | Identifier 

ParenthesizedExpression 
    : '(' Expression ')' 

ArgumentList 
    : Expression 
    | Expression ',' ArgumentList 
    | ',' ArgumentList 

И сдвиг/свертка конфликта заключается в следующем:

State 109 
    237 ParenthesizedExpression: '(' Expression ')' . 
    $default reduce using rule 237 (ParenthesizedExpression) 

... 
State 295 

    231 IndexExpression: MemberExpression '(' . ArgumentList ')' 
    237 ParenthesizedExpression: '(' . Expression ')' 
    ... 
    Expression go to state 352 

... 
State 352 
    182 ArgumentList: Expression . 
    183    | Expression . ',' ArgumentList 
    237 ParenthesizedExpression: '(' Expression . ')' 
    ... 
    ')' shift, and go to state 109 

    ')' [reduce using rule 182 (ArgumentList)] 

Другими словами, синтаксический анализатор не уверен, столкнувшись с выражением, заключенным в круглые скобки, независимо от того, является ли он ArgumentList с одним expre ssion или ParenthesizedExpression.

Есть ли способ исправить этот конфликт, сохраняя при этом грамматику LALR (1)?

спасибо.

EDIT 1:

/* другие выражения */в Expression на самом деле не пустое выражение, я просто написал ее таким образом, для краткости. В действительности у него есть другие альтернативные выражения:

Expression 
    : IndexExpression 
    | Expression '+' Expression 
    | ... 

EDIT 2:

Вот дополнительные части грамматики, которая @rici указывает, может быть проблематичным (особенно 1-го правила правой части Заявление):

Statement 
    : MemberExpression ArgumentList 
    | MemberExpression '=' Expression 
    | MemberExpression '(' ArgumentList ')' '=' Expression 
    | ... 
+0

Вам нужно больше показать свою грамматику. Или, что еще лучше, создайте пересобираемую грамматику с той же проблемой, но только несколько производств. Кстати, синтаксис 'argument_list' очень странный. Почему вы считаете полезным писать его с лево-рекурсией, чего обычно следует избегать в парсерах LALR (1)? И что означают множественные недостающие аргументы? И если все остальные аргументы могут быть опущены, почему последний не может быть? – rici

+1

Вы разрешаете синтаксис VB, где функции, которые принимают один аргумент, могут вызываться без круглых скобок? Если это так, это, вероятно, ваша проблема. – rici

+0

@rici ** отсутствующие аргументы **: в этом конкретном диалекте VB он позволяет иметь список аргументов с пустыми аргументами, кроме самого последнего. Поскольку я действительно не хочу, чтобы выражение_Expression_ было пустым, я положил это третье правило на _ArgumentList_. ** один аргумент без круглых скобок **: да! Фактически после погружения глубже, чтобы найти основную причину вчера, я пришел к выводу, что это может быть причиной. Есть ли у вас предложение о том, как включить этот синтаксис? –

ответ

2

ошибки, потому что Expression позволено быть пустым, из-за закомментированного правило /* other expressions */, nd считается непустым.

Ниже показано, где использование Expression результатов в двух эквивалентных правил:

ArgumentList 
    : Expression 
    | Expression ',' ArgumentList /* degenerates into "',' ArgumentList" */ 
    | ',' ArgumentList 
    ; 

Число сдвига/уменьшения конфликтов являются количество раз ArgumentList ссылается используется (один раз в IndexExpression и дважды в ArgumentList сама)

Чтобы удалить конфликты либо исправить ArgumentList для случая пустого Expression:

ArgumentList 
    : Expression 
    | ArgumentList ',' Expression 
    ; 

Или убедитесь, что Expression никогда не пуст (удалите комментарий).

+0

Привет, kdhp, пожалуйста, ознакомьтесь с моим Редактированием 1 для уточнения. Извините за то, что я неоднозначен в своем оригинальном посте. –

+1

@SamTatasurya Без просмотра списка выражений я могу только предположить, что либо есть другое пустое значение, оператор не был объявлен как '% left' /'% right', либо существует второе правило для ''(' Expression ') '' (также присутствуют через «IndexExpression-> MemeberExpression-> ParenthesizedExpression') – kdhp

Смежные вопросы