context-free-grammar - 这个语法有歧义吗

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