эта грамматика неоднозначна

Question

Я хочу, чтобы преобразовать эту грамматику к однозначному грамматики:

S -> if E then S 
    | if E then S else S 
    | a 
E -> b 

Я нашел решение, которое является более сложным, чем мое решение, но я не уверен, если мое решение является правильным:

S -> if E then T else S 
    | if E then S 
    | a 
T -> if E then T else T 
    | a 
E -> b 

Это мое решение правильно?

Answer 1

Это выглядит хорошо для меня. Это на самом деле не сильно отличается от стандартного раствора:

stmt  : matched | unmatched 
matched : "if" expr "then" matched "else" matched 
      | other_stmt 
unmatched : "if" expr "then" unmatched 
      | "if" expr "then" matched "else" unmatched 

Преимущества стандартного решения является то, что other_stmt (a в вашей грамматике) не дублируется, а грамматика проще расширить с другими операторами соединения. Например, если мы добавим заявление while:

stmt  : matched | unmatched 
matched : "if" expr "then" matched "else" matched 
      | "while" matched 
      | other_stmt 
unmatched : "if" expr "then" unmatched 
      | "if" expr "then" matched "else" unmatched 
      | "while" unmatched