“最弱的正式语言”是什么意思

Question

我正在研究 Alex Aiken 的编译器设计。在研究解析器幻灯片时，Alex 说“常规语言是最弱的正式语言”。

来自优酷视频

任何人都可以请澄清这一点！提前致谢。

Answer 1

他的意思可能是在乔姆斯基家族的底层。这意味着使用只能解决常规问题（如正则表达式匹配）的设备，您永远不可能希望模拟更复杂的语言或像正常的计算机一样运行通用软件。最高级别（在图表中）比“常规”强大得多，称为“递归可枚举”。描述可通过“图灵机”或任何现代计算机处理器解决的问题类别。

编辑：刚刚看了视频，这绝对是他暗指的，但是，如果他有更实用的角度。他没有教你 CS 理论（尽管这会有助于学习我在上面链接的理论）。

他的角度更实际，他只是告诉你，就编译代码的能力而言，Regular 是其中最不强大的。以下是他比较的正式语言：

• 递归可枚举
• 上下文无关
• 上下文敏感
• 常规的

常规是最不强大的，而其他的则更强大。他接着在视频的其余部分解释了常规语言的局限性。