Slang 编译器解析歧义消除两阶段解析设计与局部变量作用域实现【免费下载链接】slangMaking it easier to work with shaders项目地址: https://gitcode.com/GitHub_Trending/sl/slang本文深入解析 Slang 着色器语言编译器docs/design/parsing.md为消除语法歧义而设计的两阶段解析two-stage parsing架构第一阶段仅解析声明结构、将函数体以原始 token 形式暂存为UnparsedStmt第二阶段由语义检查semantic checking驱动按需解析函数体从而用语义信息取代猜是泛型还是小于号的启发式。读者读完本文后将掌握 Slang 解析器中歧义消解的完整决策流程、局部变量作用域hiddenFromLookup机制的底层实现以及针对 decl 级表达式的后续演进方向UnparsedExpr与ScopeRef并可直接对照源码继续深入。一、问题背景教科书式前端无法消解歧义典型的编译器前端text-book style front-end通常划分为三个阶段词法分析tokenization、语法分析parsing、语义检查semantic checking。Slang 的原始设计遵循这一模式但这种设计存在一个固有缺陷解析阶段缺少语义信息无法有效消除语法歧义。最典型的例子是表达式Xab(5)在不预先知道X是什么的前提下解析器无法确定它应该被理解为以5为参数调用泛型函数X即Xab(5)其中ab是泛型特化参数列表还是条件X a与b 5之间的逻辑与运算即Xa b(5)被读作(Xa) (b5)。这两种解读对应完全不同的 AST而解析器在语义检查之前根本没有足够信息做出正确选择。二、初始方案源自 C# 编译器的启发式消歧2.1 启发式规则与 generic specialization followersSlang 最初用一套启发式heuristic解决这个问题当编译器看到IDENTIFIER后紧跟时先尝试将表达式按泛型特化generic specialization解析如果解析成功再检查闭合之后的下一个 token 是否属于泛型特化跟随符generic specialization follower集合若属于则判定这是一个泛型特化表达式。完整的跟随符集合为::、.、(、)、[、]、:、,、?、;、、!、和。这套判断逻辑在源码中体现为tryParseGenericApp中对试探解析后下一个 token 的switch判断source/slang/slang-parser.cpp// otherwise, we speculate as generics, and fallback to comparison when parsing failed TokenSpan tokenSpan; tokenSpan.m_begin parser-tokenReader.m_cursor; tokenSpan.m_end parser-tokenReader.m_end; // Setup without diagnostic lexer, or SourceLocationLine output // as this sink is just to *try* generic application DiagnosticSink newSink(parser-sink-getSourceManager(), nullptr); Parser newParser(*parser); newParser.sink newSink; /* auto speculateParseRs */ parseGenericApp(newParser, base); if (newSink.getErrorCount() 0) { // disambiguate based on FOLLOW set switch (peekTokenType(newParser)) { case TokenType::Scope: // :: case TokenType::Dot: // . case TokenType::LParent: // ( case TokenType::RParent: // ) case TokenType::LBracket: // [ case TokenType::RBracket: // ] case TokenType::Colon: // : case TokenType::Comma: // , case TokenType::QuestionMark: // ? case TokenType::Semicolon: // ; case TokenType::OpEql: // case TokenType::OpNeq: // ! case TokenType::OpGreater: // case TokenType::OpRsh: // case TokenType::EndOfFile: return parseGenericApp(parser, base); } } return base;注意这段代码的实现细节试探解析使用了一个独立的DiagnosticSinknewSink和一份拷贝的ParsernewParser因此即使试探失败也不会污染主解析器的诊断输出或推进主 token 流——这是一个可回滚speculate的试探机制。2.2 启发式的适用前提与 Slang 中的失效这套启发式源自 C# 编译器。它在 C# 中表现良好因为C# 不允许泛型值参数因此Xab...或Xay...永远不会是合法的泛型特化——只可能是比较运算符启发式不会误判。但 Slang 的泛型参数可以是int 或 bool 等值类型value arguments这意味着ab和ay都可能是合法的泛型实参。虽然同样的启发式在大多数情况下仍能工作但当启发式失败时例如用户的表达式恰好让试探解析成功、跟随 token 又命中跟随符集合就会产生大量令用户困惑的误解析。三、系统性解法两阶段解析Two-stage Parsing要系统性地解决歧义前提是让解析器能访问语义信息如果解析器知道X是不是泛型就能毫无猜测地解析表达式。关键在于在解析进行的同时让语义信息可用。Slang 通过将解析拆分为两个阶段实现这一点。3.1 第一阶段声明解析decl parsing stage在第一阶段解析器像往常一样解析所有声明struct、变量、函数等唯一的例外是当即将解析函数体时只收集{与}之间的全部 token存入一个原始 token 列表作为一个UnparsedStmtAST 节点。通过推迟函数体的解析编译器不再需要在函数体内猜测是泛型特化还是小于比较。UnparsedStmt节点的定义位于 source/slang/slang-ast-stmt.h// A statement that we arent going to parse or check, because // we want to let a downstream compiler handle any issues FIDDLE() class UnparsedStmt : public Stmt { FIDDLE(...) // The tokens that were contained between { and } ListToken tokens; Scope* currentScope nullptr; Scope* outerScope nullptr; SourceLanguage sourceLanguage; };除了原始 token 列表外该节点还保存了currentScope、outerScope和sourceLanguage为第二阶段重新解析时恢复正确的语义上下文做准备。收集函数体 token 的实现在parseOptBody中source/slang/slang-parser.cpp其核心是一个braceDepth计数器用于精确配对花括号auto unparsedStmt parser-astBuilder-createUnparsedStmt(); unparsedStmt-currentScope parser-currentScope; unparsedStmt-outerScope parser-outerScope; unparsedStmt-sourceLanguage parser-getSourceLanguage(); parser-FillPosition(unparsedStmt); ListToken tokens unparsedStmt-tokens; int braceDepth 0; for (;;) { auto token parser-ReadToken(); if (token.type TokenType::EndOfFile) break; if (token.type TokenType::LBrace) braceDepth; else if (token.type TokenType::RBrace) braceDepth--; tokens.add(token); if (braceDepth 0) break; } Token eofToken; eofToken.type TokenType::EndOfFile; eofToken.loc parser-tokenReader.peekLoc(); tokens.add(eofToken); return unparsedStmt;两个阶段在源码中被建模为ParsingStage枚举source/slang/slang-parser.cppenum class ParsingStage { Decl, Body, };ParserOptions中默认stage ParsingStage::Body而parseSourceFile从声明阶段开始每个Parser实例都通过getStage()感知自己当前处于哪个阶段。3.2 第二阶段语义驱动的函数体解析body parsing stage第一阶段结束后编译器得到的是只含声明结构、不含函数体的 AST。基于这份初始 AST 即可开始语义检查semantic checking。当语义检查访问到UnparsedStmt节点时语义访问器semantic visitor会派生出一个SemanticsVisitor子上下文subVisitor调用parseUnparsedStmt重新解析暂存的 token将新Parser初始化为Body解析阶段把语义访问器的指针传给新解析器。这条从语义检查触发第二遍解析的调用链实现在SemanticsVisitor::maybeParseStmt中source/slang/slang-check-decl.cppStmt* SemanticsVisitor::maybeParseStmt(Stmt* stmt, const SemanticsContext context) { if (auto unparsedStmt asUnparsedStmt(stmt)) { // Parse the statement now, and check it. SemanticsVisitor subVisitor(context); TokenList tokenList; tokenList.m_tokens _Move(unparsedStmt-tokens); return parseUnparsedStmt( m_astBuilder, subVisitor, getShared()-getTranslationUnitRequest(), unparsedStmt-sourceLanguage, tokenList, getShared()-getSink(), unparsedStmt-currentScope, unparsedStmt-outerScope); } return stmt; }而parseUnparsedStmt本体source/slang/slang-parser.cpp则负责构造处于Body阶段的Parser并把语义 visitor 挂接到parser.semanticsVisitor上ParserOptions options {}; options.stage ParsingStage::Body; // ... 继承 EnableEffectAnnotations / AllowGLSL / LanguageServer / CoreModule 等编译选项 ... Parser parser(astBuilder, tokens, sink, outerScope, options); parser.currentScope outerScope; parser.namePool translationUnit-getNamePool(); parser.sourceLanguage sourceLanguage; parser.semanticsVisitor semanticsVisitor; parser.currentScope parser.currentLookupScope currentScope; parser.currentModule semanticsVisitor-getShared()-getModule()-getModuleDecl(); return parser.parseBlockStatement();从这里可以清楚看到第二阶段的启动方式解析器持有语义 visitor 指针且新解析出的语句会作为函数体重新挂回decl-bodymaybeParseStmt的返回值随后由checkStmt完成完整检查。maybeParseStmt的调用点包括visitSeqStmtsource/slang/slang-check-stmt.cpp和函数体检查入口source/slang/slang-check-decl.cpp保证顺序语句与函数体在检查前都被补解析。3.3 第二阶段中解析与检查的有机交织第二阶段中解析和语义检查是**有机交织interleaved**的不再存在解析与检查之间干净的分界线。但需要注意第二阶段中发生的检查是**按需on-demand**的只检查确定前表达式类型所必需的最小代码片段与消歧无关的其他代码保持未检查状态一旦函数体解析完成作用于该函数的语义访问器会保证遍历解析出的 AST 的每一个节点完成全部检查。visitUnparsedStmt的语义访问器实现是空的source/slang/slang-check-stmt.cpp这正是因为真正的解析工作已由maybeParseStmt提前完成节点本身无需再处理。四、语义驱动的消歧决策流程在第二阶段解析中每当遇到需要消歧时解析器会调用语义 visitor 检查之前已解析出的表达式。核心实现是tryParseGenericAppsource/slang/slang-parser.cpp决策逻辑如下4.1 基于CheckTerm的类型判定static Expr* tryParseGenericApp(Parser* parser, Expr* base) { Name* baseName nullptr; BaseGenericKind baseKind BaseGenericKind::Unknown; if (parser-semanticsVisitor) { // If we have access to a semantic visitor, we can check the base // and see if it refers to a generic. auto checkedBase parser-semanticsVisitor-CheckTerm(base); if (auto declRefExpr asDeclRefExpr(checkedBase)) { if (declRefExpr-declRef.isGenericDecl()) { baseKind BaseGenericKind::Generic; } else if ( declRefExpr-declRef.isFunctionDeclBase() || declRefExpr-declRef.isAggTypeDeclBase()) { // If declref is a function or type, even if it is not a generic, // we should parse the as a generic application for better error // messages. ... baseKind BaseGenericKind::Generic; } else { baseKind BaseGenericKind::NonGeneric; } } else if (auto overloadedExpr asOverloadedExpr(checkedBase)) { baseKind BaseGenericKind::NonGeneric; for (auto candidate : overloadedExpr-lookupResult2) { if (candidate.declRef.isGenericDecl() || candidate.declRef.isFunctionDeclBase() || candidate.declRef.isAggTypeDeclBase()) { baseKind BaseGenericKind::Generic; break; } } } ... }消歧结果通过BaseGenericKind枚举表达Unknown/Generic/NonGeneric决策规则为前表达式的检查结果决策类型检查成功是引用泛型声明的DeclRefExpr按泛型特化解析是OverloadedExpr且任一候选是泛型声明按泛型特化解析检查为引用变量variable或属性property按比较运算符解析是非泛型函数或类型FunctionDeclBase/AggTypeDeclBase仍按泛型特化解析无法正确检查或检查结果未知回退到启发式方法消歧4.2 宁可报错也要按泛型解析的设计取舍一个值得注意的设计决策是当前的表达式被检查为非泛型函数或类型时编译器仍然按泛型特化解析。源码注释说明了原因source/slang/slang-parser.cppIf declref is a function or type, even if it is not a generic, we should parse theas a generic application for better error messages. This is because functions or types can never precede ain valid Slang code, and it is more likely that the user assumed the function or type is generic by mistake.也就是说在合法的 Slang 代码中函数或类型名之后永远不会紧跟作为比较运算符因此用户极有可能是把非泛型函数/类型误当作泛型使用。此时按泛型特化解析可以让诊断信息直接指向该类型/函数不是泛型这一真实错误而不是在稍后某个位置报出令人困惑的语法错误。这是用更好的诊断换取猜测的典型工程取舍。4.3 无语义 visitor 时的回退路径当没有语义 visitor 可用时例如第一阶段解析 decl 级表达式tryParseGenericApp退化为更简单的查找与猜测source/slang/slang-parser.cppelse { // Without a semantic visitor, we fallback to a more simplistic lookup // and guessing. if (auto varExpr asVarExpr(base)) baseName varExpr-name; // if base is a known generics, parse as generics if (baseName isGenericName(parser, baseName)) baseKind BaseGenericKind::Generic; }isGenericNamesource/slang/slang-parser.cpp在没有语义 visitor 的情况下直接对当前作用域执行lookUp仅当查找结果是唯一的GenericDecl时才判定为泛型查找结果无效或存在重载时都不判定为泛型。之后若baseKind仍为Unknown则进入 2.1 节描述的试探解析 FOLLOW set启发式。五、局部变量作用域hiddenFromLookup机制5.1 问题同一块内的变量可见性两阶段解析引出了另一个与作用域相关的问题局部变量应只在其声明之后的同块代码中可见。考虑文档中的经典例子static int input 100; int f() { input 2; // global input is now 2 int input input 1; // local input is now 3 input input 2; // local input is now 5 return input; // returns 5. }其中第一条语句input 2必须访问全局input因为此时局部input尚未声明而后面的语句访问局部input。5.2 常规方案为何行不通Slang 的实现中每个BlockStatement对应创建一个ScopeDecl容器节点块内的变量声明全部注册到同一个ScopeDecl。这与两阶段解析产生冲突为了在消歧时能对任何表达式进行检查变量必须在解析到的那一刻就插入作用域但这样一来当函数体整体解析完成后进行完整检查时块内所有变量都已注册在作用域中——检查块内靠前的语句时也会查找到靠后声明的变量编译器将无法报告使用了后声明变量的错误。在例子中检查第一条语句input 2时查找逻辑会命中局部input而非全局input从而生成错误代码。文档中讨论了一个候选解法让每个局部变量声明拥有自己的作用域该作用域在所属块结束时终止使声明之后的语句成为该变量DeclStmt的子节点static int input 100; int f() { input 2; // global input is now 2 { int input input 1; // local input is now 3 input input 2; // local input is now 5 return input; // returns 5. } }这能保证作用域数据结构与变量的语义作用域一致并产生正确的诊断。但这种表示会在 AST 中形成很深的嵌套链导致查找效率低下且深层 AST 有栈溢出stack overflow风险。因此 Slang 最终没有采用这一方案。5.3hiddenFromLookup标记方案Slang 的最终方案是保持所有变量注册在同一块的同一ScopeDecl中但在每个VarDecl上维护一个独立的布尔状态hiddenFromLookup用于标记该声明是否对查找可见。该字段定义在 source/slang/slang-ast-base.hbool hiddenFromLookup false;配合另一个关键的声明检查状态DeclCheckState::ReadyForParserLookup完整机制分为两个阶段解析阶段所有 decl 默认可见。具体地当Parser处于Body阶段且持有语义 visitor 时每解析出一个局部变量声明就将其置为ReadyForParserLookup伪状态使其在消歧查找中可见source/slang/slang-parser.cppif (parser-semanticsVisitor parser-getStage() ParsingStage::Body) { // When we are in a deferred parsing stage for function bodies, // we will mark all local var decls as ReadyForParserLookup so they can // be returned via lookup. // Note that our lookup logic will ignore all unchecked decls, but during // parsing we dont want to ignore them, so we mark them as ReadyForParserLookup // here, which is a pseudo state that is only used during parsing. // Before checking the decl in semantic checking, we will mark them back as // Unchecked. decl-checkState DeclCheckState::ReadyForParserLookup; }检查阶段当函数体解析完成、准备检查某个BlockStmt时先遍历块内所有DeclStmt将其声明的 decl 标记为hiddenFromLookup true不可见然后按顺序检查子语句当检查过程遇到某个DeclStmt时才将该声明重新标记为可见使其能被其后代码的查找逻辑发现。对应实现位于 source/slang/slang-check-stmt.cppvoid SemanticsStmtVisitor::visitBlockStmt(BlockStmt* stmt) { // Make sure to fully check all nested agg type decls first. if (stmt-scopeDecl) { for (auto aggDecl : stmt-scopeDecl-getDirectMemberDeclsOfTypeAggTypeDeclBase()) { ensureAllDeclsRec(aggDecl, DeclCheckState::DefinitionChecked); } // Consider this code: // // { // int a 5 b; // should error. // int b 3; // } // // In order to detect the error trying to use b before its declared within // a block, our lookup logic contains a condition that ignores a decl if its // hiddenFromLookup field is set to true. // See _lookUpDirectAndTransparentMembers(). // This field will be set to false when we reach the decl through the DeclStmt. // if (auto seqStmt asSeqStmt(stmt-body)) { for (auto subStmt : seqStmt-stmts) { if (auto declStmt asDeclStmt(subStmt)) { if (auto decl asDecl(declStmt-decl)) decl-hiddenFromLookup true; } } } } checkStmt(stmt-body); }而visitDeclStmt在检查到声明语句时将其恢复可见source/slang/slang-check-stmt.cppvoid SemanticsStmtVisitor::visitDeclStmt(DeclStmt* stmt) { // When we encounter a declaration during statement checking, // we expect that it hasnt been checked yet (because otherwise // it would be referenced before its declaration point), but // we will bottleneck through the ensureDecl() path anyway, // to unify with the rest of semantic checking. ensureDeclBase(stmt-decl, DeclCheckState::DefinitionChecked, this); if (auto decl asDecl(stmt-decl)) { decl-hiddenFromLookup false; ... } }查找逻辑侧_isUncheckedLocalVarsource/slang/slang-lookup.cpp把hiddenFromLookup视为未检查的局部变量static bool _isUncheckedLocalVar(const Decl* decl) { auto checkStateExt decl-checkState; auto isUnchecked checkStateExt.getState() DeclCheckState::Unchecked || checkStateExt.isBeingChecked() || decl-hiddenFromLookup; return isUnchecked isLocalVar(decl); }被判定为未检查局部变量的 decl 会在_lookUpDirectAndTransparentMembers等查找路径中被跳过从而实现声明点之前不可见的语义。这套方案以一个布尔字段 检查前的批量隐藏 声明点处的逐次放行在尊重局部变量语义作用域的同时避免了为语句序列构造长链作用域 AST兼顾了正确性与实现简洁性。5.4 当前实现的已知局限两阶段解析技术对函数体内的代码消歧效果良好但当前实现并非 100% 万无一失位于 decl 级别的表达式——例如结构体成员默认值、函数参数的默认值——仍在第一阶段使用启发式方法完整解析。文档指出这在实际中问题较小因为默认值通常是简单表达式误消歧的概率远低于函数体。六、未来工作展望文档为两阶段解析规划了两个明确的技术演进方向6.1 将分阶段解析扩展到 decl 作用域UnparsedExpr将两阶段解析进一步推广到全局/声明作用域以正确支持结构体成员默认值表达式、函数及全局/成员变量的类型表达式。策略是改变第一阶段对表达式的解析方式不再直接解析表达式而是在不深入理解语法的情况下识别表达式的 token 边界将所有表达式解析为UnparsedExpr节点内含每个表达式的未解析 token。这样第一阶段的 AST 仍足够详细可以识别类型与函数的名称及其是否为泛型基于初始 AST 进行语义检查由语义检查驱动任何UnparsedExpr与UnparsedStmt的解析与检查。这实际上是把语义驱动解析从函数体推广到所有表达式层面。6.2 用ScopeRef取代hiddenFromLookup可变状态另一个演进方向是消除hiddenFromLookup标志引入更不可变immutable的 AST 表示。核心概念是ScopeRef一个Scope*加一个endIndex用于标记所引用作用域的边界。这样块内不同语句可以持有指向同一个作用域但不同末尾成员索引的ScopeRef通过ScopeRef查找时若找到的变量在作用域中的索引大于endIndex则视为不可见并报错该方案更干净能产生更好的错误信息且无需在 Decl 上维护可变状态标志。这一设计思想用作用域 边界索引的不可变快照替代可变开关在编译器工程中具有通用参考价值。七、总结Slang 的解析歧义消除方案可以概括为一条清晰的演进路径启发式阶段IDENTIFIER 先按泛型特化试探再依据跟随符集合::.()[]:,?;!判定——源自 C#但对允许泛型值参数的 Slang 并不完备两阶段解析第一阶段把函数体暂存为UnparsedStmtsource/slang/slang-ast-stmt.h语义检查通过maybeParseStmt→parseUnparsedStmtsource/slang/slang-check-decl.cpp、source/slang/slang-parser.cpp触发第二阶段tryParseGenericAppsource/slang/slang-parser.cpp借助CheckTerm对前的表达式做类型判定从机制上消除了函数体内的歧义作用域配套机制以hiddenFromLookupsource/slang/slang-ast-base.hReadyForParserLookup状态在保持单ScopeDecl结构的前提下精确模拟局部变量的声明点可见性source/slang/slang-check-stmt.cpp、source/slang/slang-lookup.cpp演进方向UnparsedExpr将分阶段解析推广到 decl 级表达式ScopeRef以不可变方式替代可变标志。这套设计说明了一个编译器工程中的普适原则当语法无法自洽消歧时与其无限堆叠启发式规则不如重构解析与语义检查的边界让语义信息在解析阶段按需可用。对于希望深入 Slang 前端实现source/slang/slang-parser.cpp、source/slang/slang-check-stmt.cpp、source/slang/slang-lookup.cpp的读者本文提到的每个机制都可在对应源码与行号处直接验证。【免费下载链接】slangMaking it easier to work with shaders项目地址: https://gitcode.com/GitHub_Trending/sl/slang创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考