Попытка решить зависание else для грамматики Mini-C

У меня есть эта грамматика:

translation_unit 
    ::= external_declaration
    | translation_unit external_declaration

external_declaration 
    ::= function_definition
    | declaration

function_definition 
    ::= type_specifier declarator compound_statement
    | STATIC type_specifier declarator compound_statement

declaration 
    ::= type_specifier declarator ';'
    | EXTERN type_specifier declarator ';'

declaration_list_opt 
    ::= declaration_list
    | empty
    
declaration_list
    ::= declaration_list declaration
    | declaration

type_specifier 
    ::= INT
    | CHAR

declarator 
    ::= direct_declarator
    | ASTERISK declarator

direct_declarator 
    ::= ID
    | direct_declarator '(' parameter_type_list ')'
    | direct_declarator '(' ')'

parameter_type_list 
    ::= parameter_list ',' ELLIPSIS
    | parameter_list

parameter_list 
    ::= parameter_list ',' parameter_declaration
    | parameter_declaration

parameter_declaration 
    ::= type_specifier declarator

compound_statement 
    ::= '{' declaration_list_opt statement_list '}'
    | '{' declaration_list_opt '}'

expression_statement 
    ::= expression ';'

expression 
    ::= equality_expression

expression 
    ::= equality_expression '=' expression
    | equality_expression '+=' expression
    | equality_expression '-=' expression
    | equality_expression '*=' expression
    | equality_expression '/=' expression
    | equality_expression '%=' expression

equality_expression 
    ::= relational_expression

equality_expression 
    ::= equality_expression '==' relational_expression
    | equality_expression '!=' relational_expression

relational_expression 
    ::= additive_expression

relational_expression 
    ::= relational_expression '<'  additive_expression
    | relational_expression '>'  additive_expression
    | relational_expression '<=' additive_expression
    | relational_expression '>=' additive_expression

postfix_expression 
    ::= primary_expression
    | postfix_expression '(' argument_expression_list ')'
    | postfix_expression '(' ')'
    | postfix_expression '[' expression ']'


argument_expression_list 
    ::= argument_expression_list ',' expression
    | expression

unary_expression 
    ::= postfix_expression
    | '-' unary_expression
    | '+' unary_expression
    | '!' unary_expression
    | '*' unary_expression
    | '&' unary_expression

mult_expression 
    ::= unary_expression

mult_expression 
    ::= mult_expression '*' unary_expression
    | mult_expression '/' unary_expression
    | mult_expression '%' unary_expression

additive_expression 
    ::= mult_expression
    | additive_expression '+' mult_expression
    | additive_expression '-' mult_expression

primary_expression 
    ::= ID
    | INUMBER
    | FNUMBER
    | CHARACTER
    | string_literal
    | '(' expression ')'
    
string_literal 
    ::= string_literal STRING
    | STRING

statement 
    ::= compound_statement
    | expression_statement
    | selection_statement
    | iteration_statement
    | jump_statement

jump_statement 
    ::= RETURN ';'
    | RETURN expression ';'
    | BREAK ';'
    | CONTINUE ';'

iteration_statement 
    ::= WHILE '(' expression ')' statement
    | FOR '(' expression_statement expression_statement expression ')' statement

selection_statement 
    ::= IF '(' expression ')' statement
    | IF '(' expression ')' statement ELSE statement
    
statement_list 
    ::= statement_list statement
    | statement

Когда я реализовал синтаксический анализатор с помощью Sly, он говорит, что selection_statement имеет конфликт с уменьшением сдвига.

Я пытаюсь решить это без использования приоритета.

Я пытался использовать что-то вроде этого:

@_("matched",
   "unmatched")
   def selection_statement(self, p):
      pass
    
@_("IF '(' expression ')' matched ELSE matched")
   def matched(self, p):
      pass

@_("IF '(' expression ')' matched",
   "IF '(' expression ')' unmatched",
   "IF '(' expression ')' matched ELSE unmatched")
   def unmatched(self, p):
      pass

