Tim Sweeney在想什么？(这个C++解析器是如何工作的？)

Question

Epic MegaGames的Tim Sweeney是Unreal的首席开发人员和编程语言极客.许多年前发布了以下屏幕截图到VoodooExtreme:

作为C++程序员和Sweeney粉丝,我被这个迷住了.它显示了通用的C++代码,它实现了某种脚本语言,在这种语言中,语言本身似乎是通用的,因为它可以定义自己的语法.

斯威尼先生从不解释自己.:-)

很少见到这种级别的模板编程,但是当人们想要推动编译器生成优秀的代码或者因为他们想要创建通用代码(例如,现代C++设计)时,你确实会看到它.

Tim似乎正在使用它在Parser.cpp中创建语法 - 您可以看到优先级二元运算符的外观.如果是这种情况,那么为什么Test.ae看起来也在定义语法？

显然这是一个需要解决的难题.胜利用这个代码的工作版本或者最合理的解释来回答,或者如果蒂姆斯威尼发表了答案,他就会自己.:-)

Answer 1

我通过电子邮件向Sweeney先生询问并收到了这个回答:

C++代码使用我编写的实现解析器组合器的模板类.我们的想法是从一些基本的解析器开始,例如文字,其中PLit <'A'>解析文字字符'A',PAny <>解析任何字符,但如果失败,PEof会失败,除非我们不是在文件的结尾,等等.然后我们将它们合并使用像p和组合程序,它解析,然后b和成功只有两个成功的任意树木 - 否则它无法用解析点不为所动.如果成功,结果是一个包含两个字段的结构,一个用于a的结果,另一个用于b的结果.等等.

由于多种原因,C++中的实现很混乱,包括模板不支持任意可变参数,如果没有第一类lambda,我们就无法轻松地使用解析器内联处理结果.

以下是模板代码的一些片段,您可以从中找出框架的详细信息.

// Parses a literal item.
UBOOL LiteralEvaluate (UClass* C,class FParseInBase& In,class FParseOutBase& Out)
{
 FParseInMark M(In);
 NNode* e = In.GetNextSource();
 if (e && e->IsA(C))
 {
  Out.Callback(e);
  return 1;
 }
 M.Restore(In);
 return 0;
}
// Optional item of the specified type.
template <class U> struct Optional
{
 static UBOOL Evaluate (class FParseInBase& In,FParseOutBase& Out)
 {
  U::Evaluate(In,Out);
  return 1;
 }
};
// Ignore items by absorbing them; retains boolean logic but not callback.
template <class T> struct Ignore
{
 static UBOOL Evaluate (class FParseInBase& In,FParseOutBase& Out)
 {
  return T::Evaluate(In,GIgnore);
 }
};
// Zero or more items of the specified type.
template <class T> struct ZeroOrMore
{
 static UBOOL Evaluate (class FParseInBase& In,FParseOutBase& Out)
 {
  while (T::Evaluate(In,Out));
  return 1;
 }
};
// One or more items of the specified type.
template <class T> struct OneOrMore
{
 static UBOOL Evaluate (class FParseInBase& In,FParseOutBase& Out)
 {
  for( INT i=0; T::Evaluate(In,Out); i++ );
  return i>0;
 }
};
// Always fails.
struct RFalse
{
 static UBOOL Evaluate (class FParseInBase& In,FParseOutBase& Out)
 {
  return 0;
 }
};
// Always succeeds.
struct RTrue
{
 static UBOOL Evaluate (class FParseInBase& In,FParseOutBase& Out)
 {
  return 1;
 }
};
// Parses the first matching items of the specified subtypes of T.
template <class A,class B=RFalse,class C=RFalse,class D=RFalse > struct Or
{
 static UBOOL Evaluate (class FParseInBase& In,FParseOutBase& Out)
 {
  return A::Evaluate(In,Out) || B::Evaluate(In,Out) || C::Evaluate(In,Out) || D::Evaluate(In,Out);
 }
};
// Parses all the specified items.
template <class A,class B=RTrue,class C=RTrue,class D=RTrue> struct And
{
 static UBOOL Evaluate (class FParseInBase& In,FParseOutBase& Out)
 {
  FParseInMark Mark(In);
  Conjunction<NNode> Q;
  if( A::Evaluate(In,Q) && B::Evaluate(In,Q) && C::Evaluate(In,Q) && D::Evaluate(In,Q) )
  {
   Q.Forward(Out);
   return 1;
  }
  Mark.Restore(In);
  return 0;
 }
};
// A separated list.
template <class A,class B> class SeparatedList : public Or<And<A,B,SeparatedList>,A> {};
// Integer comparison.
template <INT A,INT B> struct IsAtLeast
{
 static UBOOL Evaluate (class FParseInBase& In,FParseOutBase& Out)
 {
  return A>=B;
 }
};

那个Test.ae是我在1999 - 2001年实施的一种实验性脚本语言 - 那时的配色方案很时髦,我发誓.:-)

显示的代码定义了语言结构的元数据.语言在Smalltalk"一切都是对象"的路径上走了很长一段路,处理一流的元类和相关问题,但是当我熟悉Haskell,Cayenne,Coq等高级类型系统时,我最终放弃了它.语言.

如今 -

我不喜欢在C++中实现解析器或编译器,因为与Haskell等现代函数语言中的类似实现相比,代码往往会膨胀70-80%.阅读Haskell解析器组合器以获取更多细节 - 由此产生的简单性和直接性是示例性的,并且以严格的,类型安全的方式完成.

Answer 2

不能确定，但​​ C++ 代码有点像Spirit，一个广泛使用模板的 C++ 解析器生成器。Test.ae 看起来像是元编程（在语言本身中定义语言细节），这在 C++ 中（模板是一个开始，但容易出错且丑陋）比在其他目标语言（例如 UnrealScript）中更难实现，我假设 test.ae 是用它编写的）。

所以 - 看起来 Parser.cpp 定义了 UnrealScript 的基本语法（使用Spirit），而 Test.ae 正在定义 UnrealScript 的扩展。