《OGRE 3D 渲染引擎原理与架构》4.3 脚本词法与语法树

脚本编译器前两级:ScriptLexer::tokenize 把文本切成带行号的 token 流(LBRACKET/RBRACKET/COLON/VARIABLE/WORD/QUOTE/NEWLINE),ScriptToken 存 lexeme/type/line;ScriptParser::parse 再把 token 流组装成对象树。lab 复现词法切分与花括号嵌套解析。

4.3 脚本词法与语法树

4.1 节提过编译流水线的第一段是「词法 + 语法」,但没有展开。这一节补上:ScriptLexer 把原始文本切成 token 流,ScriptParser 把 token 流组装成对象树——这两级产物分别叫 token 列表和 CST(Concrete Syntax Tree)。4.2 节的翻译器消费的就是这棵树的更高抽象 AST。

本章与站内既有内容的分工

第 4.1 节讲编译流水线的总装与扩展点,第 4.2 节讲翻译阶段,本节负责最底层两级——文本 → token → 树。OGRE 的这套词法/语法不是通用编译器前端,而是为「对象 + 属性 + 花括号嵌套」这种脚本形态定制的:每个对象有类型名和可选名字,属性是「关键词 + 原子值」,嵌套用 {} 表达。

词法:token 类型与 ScriptToken

ScriptLexer.h 里定义了词法层的全部 token 类型。每种括号/符号/词形对应一个枚举值:

// OgreMain/src/OgreScriptLexer.h:token 类型(v14.6.3 源码摘录,已删减)
    /** These codes represent token IDs which are numerical translations of
        specific lexemes. Specific compilers using the lexer can register their
        own token IDs which are given precedence over these built-in ones.
    */
    enum{
        TID_LBRACKET = 0, // {
        TID_RBRACKET, // }
        TID_COLON, // :
        TID_VARIABLE, // $...
        TID_WORD, // *
        TID_QUOTE, // "*"
        TID_NEWLINE, // \n
        TID_UNKNOWN,
        TID_END
    };

    /** This struct represents a token, which is an ID'd lexeme from the
        parsing input stream.
    */
    struct ScriptToken
    {
        /// This is the lexeme for this token
        String lexeme;
        /// This is the id associated with the lexeme, which comes from a lexeme-token id mapping
        uint32 type;
        /// This holds the line number of the input stream where the token was found.
        uint32 line;
    };
    typedef std::vector<ScriptToken> ScriptTokenList;

token 类型覆盖了 OGRE 脚本语法的全部词形:{/}(对象体)、:(某些格式的分隔符)、$...(变量)、任意词(WORD)、带引号字符串(QUOTE)、换行。注意 TID_NEWLINE——换行在 OGRE 脚本里是有意义的 token,解析器用它判断语句边界。ScriptToken 是词法层的核心数据结构,三件套:lexeme(原始文本)、type(上面的枚举)、line(行号)。行号是错误报告的基础——4.1 节 Error 结构里的 line 字段就来自这里。

ScriptLexer:tokenize

词法层的入口是 ScriptLexer::tokenize——输入原始字符串,输出 token 列表:

// OgreMain/src/OgreScriptLexer.h:ScriptLexer(v14.6.3 源码摘录,已删减)
    class _OgrePrivate ScriptLexer : public ScriptCompilerAlloc
    {
    public:
        /** Tokenizes the given input and returns the list of tokens found */
        static ScriptTokenList tokenize(const String &str, const String &source);
    private: // Private utility operations
        static ScriptTokenList _tokenize(const String &str, const char* source, String& error);
        static void setToken(const String &lexeme, uint32 line, ScriptTokenList& tokens);
        static bool isWhitespace(Ogre::String::value_type c);
        static bool isNewline(Ogre::String::value_type c);
    };

tokenize 是静态方法,签名里多一个 source 参数——这是出错时定位文件名的来源。真正的实现藏在私有的 _tokenize,公开接口 tokenize 做异常包装(把 _tokenize 的 error 转成 OGRE_EXCEPT)。setToken 把单个 token 塞进列表;isWhitespace/isNewline 是两个字符分类器,词法器靠它们跳过空白、识别换行。

