02 词法与语法分析前端本册目标搞清楚源代码文本如何变成语法树——Lexer 如何扫描 Token、LanguageParser 如何用递归下降 优先级爬升建树、红绿树为何能做到编辑时 O(1) 复用、Syntax API 长什么样、语法错误如何恢复。一、要点速览词法Lexer4785 行逐字符扫描产出SyntaxToken序列空白与注释作为Trivia挂在 Token 上不进语法树主体。语法LanguageParser11539 行是手写递归下降分析器二元表达式用优先级爬升precedence climbing而非传统算符优先文法表。红绿树语法树分两层——内部绿节点GreenNode不可变、无父指针、全局缓存与对外红节点SyntaxNodefaçade按需创建。这是 IDE 高性能编辑的关键。错误恢复SyntaxParser.EatToken系列在缺 Token 时插入缺失节点并继续解析保证一棵完整但不完美的树总能产出。所有节点的种类用SyntaxKind枚举ushort标识是贯穿前端的总开关。二、词法分析Lexer2.1 入口与文件文件src/Compilers/CSharp/Portable/Parser/行数职责AbstractLexer.cs—词法器骨架缓冲区、位置管理Lexer.cs4785C# 词法器主体普通 Token、指令#if…、XML 文档注释QuickScanner.cs433快速路径常见 Token标识符、运算符的免分配扫描2.2 主循环Lex()Lexer.cs:235词法器按模式分派普通代码 / 预处理指令 / XML 注释的多种子模式publicSyntaxTokenLex(LexerModemode){_modemode;switch(_mode){caseLexerMode.Syntax:caseLexerMode.DebuggerSyntax:returnthis.QuickScanSyntaxToken()??this.LexSyntaxToken();// L245caseLexerMode.Directive:returnthis.LexDirectiveToken();}// ...XML 文档注释的各种模式L250-276}性能设计值得注意普通代码 Token 先走QuickScanner.cs:193的QuickScanSyntaxToken()——一个手写的、只为最常见 Token 形态服务的快速路径失败才回退到完整的LexSyntaxToken()Lexer.cs:297。这是编译器里典型的快慢双路径优化。2.3 Token 的解剖TokenInfoLexer.cs:84定义了扫描一个 Token 时的临时信息结构internalstructTokenInfo{internalSyntaxKindKind;// SyntaxKind.IdentifierToken / NumericLiteralToken / ...internalSyntaxKindContextualKind;// 上下文关键字如 async在语法阶段的第二身份internalstringText;internalstringStringValue;internalstringIdentifierName;...}ContextualKind值得记住async、partial、var这类上下文关键字在词法阶段仍是普通标识符只是额外登记了可能是关键字的候选身份真正决策推迟到语法/绑定阶段。2.4 Trivia空白与注释的去处语法树的主体只包含有语义的节点空格、换行、注释、预处理指令统称Trivia按规则挂到 Token 上一个 Token 最多带1 个 trailing trivia本行内其后的空白/注释其后直到下一个 Token 之前的所有 trivia 都算它的leading trivia预处理指令#if、#pragma也是结构化 triviaStructuredTriviaSyntax因此 IDE 折叠/着色能精确定位。为什么这样设计——①语法结构不受排版影响树可以任意格式化后再打印②重构重写节点时 trivia 随 Token 走最大程度保留用户格式。三、语法分析LanguageParser3.1 总入口方法Parser/LanguageParser.cs行号作用ParseCompilationUnit()298整个文件入口 →CompilationUnitSyntaxParseStatement()6464语句分派if/for/while/表达式语句…ParseSubExpression(Precedence)8889一切表达式的总入口LanguageParser继承自SyntaxParser.cs1111 行后者封装了从词法器流式取 Token的基础设施EatToken()SyntaxParser.cs:435、PeekToken、前看缓冲等。3.2 递归下降 优先级爬升C# 的语句/声明部分是典型的手写递归下降一个ParseStatement大 switch。表达式则采用优先级爬升核心在LanguageParser.cs:8724的Precedence枚举enumPrecedence:uint{Expression0,// 最宽松接受一切表达式Assignment,LambdaAssignment,// 与赋值同级、右结合语言规范的直接体现Ternary,Coalescing,ConditionalOr,ConditionalAnd,LogicalOr,LogicalXor,LogicalAnd,Equality,Relational,Shift,Additive,Mutiplicative,Unary,Cast,PointerIndirection,AddressOf,Primary_UNUSED,// 基础表达式按 ad-hoc 方式解析}运算符 → 优先级的映射在GetPrecedence(SyntaxKind)L8748。解析循环ParseSubExpressionCoreL8901的工作方式先解析一个操作数基础表达式字面量、标识符、括号…看下一个 Token 是什么运算符查GetPrecedence得newPrecedence若newPrecedence高于或同级且右结合当前precedence就把刚解析的操作数当左操作数递归ParseSubExpression(newPrecedence)解析右侧L9052–9057 的BinaryExpression分支即此循环直至遇到优先级不够的运算符返回。读代码建议在ParseSubExpressionCoreL8901打断点编译a b c * d单步看优先级如何驱动结合方向——这是理解本节最快的方式。3.3 为什么不用语法生成器ANTLR/YaccC# 语法里有大量上下文依赖泛型 vs 比较运算符的歧义、查询表达式、模式匹配手写代码能自然表达试试看式的回溯isDeclaration试探等错误恢复策略需要精细控制见 3.4生成器难以定制性能手写解析器可以针对热路径做QuickScanner这类特化。3.4 错误恢复残缺输入也要长出完整的树语法错误的处理原则是绝不抛异常中断而是EatToken(SyntaxKind kind)SyntaxParser.cs:463/518期望的 Token 不在时产出一个IsMissing的占位 Token 并报告诊断如 CS1002 应输入;解析继续坏 Token 被吞掉并挂为 skipped trivia使后续正确代码仍能进入树因此任何乱码输入都能得到一棵结构完整局部带 Omitted/Skipped 节点的语法树——这是 IDE 在残缺代码上仍能提供补全/绑定的前提。四、红绿树Roslyn 最著名的工程决策4.1 两层节点层基类特征绿节点内部GreenNodesrc/Compilers/Core/Portable/Syntax/GreenNode.cs:17internal abstract不可变没有父指针只存宽度不存绝对位置引用相等即结构相等配合节点缓存红节点对外 APISyntaxNodesrc/Compilers/Core/Portable/Syntax/SyntaxNode.cs:22public abstract partial持父指针与绝对位置Span按需从绿节点包装生成本身轻量C# 特化的红节点基类是CSharpSyntaxNodeSyntax/CSharpSyntaxNode.cs:25publicabstractpartialclassCSharpSyntaxNode:SyntaxNode,IFormattable绿节点版本在Syntax/InternalSyntax/如InternalSyntax/SyntaxToken.cs475 行解析器Parser全程只操作绿节点你用 API 拿到的SyntaxNode都是事后包装的红 façade。4.2 为什么这样能 O(1) 复用树不可变 绿节点无父指针 → 任何未修改的子树在编辑后新树里被原样共享编辑前 CompilationUnit ─ classDecl ─ methodDecl ─ body ─ stmt1, stmt2 编辑 stmt2 CompilationUnit─ classDecl ─ methodDecl─ body ─ stmt1(共享), stmt2(新)ReplaceNode只需沿着路径新建 O(树高) 个绿节点其余全部复用配合Microsoft.CodeAnalysis.CSharp的节点缓存InternalSyntax/CSharpSyntaxNodeCache.cs常见小子树短标识符、小字面量甚至是跨编辑共享的。IDE 每个按键触发一次全量重建语法树因此变得廉价——这是 Roslyn 能支撑现代 IDE 体验的基石。红节点则是另一重缓存parent、Span等派生信息只在被查询时才计算。记住口诀绿管结构不可变、可共享红管导航父指针、位置。4.3 SyntaxKind前端的总开关Syntax/SyntaxKind.cs:6publicenumSyntaxKind:ushort用ushort而非int每个绿节点都要存一个 Kind内存减半在百万节点的树上很可观。树里所有种类——SyntaxKind.ClassDeclaration、SyntaxKind.IdentifierToken、SyntaxKind.WhitespaceTrivia——共用这一个枚举。五、Syntax API 使用者视角速写读懂前两节后这些 API 的行为就有了着落vartreeCSharpSyntaxTree.ParseText(class C { void M() { } });varroot(CompilationUnitSyntax)tree.GetRoot();// 红节点入口varclsroot.Members.OfTypeClassDeclarationSyntax().Single();varmcls.Members.OfTypeMethodDeclarationSyntax().Single();m.Span// 绝对位置红节点派生m.Identifier// SyntaxToken绿色数据的红包装m.Body.OpenBraceToken.LeadingTrivia// 挂在 { 上的前导 triviavarm2m.WithIdentifier(SyntaxFactory.ParseToken(N));// 产生新树旧树不变遍历/改写基础设施全部由红绿树结构免费获得CSharpSyntaxWalkerSyntax/CSharpSyntaxWalker.cs—— visitor 遍历CSharpSyntaxRewriterSyntax/CSharpSyntaxRewriter.cs—— visitor 改写返回新树。六、实验语法树转储用本地构建产物roslyn-src/Binaries/Debug/Dlls/或main/packages中被覆盖过的 2.10 包写一个 30 行的控制台程序// 引用 Microsoft.CodeAnalysis.dll 与 Microsoft.CodeAnalysis.CSharp.dllvartreeCSharpSyntaxTree.ParseText(class C { int x a b * c; },CSharpParseOptions.Default.WithLanguageVersion(LanguageVersion.Latest));tree.GetRoot().WriteTo(Console.Out);// 打印规范化源码Trivia 被剥离的体现foreach(vartokintree.GetRoot().DescendantTokens())Console.WriteLine(${tok.Kind()}{tok.Text} leading{tok.LeadingTrivia});观察三件事①WriteTo输出与原文的空白差异Trivia 不属于结构②a b * c的树形BinaryExpression(Add, a, BinaryExpression(Multiply, b, c))③每个 Token 的 trivia 分布。把LanguageVersion换成CSharp5再跑体会语言版本在语法层就生效某些语法直接报错。七、代码位置索引内容位置相对roslyn-src/src/Compilers/CSharp/Portable/Token 信息结构TokenInfoParser/Lexer.cs:84词法主入口Lex()Parser/Lexer.cs:235完整扫描LexSyntaxToken()Parser/Lexer.cs:297快速路径QuickScanSyntaxToken()Parser/QuickScanner.cs:193语法总入口ParseCompilationUnit()Parser/LanguageParser.cs:298语句分派ParseStatement()Parser/LanguageParser.cs:6464表达式入口ParseSubExpression()Parser/LanguageParser.cs:8889优先级枚举 / 映射Parser/LanguageParser.cs:8724/:8748取 Token 基础设施EatToken系Parser/SyntaxParser.cs:435-533绿节点基类GreenNode../Core/Portable/Syntax/GreenNode.cs:17红节点基类SyntaxNode../Core/Portable/Syntax/SyntaxNode.cs:22C# 红节点基类Syntax/CSharpSyntaxNode.cs:25C# 绿 TokenSyntax/InternalSyntax/SyntaxToken.cs节点缓存Syntax/InternalSyntax/CSharpSyntaxNodeCache.csSyntaxKind枚举Syntax/SyntaxKind.cs:6遍历/改写器Syntax/CSharpSyntaxWalker.cs、Syntax/CSharpSyntaxRewriter.cs语法树实现红 façade 总目录Syntax/CSharpSyntaxTree.cs及同目录各*Syntax.cs下一册03-符号与语义绑定.md——语法树只回答长什么样绑定阶段回答是什么意思。
02 词法与语法分析前端本册目标搞清楚源代码文本如何变成语法树——Lexer 如何扫描 Token、LanguageParser 如何用递归下降 优先级爬升建树、红绿树为何能做到编辑时 O(1) 复用、Syntax API 长什么样、语法错误如何恢复。一、要点速览词法Lexer4785 行逐字符扫描产出SyntaxToken序列空白与注释作为Trivia挂在 Token 上不进语法树主体。语法LanguageParser11539 行是手写递归下降分析器二元表达式用优先级爬升precedence climbing而非传统算符优先文法表。红绿树语法树分两层——内部绿节点GreenNode不可变、无父指针、全局缓存与对外红节点SyntaxNodefaçade按需创建。这是 IDE 高性能编辑的关键。错误恢复SyntaxParser.EatToken系列在缺 Token 时插入缺失节点并继续解析保证一棵完整但不完美的树总能产出。所有节点的种类用SyntaxKind枚举ushort标识是贯穿前端的总开关。二、词法分析Lexer2.1 入口与文件文件src/Compilers/CSharp/Portable/Parser/行数职责AbstractLexer.cs—词法器骨架缓冲区、位置管理Lexer.cs4785C# 词法器主体普通 Token、指令#if…、XML 文档注释QuickScanner.cs433快速路径常见 Token标识符、运算符的免分配扫描2.2 主循环Lex()Lexer.cs:235词法器按模式分派普通代码 / 预处理指令 / XML 注释的多种子模式publicSyntaxTokenLex(LexerModemode){_modemode;switch(_mode){caseLexerMode.Syntax:caseLexerMode.DebuggerSyntax:returnthis.QuickScanSyntaxToken()??this.LexSyntaxToken();// L245caseLexerMode.Directive:returnthis.LexDirectiveToken();}// ...XML 文档注释的各种模式L250-276}性能设计值得注意普通代码 Token 先走QuickScanner.cs:193的QuickScanSyntaxToken()——一个手写的、只为最常见 Token 形态服务的快速路径失败才回退到完整的LexSyntaxToken()Lexer.cs:297。这是编译器里典型的快慢双路径优化。2.3 Token 的解剖TokenInfoLexer.cs:84定义了扫描一个 Token 时的临时信息结构internalstructTokenInfo{internalSyntaxKindKind;// SyntaxKind.IdentifierToken / NumericLiteralToken / ...internalSyntaxKindContextualKind;// 上下文关键字如 async在语法阶段的第二身份internalstringText;internalstringStringValue;internalstringIdentifierName;...}ContextualKind值得记住async、partial、var这类上下文关键字在词法阶段仍是普通标识符只是额外登记了可能是关键字的候选身份真正决策推迟到语法/绑定阶段。2.4 Trivia空白与注释的去处语法树的主体只包含有语义的节点空格、换行、注释、预处理指令统称Trivia按规则挂到 Token 上一个 Token 最多带1 个 trailing trivia本行内其后的空白/注释其后直到下一个 Token 之前的所有 trivia 都算它的leading trivia预处理指令#if、#pragma也是结构化 triviaStructuredTriviaSyntax因此 IDE 折叠/着色能精确定位。为什么这样设计——①语法结构不受排版影响树可以任意格式化后再打印②重构重写节点时 trivia 随 Token 走最大程度保留用户格式。三、语法分析LanguageParser3.1 总入口方法Parser/LanguageParser.cs行号作用ParseCompilationUnit()298整个文件入口 →CompilationUnitSyntaxParseStatement()6464语句分派if/for/while/表达式语句…ParseSubExpression(Precedence)8889一切表达式的总入口LanguageParser继承自SyntaxParser.cs1111 行后者封装了从词法器流式取 Token的基础设施EatToken()SyntaxParser.cs:435、PeekToken、前看缓冲等。3.2 递归下降 优先级爬升C# 的语句/声明部分是典型的手写递归下降一个ParseStatement大 switch。表达式则采用优先级爬升核心在LanguageParser.cs:8724的Precedence枚举enumPrecedence:uint{Expression0,// 最宽松接受一切表达式Assignment,LambdaAssignment,// 与赋值同级、右结合语言规范的直接体现Ternary,Coalescing,ConditionalOr,ConditionalAnd,LogicalOr,LogicalXor,LogicalAnd,Equality,Relational,Shift,Additive,Mutiplicative,Unary,Cast,PointerIndirection,AddressOf,Primary_UNUSED,// 基础表达式按 ad-hoc 方式解析}运算符 → 优先级的映射在GetPrecedence(SyntaxKind)L8748。解析循环ParseSubExpressionCoreL8901的工作方式先解析一个操作数基础表达式字面量、标识符、括号…看下一个 Token 是什么运算符查GetPrecedence得newPrecedence若newPrecedence高于或同级且右结合当前precedence就把刚解析的操作数当左操作数递归ParseSubExpression(newPrecedence)解析右侧L9052–9057 的BinaryExpression分支即此循环直至遇到优先级不够的运算符返回。读代码建议在ParseSubExpressionCoreL8901打断点编译a b c * d单步看优先级如何驱动结合方向——这是理解本节最快的方式。3.3 为什么不用语法生成器ANTLR/YaccC# 语法里有大量上下文依赖泛型 vs 比较运算符的歧义、查询表达式、模式匹配手写代码能自然表达试试看式的回溯isDeclaration试探等错误恢复策略需要精细控制见 3.4生成器难以定制性能手写解析器可以针对热路径做QuickScanner这类特化。3.4 错误恢复残缺输入也要长出完整的树语法错误的处理原则是绝不抛异常中断而是EatToken(SyntaxKind kind)SyntaxParser.cs:463/518期望的 Token 不在时产出一个IsMissing的占位 Token 并报告诊断如 CS1002 应输入;解析继续坏 Token 被吞掉并挂为 skipped trivia使后续正确代码仍能进入树因此任何乱码输入都能得到一棵结构完整局部带 Omitted/Skipped 节点的语法树——这是 IDE 在残缺代码上仍能提供补全/绑定的前提。四、红绿树Roslyn 最著名的工程决策4.1 两层节点层基类特征绿节点内部GreenNodesrc/Compilers/Core/Portable/Syntax/GreenNode.cs:17internal abstract不可变没有父指针只存宽度不存绝对位置引用相等即结构相等配合节点缓存红节点对外 APISyntaxNodesrc/Compilers/Core/Portable/Syntax/SyntaxNode.cs:22public abstract partial持父指针与绝对位置Span按需从绿节点包装生成本身轻量C# 特化的红节点基类是CSharpSyntaxNodeSyntax/CSharpSyntaxNode.cs:25publicabstractpartialclassCSharpSyntaxNode:SyntaxNode,IFormattable绿节点版本在Syntax/InternalSyntax/如InternalSyntax/SyntaxToken.cs475 行解析器Parser全程只操作绿节点你用 API 拿到的SyntaxNode都是事后包装的红 façade。4.2 为什么这样能 O(1) 复用树不可变 绿节点无父指针 → 任何未修改的子树在编辑后新树里被原样共享编辑前 CompilationUnit ─ classDecl ─ methodDecl ─ body ─ stmt1, stmt2 编辑 stmt2 CompilationUnit─ classDecl ─ methodDecl─ body ─ stmt1(共享), stmt2(新)ReplaceNode只需沿着路径新建 O(树高) 个绿节点其余全部复用配合Microsoft.CodeAnalysis.CSharp的节点缓存InternalSyntax/CSharpSyntaxNodeCache.cs常见小子树短标识符、小字面量甚至是跨编辑共享的。IDE 每个按键触发一次全量重建语法树因此变得廉价——这是 Roslyn 能支撑现代 IDE 体验的基石。红节点则是另一重缓存parent、Span等派生信息只在被查询时才计算。记住口诀绿管结构不可变、可共享红管导航父指针、位置。4.3 SyntaxKind前端的总开关Syntax/SyntaxKind.cs:6publicenumSyntaxKind:ushort用ushort而非int每个绿节点都要存一个 Kind内存减半在百万节点的树上很可观。树里所有种类——SyntaxKind.ClassDeclaration、SyntaxKind.IdentifierToken、SyntaxKind.WhitespaceTrivia——共用这一个枚举。五、Syntax API 使用者视角速写读懂前两节后这些 API 的行为就有了着落vartreeCSharpSyntaxTree.ParseText(class C { void M() { } });varroot(CompilationUnitSyntax)tree.GetRoot();// 红节点入口varclsroot.Members.OfTypeClassDeclarationSyntax().Single();varmcls.Members.OfTypeMethodDeclarationSyntax().Single();m.Span// 绝对位置红节点派生m.Identifier// SyntaxToken绿色数据的红包装m.Body.OpenBraceToken.LeadingTrivia// 挂在 { 上的前导 triviavarm2m.WithIdentifier(SyntaxFactory.ParseToken(N));// 产生新树旧树不变遍历/改写基础设施全部由红绿树结构免费获得CSharpSyntaxWalkerSyntax/CSharpSyntaxWalker.cs—— visitor 遍历CSharpSyntaxRewriterSyntax/CSharpSyntaxRewriter.cs—— visitor 改写返回新树。六、实验语法树转储用本地构建产物roslyn-src/Binaries/Debug/Dlls/或main/packages中被覆盖过的 2.10 包写一个 30 行的控制台程序// 引用 Microsoft.CodeAnalysis.dll 与 Microsoft.CodeAnalysis.CSharp.dllvartreeCSharpSyntaxTree.ParseText(class C { int x a b * c; },CSharpParseOptions.Default.WithLanguageVersion(LanguageVersion.Latest));tree.GetRoot().WriteTo(Console.Out);// 打印规范化源码Trivia 被剥离的体现foreach(vartokintree.GetRoot().DescendantTokens())Console.WriteLine(${tok.Kind()}{tok.Text} leading{tok.LeadingTrivia});观察三件事①WriteTo输出与原文的空白差异Trivia 不属于结构②a b * c的树形BinaryExpression(Add, a, BinaryExpression(Multiply, b, c))③每个 Token 的 trivia 分布。把LanguageVersion换成CSharp5再跑体会语言版本在语法层就生效某些语法直接报错。七、代码位置索引内容位置相对roslyn-src/src/Compilers/CSharp/Portable/Token 信息结构TokenInfoParser/Lexer.cs:84词法主入口Lex()Parser/Lexer.cs:235完整扫描LexSyntaxToken()Parser/Lexer.cs:297快速路径QuickScanSyntaxToken()Parser/QuickScanner.cs:193语法总入口ParseCompilationUnit()Parser/LanguageParser.cs:298语句分派ParseStatement()Parser/LanguageParser.cs:6464表达式入口ParseSubExpression()Parser/LanguageParser.cs:8889优先级枚举 / 映射Parser/LanguageParser.cs:8724/:8748取 Token 基础设施EatToken系Parser/SyntaxParser.cs:435-533绿节点基类GreenNode../Core/Portable/Syntax/GreenNode.cs:17红节点基类SyntaxNode../Core/Portable/Syntax/SyntaxNode.cs:22C# 红节点基类Syntax/CSharpSyntaxNode.cs:25C# 绿 TokenSyntax/InternalSyntax/SyntaxToken.cs节点缓存Syntax/InternalSyntax/CSharpSyntaxNodeCache.csSyntaxKind枚举Syntax/SyntaxKind.cs:6遍历/改写器Syntax/CSharpSyntaxWalker.cs、Syntax/CSharpSyntaxRewriter.cs语法树实现红 façade 总目录Syntax/CSharpSyntaxTree.cs及同目录各*Syntax.cs下一册03-符号与语义绑定.md——语法树只回答长什么样绑定阶段回答是什么意思。
