出一道与编译相关的计算理论问题

Question

我们知道,编译程序也是程序,等价于一DFA,接受的是正则语言.可是,我们知道,高级语言代码并非用正则语言编写,那么按理,编译程序是处理不了高级语言的,可是为什么编译程序能够处理呢?

Answer 1

那不是一遍一遍的分析和转换就转换的正则化了么。

Answer 2

这不就是编译原理吗。
转成有限状态机

Answer 3

我要问的是,DFA(有限状态机)只能接受正则语言,而高级语言看起来并不是正则语言,所以它按理不能接受.可是我们发现我们的编译程序(一个DFA)却能很好的接受这些看起来并不是正则语言的高级语言.为什么?

Answer 4

我觉得你的说法有点错误。编译程序不单单等于DFA，接受的也不单单是正则语言。你所说的只是正则语言所对应的编译器。其实，正则语言的表达能力是比较有限的，我们通常用的高级语言，比如C语言，是用上下文无关描述的。

Answer 5

原帖由 cjaizss 于 2009-4-1 21:06 发表
我要问的是,DFA(有限状态机)只能接受正则语言,而高级语言看起来并不是正则语言,所以它按理不能接受.可是我们发现我们的编译程序(一个DFA)却能很好的接受这些看起来并不是正则语言的高级语言.为什么?

不好意思，没看完你的描述。我想问一下，有这样的事情吗？比如？

Answer 6

原帖由 wongyeam 于 2009-4-2 11:27 发表
我觉得你的说法有点错误。编译程序不单单等于DFA，接受的也不单单是正则语言。你所说的只是正则语言所对应的编译器。其实，正则语言的表达能力是比较有限的，我们通常用的高级语言，比如C语言，是用上下文无关描 ...

这一点不会错的,任何可以处理非正则语言的机器只会出现在形式系统中,现实中是不会出现的,只要学过了计算理论就知道其原因.

Answer 7

正则语言的表达能力的确有限,有限状态机的处理能力和正则语言的表达能力一样非常有限.可惜的是,我们周围的一切与数字技术相关的东西其能力都只是有限状态机的能力.