regex - 试图理解解析和扫描（reg. 语言和 cf 语言的区别）

Question

首先，我不学习计算机科学，我只是对这个学科感兴趣。

解析器基本上做到了这一点：

1. 读取输入
2. 创建令牌
3. 实际解析令牌并创建一个 AST

所以我认为为了确定一个单词是否是常规语言，你使用 FSM，而对于 CF 语言，你需要一个解析器，因为可能存在递归结构。因此，存在用于常规语言的扫描器生成器和用于 CF 语言的解析器生成器。

但是现在我读到你可以为正则表达式构建一个递归的体面解析器：

http://matt.might.net/articles/parsing-regex-with-recursive-descent/

那么这一切是如何结合在一起的呢？

为什么我需要解析常规语言？我认为有限状态机就足够了？

例如，如果我想识别 java 程序中的块注释（即/* .. */），我只需要编写一个 FSM，所以基本上是一个 switch-case-statement。我不需要解析器...

感谢您的帮助和澄清！

Answer 1

正则表达式可以匹配的内容与解析正则表达式所需的内容之间存在差异。例如，正则表达式可以包含嵌套组，因此您无法使用正则表达式解析这些组。例如，您必须“计算”嵌套的括号对，这超出了常规语言的能力。

另请参阅：是否有表示正则表达式的正则语言。