Генератор парсеров Jison, сдвиг уменьшить конфликт грамматики, как решить? - PullRequest
Новая
       54

Генератор парсеров Jison, сдвиг уменьшить конфликт грамматики, как решить?

0 голосов
/ 27 февраля 2020

В настоящее время я работаю над конвертером визуальных основ c, используя jison, и у меня есть эти конфликты в моей грамматике: 

Conflict in grammar: multiple actions possible when lookahead token is ELSE in state 11
- reduce by rule: If -> IfBlock
- shift token (then go to state 16)
Conflict in grammar: multiple actions possible when lookahead token is ELSE_IF in state 11
- reduce by rule: If -> IfBlock
- shift token (then go to state 17)
Conflict in grammar: multiple actions possible when lookahead token is TERMINATOR in state 27
- reduce by rule: IfBlock -> IF Expression THEN Body
- shift token (then go to state 13)
Conflict in grammar: multiple actions possible when lookahead token is TERMINATOR in state 29
- reduce by rule: IfBlock -> IfBlock ELSE_IF Expression THEN Body
- shift token (then go to state 13)

States with conflicts:
State 11
  If -> IfBlock . #lookaheads= $end TERMINATOR IF_END ELSE ELSE_IF SUB_END
  If -> IfBlock .ELSE Body IF_END #lookaheads= $end TERMINATOR IF_END ELSE ELSE_IF SUB_END
  IfBlock -> IfBlock .ELSE_IF Expression THEN Body #lookaheads= $end ELSE ELSE_IF TERMINATOR SUB_END IF_END
State 27
  IfBlock -> IF Expression THEN Body . #lookaheads= $end ELSE ELSE_IF TERMINATOR SUB_END IF_END
  Body -> Body .TERMINATOR Line
  Body -> Body .TERMINATOR
State 29
  IfBlock -> IfBlock ELSE_IF Expression THEN Body . #lookaheads= $end ELSE ELSE_IF TERMINATOR SUB_END IF_END
  Body -> Body .TERMINATOR Line
  Body -> Body .TERMINATOR

Вот упрощенная версия моей грамматики (действия удалены): 

const grammar = {
  Root: [
    [
      ''
    ],
    [
      'Body'
    ]
  ],
  Body: [
    [
      'Line'
    ],
    [
      'Body TERMINATOR Line'
    ],
    [ 'Body TERMINATOR' ]
  ],
  Line: [ [ 'Expression' ], [ 'Statement' ] ],
  Statement: [ [ 'Return' ], [ 'If' ] ],
  Expression: [ [ 'Code' ] ],
  Return: [
    [
      'RETURN Expression'
    ],
    [
      'RETURN'
    ]
  ],
  Code: [
    [
      'SUB_START Identifier PARAM_START ParamList PARAM_END TERMINATOR Body SUB_END'
    ]
  ],
  IfBlock: [
    [
      'IF Expression THEN Body'
    ],
    [
      'IfBlock ELSE_IF Expression THEN Body'
    ]
  ],
  If: [
    [ 'IfBlock' ],
    [
      'IfBlock ELSE Body IF_END'
    ]
  ]
}

Конфликт возникает, когда я пытаюсь реализовать правило для оператора If, похоже, он конфликтует с правилом Body.

Я потратил почти день, пытаясь его решить, но Я не могу Я знаю, что парсер может смотреть только один токен вперед, но я не могу найти решение самостоятельно. И я связан с jison, поэтому я не могу использовать другой генератор парсера. Есть ли обходной путь для моей грамматики?

1 Ответ

1 голос
/ 27 февраля 2020

Глядя на эти произведения: 

If: [
        [ 'IfBlock' ],
        [ 'IfBlock ELSE Body IF_END ']
    ]

Мне кажется, что грамматика говорит, что оператор if должен заканчиваться IF_END , только если включает else пункт. if, в котором отсутствует предложение else, не может быть прервано IF_END.

Это не мое понимание синтаксиса визуальных основ c. END_IF является обязательным в многострочном синтаксисе и не используется в однострочном синтаксисе.

Таким образом, у вас есть два конфликта, потому что ваша If продукция принимает некоторые операторы с END_IF и некоторые без:

  • Для if операторов без END_IF имеется двусмысленность classi c "dangling else".

  • Кроме того, для многострочного В операторах if без END_IF грамматика не позволяет определить, является ли следующий оператор частью последнего предложения в операторе if или новым оператором. (Вот почему многострочным if операторам необходимо END_IF.

Неоднозначность «висячее другое» относительно мягкая, то есть нормальное разрешение, которое предпочитает сдвиг для уменьшения, приведет к правильный результат. Если вы хотите устранить сообщение об ошибке, вы можете сделать разрешение явным, используя правила приоритета, давая ELSE и ELSE_IF более высокий приоритет, чем IF. Чтобы использовать эту технику, вы должны сделать IF видимым в правилах, которые зависят от приоритета, что в основном означает удаление IF из IfBLock, чтобы оставить вас с: 

IfBlock: [
  [ 'Expression THEN Body' ],
  [ 'IfBlock ELSE_IF Expression THEN Body' ]
],
If: [
  [ 'IF IfBlock' ],
  [ 'IF IfBlock ELSE Body' ]  // IF_END removed
]

Вам также понадобятся отношения приоритета: 

[ 'left', 'IF' ],
[ 'left', 'ELSE', 'ELSE_IF' ]

Это более или менее заставит вас переходить на однострочные операторы if, за исключением того, что вам нужно заменить Block чем-то, что не позволяет TERMINATOR.

для многострочных if операторов. однако вам потребуется другой синтаксис:

  • END_IF является обязательным

  • Должен быть TERMINATOR после THEN и ELSE, а б прежде ELSE и END_IF. Другими словами, блоки операторов в многострочном if должны начинаться с начала строки и заканчиваться TERMINATOR.

Эти ограничения не являются только косметическими c: они есть, потому что в противном случае невозможно поместить оператор после многострочного if, поскольку без END_IF любое последующее утверждение будет добавлено к последнему предложению THEN или ELSE.

...