Каков правильный способ преобразования EBNF в BNF при использовании парсера GLR?

Question

EBNF как этот

Goal = Stmt 
Stmt = "if" "expr" "then" Stmt ("else" Stmt)? 
Stmt = "S" 

Должен ли я конвертировать это

Goal = Stmt 
X = "else" Stmt 
Stmt = "if" "expr" "then" Stmt | "if" "expr" "then" Stmt X 
Stmt = "S" 

Или

Goal = Stmt 
Stmt = "if" "expr" "then" Stmt | "if" "expr" "then" Stmt "else" Stmt 
Stmt = "S" 

Являются ли эти два BNF означают то же самое, чтобы РВО парсер?

------------------------ СОДЕРЖАНИЕ APPEND -------------------- ----------

Если lexes являются

"if" "expr" "then" "if" "expr" "then" "S" "else" "S" 

РВО анализатор должен получить два дерева

Goal 
    Stmt 
     "if" 
     "expr" 
     "then" 
     Stmt 
      "if" 
      "expr" 
      "then" 
      Stmt 
       "S" 
     "else" 
     Stmt 
      "S" 

И

Goal 
    Stmt 
     "if" 
     "expr" 
     "then" 
     Stmt 
      "if" 
      "expr" 
      "then" 
      Stmt 
       "S" 
      "else" 
      Stmt 
       "S" 

Но первый преобразованный BNF может получить только первое дерево, потому что, когда он встречается с, конфликта нет в сокращении/смене, конфликт наступает на X.

Второй BNF будет иметь конфликт с уменьшением/он соответствует "else", поэтому синтаксический анализатор разбивается на два потока для разбора в разных условиях.

Я прав? Есть ли какой-нибудь ACTION, генератор GOTO TABLE, который будет обрабатывать первый BNF так же, как второй?

Answer 1

Они являются эквивалентными грамматиками и будут анализировать один и тот же язык.

Ваша грамматика с X использует только Х в одном месте. Чистый эффект такой, как если бы тело X было заменено, где X ссылается. На практике наличие X-продукции заставит анализатор сделать немного больше работы. Если вы не хотите приложить семантическое действие к сокращению для X, эта дополнительная работа не покупает ничего в эффективности.

В той степени, в которой использование такого одноразового использования делает грамматику более пригодной для обслуживания, это полезно делать. В такой небольшой грамматике я не вижу смысла. В практических грамматиках (у нас есть GLR-грамматика для IBM COBOL с 5000 постановлениями [обвинять IBM, а не нас]), такое структурирование может быть весьма полезным, а дополнительные служебные наработки не имеют значения.