可以将所有歧义语法转换为歧义语法吗?

本文介绍了可以将所有歧义语法转换为歧义语法吗?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

有些语法可以通过左递归转换为明确的语法.有没有不能转换为明确语法的语法?

There are grammars we convert to unambiguous by using left recursion. Are there grammars that cannot be converted to unambiguous grammars?

推荐答案

大多数实用语言都有明确的上下文无关语法(忽略上下文敏感功能，例如变量声明，空格敏感度等).

There are unambiguous context-free grammars for most practical languages (ignoring context-sensitive features such as variable declarations, whitespace sensitivity, etc.).

但是在给定歧义文法的情况下，没有算法可以找到歧义文法.而且，甚至没有一种算法可以肯定地告诉您给定的语法是否模棱两可.这些都是不确定的问题.

But there is no algorithm which can find an unambiguous grammar given an ambiguous grammar. Furthermore, there is not even an algorithm which can tell you for certain whether a given grammar is ambiguous. These are both undecidable problems.

而且，要回答您的问题，是的，有无上下文的语言，没有明确的语法.这类语言被称为天生就有歧义.

And, to answer your question, yes there are context-free languages for which there is no unambiguous grammar. Such languages are said to be inherently ambiguous.