词法器的核心循环逻辑(在 _tokenize 里)是:逐字符扫描,遇到 {/}/: 直接产出单字符 token,遇到 " 开始收集带引号的 QUOTE 词,遇到 $ 开始收集 VARIABLE,遇到换行产出 NEWLINE 并递增行号,其他字符累积成 WORD——遇到空白或标点就 flush 一个 WORD token。

语法:ScriptParser 组装对象树

token 流还不是树。ScriptParser 负责把 token 组装成 ConcreteNode:

// OgreMain/src/OgreScriptParser.h:ScriptParser(v14.6.3 源码摘录,已删减)
    class _OgrePrivate ScriptParser : public ScriptCompilerAlloc
    {
    public:
        static ConcreteNodeListPtr parse(const ScriptTokenList &tokens, const String& file);
        static ConcreteNodeListPtr parseChunk(const ScriptTokenList &tokens, const String& file);
    private:
        static const ScriptToken *getToken(ScriptTokenList::const_iterator i, ScriptTokenList::const_iterator end, int offset);
        static ScriptTokenList::const_iterator skipNewlines(ScriptTokenList::const_iterator i, ScriptTokenList::const_iterator end);
    };

两个公开入口:parse 解析完整脚本,parseChunk 解析一个局部块。私有的 getToken 和 skipNewlines 是两个游标工具——getToken 带偏移量取 token(越界返回空指针),skipNewlines 跳过换行 token 找到下一条有效语句。

ConcreteNode 是语法树的节点类型,OGRE 在 OgreScriptCompiler.h 里定义了它。它有三种角色(CNT_OBJECT/CNT_PROPERTY/CNT_ATOM),对象节点有 type/name/children,属性节点有 name/values,原子节点只有一个 value。语法解析的规则可以概括成两句话:

  • 对象 = 两个 WORD(类型 + 名字,名字可省略)后跟 { ... },花括号里的内容递归解析。
  • 属性 = 一个 WORD 后跟若干 WORD/QUOTE/VARIABLE 原子,以换行或 } 结束。

material Red { technique t0 { pass p0 { ambient 0.5 0.5 0.5 } } } 这颗脚本最后就变成 4.2 节翻译器消费的那棵树:material/Red 是根对象,technique/t0、pass/p0 逐级嵌套,ambient 是叶子属性。

源码定位

上游引用固定到 OGRE v14.6.3 源码 。

可运行产物:C++ 最小验证

下面用纯 C++ 复现词法与语法两级:tokenize 处理 {}/:/$var/引号/换行,parse 把 token 流组装成带 cls+name+props+children 的对象树。它与 src/ogre-ext-04-3-script-lexer-parser.cpp 逐字节一致:

// file: src/ogre-ext-04-3-script-lexer-parser.cpp
// tier: L1
// verify: clang++ -std=c++20 -I. src/ogre-ext-04-3-script-lexer-parser.cpp -o bin/ogre-ext-04-3-script-lexer-parser && ./bin/ogre-ext-04-3-script-lexer-parser
//
// 复现脚本词法与语法树(对应 OgreMain/src/OgreScriptLexer.h 44-80 的
//   ScriptToken/tokenize,OgreScriptParser.h 44-52 的 parse/parseChunk,以及
//   OgreScriptCompiler.h 66-73 的 ConcreteNode 与 76-117 的 AbstractNode):
//   词法把脚本切成带行号的 token 流,语法把花括号嵌套组装成对象树,
//   对象 = cls + name,属性 = 名字 + 若干原子值。
// 独立最小验证,非 OGRE 源码。
#include "verify.h"

#include <cstdint>
#include <string>
#include <vector>

