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 是叶子属性。
源码定位
OgreMain/src/OgreScriptLexer.h:token 类型枚举(44-54)、ScriptToken(59-68)、ScriptLexer(70-80)、tokenize(74)OgreMain/src/OgreScriptParser.h:ScriptParser(44-52)、parse(47)、parseChunk(48)
上游引用固定到 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 实例管理器 。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。