Подтвердить что ты не робот

О чем думал Тим Суини? (Как работает этот С++-парсер?)

Тим Суини из Epic MegaGames является ведущим разработчиком Unreal и программист geek. Много лет назад был опубликован следующий снимок экрана для VoodooExtreme:

Tim Sweeney's screenshot

Как программист на С++ и поклонник Sweeney, я был очарован этим. Он показывает общий код на С++, который реализует какой-то язык сценариев, где этот язык сам по себе является общим в том смысле, что он может определять свою собственную грамматику.

г. Суини никогда не объяснял себя.: -)

Редко видеть этот уровень программирования шаблонов, но вы видите его время от времени, когда люди хотят заставить компилятор генерировать отличный код или потому, что они хотят создать общий код (например, Современный дизайн С++).

Тим, похоже, использует его для создания грамматики в Parser.cpp - вы можете видеть, что выглядит как приоритетные двоичные операторы. Если это так, то почему Test.ae выглядит так же, как определение грамматики?

Очевидно, что это головоломка, которую нужно решить. Победа идет на ответ с рабочей версией этого кода, или самым правдоподобным объяснением, или самим Тимом Суини, если он отправит ответ.: -)

4b9b3361

ОТВЕТЫ

Ответ 1

Я спросил мистера Суини по электронной почте и получил этот ответ:

Код С++ использует классы шаблонов, которые я написал, которые реализуют комбинаторы парсеров. Идея состоит в том, чтобы начать с некоторых основных синтаксических анализаторов, таких как литералы, где PLit < 'A' > анализирует литеральный символ "A", PAny < > анализирует любой символ, но терпит неудачу, если в конце сбоя PEof завершается с ошибкой, если мы не в конце файла и т.д. И затем мы объединяем их в произвольные деревья с помощью комбинаторов, таких как PAnd, которые анализируют a тогда b, и преуспевают только в том случае, если оба успешно - иначе он терпит неудачу с точкой разбора без движения. И если это удастся, результатом будет структура, содержащая два поля: одна для результата a и одна для результата b. И так далее.

Реализация путаница в С++ по ряду причин, в том числе, что шаблоны не поддерживают произвольные переменные параметры, и без первоклассных lambdas мы не можем легко обрабатывать результаты inline с помощью синтаксического анализатора.

Вот некоторые фрагменты кода шаблона, из которых вы, вероятно, можете выяснить детали фреймворка.

// 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 и других языки.

В настоящее время -

Я не являюсь поклонником реализации парсеров или компиляторов на С++, поскольку код, как правило, раздувается на 70-80% по сравнению с аналогичной реализацией на современном функциональном языке, таком как Haskell. Для более подробного ознакомления с комбинаторами парсеров Haskell - получившаяся в результате простота и прямота является образцовой, и это делается строго и безопасно.

Ответ 2

Не могу точно сказать, но код типа С++ sorta выглядит как Spirit, генератор синтаксического анализатора С++, который широко используется шаблонов. Test.ae выглядит как метапрограммирование (определяющее детали языка в самом языке), что сложнее сделать на С++ (шаблоны - это начало, но подвержено ошибкам и уродливым), чем это было бы на каком-то другом целевом языке (например, UnrealScript, что я и предполагаю, что test.ae написано в).

Итак - похоже, что Parser.cpp определяет базовую грамматику для UnrealScript (используя Spirit), а Test.ae определяет расширения для UnrealScript.

Ответ 3

Я не знаю, что сделал Суини, и я буду предполагать, что другие ответы об использовании Духа находятся в правильном духе. У меня нет опыта с шаблонами Spirit, но я понимаю, что если вы определяете сложную грамматику с ним, становится довольно сложно обрабатывать (а также медленно компилировать). Для определения истины следует использовать опыт других людей.

Существуют и другие способы реализации расширений для С++, например, с использованием программных преобразований и расширяемых грамматик. См. этот SO ответ на увеличение самой грамматики С++ с произвольными расширениями, где возможны очень сложные расширения и которые фактически использовались.

Метапрограммирование шаблона генерирует интересный код, в котором специально используются шаблоны. Используя программные преобразования, вы можете генерировать произвольно интересный код в любой точке программы, например, как будто "шаблоны" (дополнительный синтаксис) изменяет семантику любым способом, который, по вашему мнению, является полезным.

Ответ 4

Снимок экрана, очевидно, из MSVC 6.0 или более раннего временного кадра, который не очень ценит сложные шаблоны (и, конечно же, не поддерживает частичную специализированную специализацию). Я не использовал дух. Из этих скриншотов невозможно сказать, что Суини действительно делает, помимо определения того, что выглядит DSL в Test.ae.

В Parser.cpp содержатся только полные инструкции на языке С++, и они ничего не говорят вам ничего, кроме того, что он объявляет 3 типа. Вы действительно ничего не можете сказать - слишком много скрывается окном "Test.ae".