namespace ogre_repro {

using String = std::string;

// 对应 OgreScriptLexer.h 44-54 的 token 类型
enum {
  TID_LBRACKET = 0,
  TID_RBRACKET,
  TID_COLON,
  TID_VARIABLE,
  TID_WORD,
  TID_QUOTE,
  TID_NEWLINE,
  TID_UNKNOWN,
  TID_END
};

// 对应 OgreScriptLexer.h 59-68 的 ScriptToken
struct ScriptToken {
  String lexeme;
  uint32_t type;
  uint32_t line;
};

// 对应 OgreScriptLexer.h 74:极简 tokenize,识别 {} : $ " 与空白/换行
std::vector<ScriptToken> tokenize(const String& str) {
  std::vector<ScriptToken> tokens;
  uint32_t line = 1;
  String word;
  bool inQuote = false;
  auto flushWord = [&]() {
    if (!word.empty()) {
      ScriptToken t{word, TID_WORD, line};
      tokens.push_back(t);
      word.clear();
    }
  };
  auto pushSingle = [&](char c, uint32_t type) {
    flushWord();
    ScriptToken t{String(1, c), type, line};
    tokens.push_back(t);
  };
  for (size_t i = 0; i < str.size(); ++i) {
    char c = str[i];
    if (inQuote) {
      if (c == '"') {
        inQuote = false;
        ScriptToken t{word, TID_QUOTE, line};
        tokens.push_back(t);
        word.clear();
      } else {
        word.push_back(c);
      }
      continue;
    }
    if (c == '"') { flushWord(); inQuote = true; continue; }
    if (c == '{') { pushSingle(c, TID_LBRACKET); continue; }
    if (c == '}') { pushSingle(c, TID_RBRACKET); continue; }
    if (c == ':') { pushSingle(c, TID_COLON); continue; }
    if (c == '$') {
      flushWord();
      String var;
      size_t j = i;
      while (j < str.size() && str[j] != ' ' && str[j] != '\t' &&
             str[j] != '\n' && str[j] != '{' && str[j] != '}') {
        var.push_back(str[j]);
        ++j;
      }
      ScriptToken t{var, TID_VARIABLE, line};
      tokens.push_back(t);
      i = j - 1;
      continue;
    }
    if (c == '\n') {
      flushWord();
      ScriptToken t{"\n", TID_NEWLINE, line};
      tokens.push_back(t);
      ++line;
      continue;
    }
    if (c == ' ' || c == '\t') { flushWord(); continue; }
    word.push_back(c);
  }
  flushWord();
  return tokens;
}

// 极简对象树:对应 AbstractNode 的 OBJECT / PROPERTY / ATOM
struct ScriptProperty {
  String name;
  std::vector<String> values;
};
struct ScriptObject {
  String cls;
  String name;
  std::vector<ScriptProperty> props;
  std::vector<ScriptObject> children;
};
struct ParseResult {
  std::vector<ScriptObject> root;
};

// 递归解析对象体:遇到 RBRACKET 返回
void parseBody(const std::vector<ScriptToken>& tokens, size_t& i, ScriptObject& obj) {
  while (i < tokens.size() && tokens[i].type != TID_RBRACKET) {
    if (tokens[i].type == TID_WORD) {
      // 嵌套对象:WORD WORD {(两个词后跟左花括号)
      if (i + 2 < tokens.size() && tokens[i + 1].type == TID_WORD &&
          tokens[i + 2].type == TID_LBRACKET) {
        ScriptObject child;
        child.cls = tokens[i].lexeme;
        child.name = tokens[i + 1].lexeme;
        i += 3;
        parseBody(tokens, i, child);
        obj.children.push_back(child);
      } else {
        // 属性:WORD 后跟若干 WORD 原子
        ScriptProperty prop;
        prop.name = tokens[i].lexeme;
        ++i;
        while (i < tokens.size() && tokens[i].type == TID_WORD) {
          prop.values.push_back(tokens[i].lexeme);
          ++i;
        }
        obj.props.push_back(prop);
      }
    } else {
      ++i;
    }
  }
  if (i < tokens.size() && tokens[i].type == TID_RBRACKET) ++i;
}

// 对应 OgreScriptParser.h 47:token 流 → 根级对象
ParseResult parse(const std::vector<ScriptToken>& tokens) {
  ParseResult out;
  size_t i = 0;
  while (i < tokens.size()) {
    if (tokens[i].type == TID_WORD && i + 1 < tokens.size() &&
        tokens[i + 1].type == TID_WORD) {
      ScriptObject obj;
      obj.cls = tokens[i].lexeme;
      obj.name = tokens[i + 1].lexeme;
      i += 2;
      if (i < tokens.size() && tokens[i].type == TID_LBRACKET) {
        ++i;
        parseBody(tokens, i, obj);
      }
      out.root.push_back(obj);
    } else {
      ++i;
    }
  }
  return out;
}

}  // namespace ogre_repro

