解析器和词法分析器的共同点：

1. 他们从输入中读取一些 字母的 符号。 __

   • 提示：字母表不一定是字母。但它必须是解析器/词法分析器理解的语言的 原子符号。
   • 词法分析器的符号：ASCII 字符。
   • 解析器的符号：特定的标记，它们是语法的终结符号。

   • 他们分析这些 符号 并尝试将它们与他们理解的语言的 语法相匹配。

   • 这通常是真正的区别所在。有关更多信息，请参见下文。

   • 词法分析器理解的语法：常规语法（乔姆斯基的第 3 级）。
   • 解析器理解的语法：上下文无关语法（乔姆斯基的第 2 级）。

   • 他们将 语义 （意义）附加到他们找到的语言片段上。

   • 词法分析器通过将 词 位（来自输入的符号字符串）分类为特定 标记 来附加意义。例如，所有这些词位：*, ==, <=,^将被 C/C++ 词法分析器归类为“运算符”标记。

   • 解析器通过将输入（句子）中的标记字符串分类为特定的 非终结符 并构建 解析树 来附加含义。例如，所有这些标记字符串：[number][operator][number], [id][operator][id],[id][operator][number][operator][number]将被 C/C++ 解析器归类为“表达式”非终结符。

   • 他们可以为识别的元素附加一些额外的含义（数据）。

   • 当词法分析器识别出构成正确数字的字符序列时，它可以将其转换为二进制值并与“数字”标记一起存储。

   • 类似地，当解析器识别出一个表达式时，它可以计算它的值并与语法树的“表达式”节点一起存储。

   • 他们都在他们的输出中产生了他们所认识的语言的正确 句子 。

   • 词法分析器产生 标记 ，它们是它们识别的 常规语言的 句子。 每个标记都可以有一个内部语法（尽管是 3 级，而不是 2 级），但这对于输出数据和读取它们的数据并不重要。 __

   • 解析器产生 句法树 ，它们是它们识别的 上下文无关语言的 句子的表示。 通常整个文档/源文件只有一棵大树，因为整个文档/源文件对他们来说是一个合适的 句子 。但是解析器无法在其输出中生成一系列语法树是没有任何原因的。例如，它可以是一个解析器，它可以识别粘贴在纯文本中的 SGML 标签。所以它会将SGML 文档 标记 为一系列标记：. __[TXT][TAG][TAG][TXT][TAG][TXT]...

如您所见，解析器和分词器有很多共同点。一个解析器可以是另一个解析器的分词器，它将其输入记号读取为它自己的字母表中的符号（记号只是某些字母表的符号），就像来自一种语言的句子可以是其他一些更高级别的字母符号一样语言。例如，如果*和-是字母表的符号M（作为“莫尔斯电码符号”），那么您可以构建一个解析器，将这些点和线的字符串识别为莫尔斯电码中编码的字母。“摩尔斯电码”语言中的句子可能是其他解析器的
标记 ，这些 标记 是其语言的原子符号（例如“英语单词”语言）。这些“英语单词”可能是一些理解“英语句子”语言的高级解析器的标记（字母表的符号）。而
所有这些语言的不同之处仅在于语法的复杂性 。而已。

那么这些“乔姆斯基的语法水平”到底是怎么回事？好吧，诺姆乔姆斯基根据语法的复杂性将语法分为四个级别：

• 第 3 级：常规语法

它们使用正则表达式，也就是说，它们只能由字母符号 ( a, b)、它们的连接符号 ( ab, aba, bbbetd.) 或替代符号
(例如a|b) 组成。
它们可以实现为有限状态自动机 (FSA)，如 NFA（非确定性有限自动机）或更好的 DFA（确定性有限自动机）。
常规语法无法处理 嵌套语法 ，例如正确嵌套/匹配的括号(()()(()()))、嵌套的 HTML/BBcode
标记、嵌套块等。这是因为处理它的状态自动机应该有无限多的状态来处理无限多的嵌套级别。

• 第 2 级：上下文无关文法

它们的语法树中可以有嵌套的、递归的、自相似的分支，因此它们可以很好地处理嵌套结构。
它们可以实现为带有堆栈的状态自动机。此堆栈用于表示语法的嵌套级别。在实践中，它们通常被实现为自上而下的递归下降解析器，它使用机器的过程调用堆栈来跟踪嵌套级别，并对其语法中的每个非终端符号使用递归调用的过程/函数。
但是它们无法处理 上下文相关的
语法。例如，当您有一个表达式时x+3，在一个上下文中，这x可能是一个变量的名称，而在其他上下文中，它可能是一个函数的名称等。

• 级别 1：上下文相关的语法

• 0 级：无限制文法

  也称为递归可枚举文法。