可以将所有歧义语法转换为歧义语法吗? [英] Can all ambiguous grammars be converted to unambiguous grammars?

问题描述

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

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.

这篇关于可以将所有歧义语法转换为歧义语法吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！