int main() {
  using namespace ogre_repro;

  // 词法:material Red { ... } 多行脚本
  String script =
      "material Red {\n"
      "  technique t0 {\n"
      "    pass p0 {\n"
      "      ambient 0.5 0.5 0.5\n"
      "    }\n"
      "  }\n"
      "}\n";
  std::vector<ScriptToken> tokens = tokenize(script);

  // token 总数与换行数(7 行,每行一个 \n)
  CHECK_EQ(tokens.size(), size_t(23));
  uint32_t newlines = 0;
  for (const auto& t : tokens)
    if (t.type == TID_NEWLINE) ++newlines;
  CHECK_EQ(newlines, uint32_t(7));

  // 首 token 是对象类型词
  CHECK(tokens[0].lexeme == "material");

  // 语法:根级一个对象 material/Red
  ParseResult res = parse(tokens);
  CHECK_EQ(res.root.size(), size_t(1));
  CHECK(res.root[0].cls == "material");
  CHECK(res.root[0].name == "Red");

  // 一层嵌套:technique/t0
  CHECK_EQ(res.root[0].children.size(), size_t(1));
  CHECK(res.root[0].children[0].cls == "technique");
  CHECK(res.root[0].children[0].name == "t0");

  // 两层嵌套:pass/p0
  CHECK_EQ(res.root[0].children[0].children.size(), size_t(1));
  CHECK(res.root[0].children[0].children[0].cls == "pass");
  CHECK(res.root[0].children[0].children[0].name == "p0");

  // 属性:ambient 带 3 个原子值
  const ScriptObject& pass = res.root[0].children[0].children[0];
  CHECK_EQ(pass.props.size(), size_t(1));
  CHECK(pass.props[0].name == "ambient");
  CHECK_EQ(pass.props[0].values.size(), size_t(3));

  // 引号:一个 QUOTE token 保留内部空格
  std::vector<ScriptToken> quoteTokens = tokenize("diffuse \"red lit\" 1.0");
  CHECK_EQ(quoteTokens[1].type, uint32_t(TID_QUOTE));
  CHECK(quoteTokens[1].lexeme == "red lit");

  // 变量:$var 成为一个 VARIABLE token
  std::vector<ScriptToken> varTokens = tokenize("$myvar");
  CHECK_EQ(varTokens.size(), size_t(1));
  CHECK_EQ(varTokens[0].type, uint32_t(TID_VARIABLE));
  CHECK(varTokens[0].lexeme == "$myvar");

  return lab::report("4.3 脚本词法与语法树");
}

本机实测(Apple clang 16,clang++ -std=c++20 -Wall):编译通过(零警告),断言 20/20 通过。

小结

  • token 类型含 {/}/:/$变量/WORD/引号/换行,TID_NEWLINE 是有意义的语句边界。
  • ScriptToken 三件套:lexeme/type/line,行号是错误报告的基础。
  • ScriptLexer::tokenize 逐字符扫描产出 token,source 参数用于错误定位。
  • ScriptParser::parse/parseChunk 把 token 流组装成 ConcreteNode 对象树。
  • 语法规则两句话:对象 = 两个词 + {} 递归体,属性 = 一个词 + 若干原子值。

阅读导航:上一节:4.2 材质脚本解析 · 下一节:5.1 实例管理器 。

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图