乔姆斯基层次结构和编程语言 [英] chomsky hierarchy and programming languages

问题描述

我正在尝试学习与编程语言相关的Chomsky层次结构的某些方面，而我仍然必须阅读《龙书》.

I'm trying to learn some aspects of the Chomsky Hierarchy which are related to programming languages, and i still have to read the Dragon Book.

我已经读到大多数编程语言都可以解析为上下文无关文法(CFG).就计算能力而言，它等于下推式不确定性自动机之一.我说的对吗?

I've read that most programming languages can be parsed as a context free grammar (CFG). In term of computational power, it equals the one of a pushdown non deterministic automaton. Am I right?

如果这是真的，那么CFG如何保存一个无限制的语法(UG)，该语法即将完成?我之所以问是因为，即使CFG描述了编程语言，它们实际上也被用来描述图灵机，因此是通过UG.

If it's true, then how could a CFG hold an unrestricted grammar (UG), which is turing complete? I'm asking because, even if programming languages are described by CFGs, they are actually used to describe turing machines, and so via an UG.

我认为这是因为至少有两个不同的计算级别，第一个是CFG的解析着重于与语言结构(表示?)有关的语法，而另一个则着重于语义(从某种意义上讲，数据本身的解释?)与正在完善的编程语言的功能有关.同样，这些假设对吗?

I think that's because of at least two different levels of computing, the first, which is the parsing of a CFG focuses on the syntax related to the structure ( representation ? ) of the language, while the other focuses on the semantic ( sense, interpretation of the data itself ? ) related to the capabilities of the programming language which is turing complete. Again, are these assumptions right?

推荐答案

我已经读到大多数编程语言都可以解析为上下文无关文法(CFG).就计算能力而言，它等于下推式不确定性自动机之一.我说的对吗?

I've read that most programming languages can be parsed as a context free grammar (CFG). In term of computational power, it equals the one of a pushdown non deterministic automaton. Am I right?

从技术上讲，是的.有用，没有.

至少有两种有用的方式来思考这些问题:

There are at least two useful ways to think about these questions:

• 如果您要考虑一组字符串，则使用的是语言.
• 如果您正在考虑一种算法来确定字符串是否在某种语言中，那么您将遇到决策问题.

• If you're thinking of a set of strings, you have a language.
• If you're thinking about an algorithm to decide whether a string is or is not in a language, you have a decision problem.

困难在于，尽管大多数编程语言都具有易于通过上下文无关的语法描述的基础结构(Tcl是一个有趣的例外)，但许多由上下文无关的语法描述的句子实际上并没有在该语言中"是指该语言中的有效程序".这些多余的句子通常被某种形式的静态语义排除.例如，以下话语是C程序的上下文无关语法中的一个句子，但它本身并不是有效C程序集中的句子:

The difficulty is that while most programming languages have an underlying structure that is easily described by a context-free grammar (Tcl being an interesting exception), many sentences that are described by the context-free grammar are not actually "in the language," where by "in the language" I mean "a valid program in the language in question." These extra sentences are usually ruled out by some form of static semantics. For example, the following utterance is a sentence in the context-free grammar of C programs but it is not itself in the set of valid C programs:

int f(void) { return n + 1; }

这里的问题是n不在范围内. C需要使用前声明"，并且该属性不能使用上下文无关的语法来表示.

The problem here is that n is not in scope. C requires "declaration before use", and that property cannot be expressed using a context-free grammar.

一种真正的编程语言的典型决策过程是编译器或解释器的前端的一部分，它至少包含两个部分:一个是 parser ，在决策能力上等同于下推式自动机；但第二种方法会进行额外的检查，以排除许多言语是无效的.如果这些检查需要任何类型的使用前定义"属性，则不能通过下推自动机或无上下文语法来完成.

A typical decision procedure for a real programming language is part of the front end of a compiler or interpreter, and it has at least two parts: one, the parser, is equivalent in decision power to a pushdown automaton; but the second does additional checks which rule out many utterances as invalid. If these checks require any kind of definition-before-use property, they can't be done by a pushdown automaton or context-free grammar.

如果是真的，那么CFG如何保存一个无限制的语法(UG)，该语法即将完成?

If it's true, then how could a CFG hold an unrestricted grammar (UG), which is turing complete?

CFG不会保留"任何内容，而只是描述一种语言.

A CFG doesn't "hold" anything—it simply describes a language.

...即使CFG描述了编程语言，它们实际上也用于描述图灵机，因此是通过UG.

... even if programming languages are described by CFGs, they are actually used to describe turing machines, and so via an UG.

您在这里跳过了一些重要的间接访问级别.

You're skipping past some important levels of indirection here.

我认为这是因为至少有两个不同的计算级别，第一个是CFG的解析着重于与语言结构(表示?)有关的语法，而另一个则着重于语义(从某种意义上讲，数据本身的解释?)与正在完善的编程语言的功能有关.同样，这些假设对吗?

I think that's because of at least two different levels of computing, the first, which is the parsing of a CFG focuses on the syntax related to the structure ( representation ? ) of the language, while the other focuses on the semantic ( sense, interpretation of the data itself ? ) related to the capabilities of the programming language which is turing complete. Again, are these assumptions right?

对我来说，它们似乎有些混乱，但您的方向正确.一个关键问题是"语言和编程语言之间有什么区别?"答案是编程语言具有计算解释.计算解释的种类很多，但并非全部都是图灵完备的. 但是魔术在于解释，而不是语法，因此Chomsky层次结构在这里并不是很相关.

They seem a bit muddled to me, but you're on the right track. A key question is "what's the difference between a language and a programming language?" The answer is that a programming language has a computational interpretation. Computational interpretations come in many fine varieties, and not all of them are Turing-complete. But the magic is in the interpretation, not in the syntax, so the Chomsky hierarchy is not very relevant here.

为了证明我的观点，举了一个极端的例子:常规语言[1-9][0-9]*在以下解释下是图灵完备的:

To prove my point, an extreme example: the regular language [1-9][0-9]* is Turing-complete under the following interpretation:

• SK组合器语言是图灵完整的.
• 仅有许多SK程序.
• 可以轻松地对它们进行唯一性和确定性的枚举.
• 因此，我们可以将每个正整数与SK程序相关联.
• 如果我们以标准方式将数字序列解释为正整数，那么我们可以很好地将相同的数字序列解释为SK程序，而且，可以表达任何个SK程序使用有限的数字序列.

• The SK-combinator language is Turing complete.
• There are only countably many SK programs.
• They can easily be enumerated uniquely and deterministically.
• Therefore we can associate each positive integer with an SK program.
• If we interpret a sequence of digits as a positive integer in the standard way, we can equally well interpret the same sequence of digits as an SK program, and moreover, any SK program can be expressed using a finite sequence of digits.

因此整数文字的语言是图灵完备的.

Therefore the language of integer literals is Turing-complete.

如果现在不疼，那就应该了.

If your head doesn't hurt now, it should.

这篇关于乔姆斯基层次结构和编程语言的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！