Но у него бесконечная рекурсия по совпадению.

Я попытался добавить другие операторы для сопоставления, чтобы решить рекурсию, но это только порождает больше конфликтов.

Что я должен использовать, чтобы исключить рекурсию?

Это канонический пример конфликта сдвиг/редукция. Например, это тот, который используется в руководстве Bison для обсуждения проблемы. Чтобы реализовать семантику C для привязки else к самому внутреннему соответствию if, вы разрешаете конфликт путем сдвига, который Bison использует по умолчанию для всех конфликтов сдвига/уменьшения. Я не знаю, как сказать Слаю сделать то же самое.

John Bollinger 03.04.2023 17:17

Разве это не вопрос Python? Грамматика может быть C-подобной, но кодирование на Python и Sly. А разве Слай не на пенсии?

Tom Karzes 03.04.2023 18:29

@TomKarzes: Sly написан (и используется) на Python, но, вероятно, это не относится к этой ситуации.

Sean Duggan 03.04.2023 22:07

@JohnBollinger: Sly автоматически переключается, но отображает предупреждение. Я пытаюсь удалить предупреждение.

Juan_2054 03.04.2023 23:21

@Juan_2054: Тогда вам нужно сделать свою грамматику однозначной. Как бы вы обработали вложенный оператор if с единственным оператором else?

Sean Duggan 04.04.2023 00:01

@SeanDuggan Я хочу связать это с ближайшим if.

Juan_2054 04.04.2023 00:07

Документация Sly неплохая. Он содержит раздел, посвященный работе с двусмысленностью. Я склонен предположить, что, объявив ELSE более приоритетным, чем IF, вы удовлетворите Sly, что ему не нужно предупреждать.

John Bollinger 04.04.2023 02:39

@SeanDuggan В сообщении есть два типа кода: (1) Sly и (2) Python (встроенный в код Sly, но видимый непосредственно). В сообщении нет кода C. Следовательно, применяются языковые теги «Sly» и «Python».

Tom Karzes 04.04.2023 03:02

@TomKarzes: Похоже, они пытаются внедрить C в Sly, но я признаю, что они не так много говорят.

Sean Duggan 04.04.2023 05:12

@SeanDuggan Название поста описывает его как «грамматику Mini-C», поэтому, предположительно, это упрощенное подмножество C.

Tom Karzes 04.04.2023 07:23
Стоит ли изучать PHP в 2026-2027 годах?
Стоит ли изучать PHP в 2026-2027 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
4
10
97
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Я нашел ответ. Мне просто пришлось изменить мою грамматику, чтобы она выглядела так:

statement 
    ::= matched
    | unmatched

matched 
    ::= if_matched
    | iteration_statement_matched
    | compound_statement
    | expression_statement
    | jump_statement

unmatched
    ::= if_unmatched
    | iteration_statement_unmatched

if_matched 
    ::= IF '(' expression ')' matched ELSE matched

if_unmatched 
    ::= IF '(' expression ')' statement
    | IF '(' expression ')' matched ELSE unmatched

iteration_statement_matched 
    ::= WHILE '(' expression ')' matched

iteration_statement_matched 
    ::= FOR '(' expression_statement expression_statement expression ')' matched

iteration_statement_unmatched 
    ::= WHILE '(' expression ')' unmatched

iteration_statement_unmatched 
    ::= FOR '(' expression_statement expression_statement expression ')' unmatched

Я использовал этот пост в качестве справки: Конфликт Shift/reduce в чашке java - проблема с болтающимся остатком

Рад, что вы решили это! Вы сможете принять свой ответ через 48 часов после того, как вопрос был задан (я думаю, вы можете принять ответы других в течение 10 минут). Есть ли шанс, что вы можете опубликовать код Sly, с которым вы столкнулись, чтобы помочь другим в будущем?

Sean Duggan 04.04.2023 17:27

@SeanDuggan Конечно. Когда закончу, загружу.

Juan_2054 04.04.2023 23:36

Другие вопросы по теме