字节面试必问的红黑树

• Package：解析出 package 关键字的位置，1:1 指的是位置在第一行的第一个。
• Name：解析出 package name 的名称，类型是 *ast.Ident，1:9 指的是位置在第一行的第九个。
• Decls：节点的顶层声明，其对应 BadDecl(Bad Declaration)、GenDecl(Generic Declaration)、FuncDecl(Function Declaration)。
• Scope：在此文件中的函数作用域，以及作用域对应的对象。
• Imports：在此文件中所导入的模块。
• Unresolved：在此文件中未解析的标识符。
• Comments：在此文件中的所有注释内容。

可视化后的语法树如下：
 

再根据所输出的 Token 稍加思考，做对比，就可得知其仅是单纯的利用扫描器翻译和输出。而实质上在识别记号时，扫描器也会完成其他工作，例如把标识符放到符号表，将数字、字符串常量存放到文字表等。

词法分析产生的记号一般可以分为如下几类：

• 关键字。
• 标识符。
• 字面量(包含数字、字符串等)。
• 特殊符合(如加号、等号)

语法分析/语义分析

语法分析器

语法分析器(Grammar Parser)将对扫描器所产生的记号进行语法分析，从而产生语法树(Syntax Tree)，也称抽象语法树(Abstract Syntax Tree，AST)。

常见的分析方式是自顶向下或者自底向上，以及采取上下文无关语法(Context-free Grammer)作为分析手段。这块可参考一些计算机理论的资料，涉及的比较广。

但语法分析仅完成了对表达式的语法层面的分析，但并不清楚这个语句是否真正有意义，还需要一步语义分析。

语义分析器

语义分析器(Semantic Analyzer)将会对对语法分析器所生成的语法树上的表达式标识具体的类型。主要分为两类：

• 静态语义：在编译器就可以确定的语义。
• 动态语义：在运行期才可以确定的语义。

在经过语义分析阶段后，整个语法树的表达式都会被标识上类型，如果有些类型需要进行隐式转换，语义分析程序将会在语法书中插入相应的转换点，成为有更具体含义的语义。

实战演练

语法分析器生成的语法树，本质上就是以表达式(Expression)为节点的树。在 Go 语言中可通过 go/token、go/parser、go/ast 等相关方法生成语法树，代码如下：

（编辑：淮安站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!