Битва «Слушатель vs Посетитель» на стадионе antlr4

Посещать или слушать? Дело вкуса – не более. Или нет?
Предыстория.

Разобрав исходный текст, на выходе образовалось дерево:



Само по себе дерево не имеет ни какого смысла, оно “Деревянное”, смыслом и какой либо ценностью обладает результат анализа (обхода) этого дерева. Для тех кто не готов напрягаться и писать самописные сани по спуску с дерева (например, меня) в antlr4 добавлена возможность получить анализатор почти бесплатно.

1. Visitor

Классика — поведенческий шаблон проектирования. При обходе узлов определяется метод обрабатывающий текущий тип узла, после чего метод вызывается и вот конкретно здесь начинается разработка, а именно анализ пришедшего поддерева.

2. Listener

Новшество, появившееся в четвертой версии. Поведение этого класса уже далеко не классическое (Observer или Publish/Subscribe). В классическом исполнении наблюдается менеджер который оповещает подписчиков о наступлении событий. Поведения рассматриваемого слушателя больше похоже на работу инспектора. Инспектор перед проверкой узла делает заметку “Я проверяю Х узел”, далее идет обход потомков узла, после обхода, которых можно сделать “Заключение о результатах обхода узла Х”.

Практика

Для лучшего понимания происходящего обратимся к автору распознавателя pragprog.com/book/tpantlr2/the-definitive-antlr-4-reference. В книге “The Definitive ANTLR 4 Reference” В разделе 8.2 Translating JSON to XML автор производит трансляцию, используя Listener.

Примеры в книге основаны на JAVA, я с JAVA не знаком, но переводятся на C# без болезненно (вот что значит клонирование best practice).

Для приготовления слушателя нам понадобиться VS, C# proj и JASON.g4 с примерно таким наполнением

grammar JASON;

json: object
	| array
	;

object
	: '{' pair ( ',' pair )* '}'	# AnObject
	| '{' '}'						# EmptyObject
	;

	pair: STRING':'value;

array
	: '['value(','value)*']'	# ArrayOfValues
	| '['']'					# EmptyArray
	;

value
	: STRING	# String
	| NUMBER	# Atom
	| object	# ObjectValue
	| array	# ArrayValue
	| 'true'	# Atom
	| 'false'	# Atom
	| 'null'	# Atom
	;

STRING
	: '"' ( ESC | ~["\\] )* '"';

	fragment ESC: '\\'(["\\/bfnrt]|UNICODE);
	fragment UNICODE:'u'HEX HEX HEX HEX;
	fragment HEX:[0-9a-fA-F];

NUMBER
	: '-'? INT'.'INT EXP? //1.35,1.35E-9,0.3,-4.5
	| '-'? INT EXP //1e10-3e4
	| '-'? INT //-3,45
	;

	fragment INT: '0'|[1-9][0-9]*;//noleadingzeros
	fragment EXP: [Ee][+\-]? INT;//\-since-means"range"inside[...]

WS : [\t\n\r]+->skip;

Это грамматика позволяющая распознать JASON. В свойствах файла необходимо выставить Generate Listener и Generate Visitor (это еще пригодиться). Результатом работы Слушателя в оригинальном примере из книги является текст xml, меня это не устраивает я буду получать XElement (все равно xml текст нужно будет во что то переводить, хотя плюс текста в том что он не зажимает в рамки использования конкретных классов).

Алгоритм прост: тк antlr4 использует нисходящий разбор (в нашем случае от корня к узлам), то xml будет формироваться точно так же, создание элемента предка к которому будут добавляться потомки.

Пример Слушателя:

      class XmlListener : JASONBaseListener
	{
		#region fields

		ParseTreeProperty<XElement> xml = new ParseTreeProperty<XElement>();

		#endregion

		#region result

		public XElement Root { get; private set; }

		#endregion

		#region xml api

		XElement GetXml( IParseTree ctx )
		{
			return xml.Get( ctx );
		}

		/// <summary>
		/// поиск родительского xml элемента
		/// </summary>
		XElement GetParentXml( IParseTree ctx )
		{
			var parent = ctx.Parent;

			XElement result = GetXml( parent );

			if ( result == null )
				result = GetParentXml( parent );

			return result;
		}

		void SetXml( IParseTree ctx, XElement e )
		{
			xml.Put( ctx, e );
		}

		#endregion

		#region listener

		public override void ExitString( JASONParser.StringContext context )
		{
			var value = GetStringValue( context.STRING() );

			AddValue( context, value );
		}

		public override void ExitAtom( JASONParser.AtomContext context )
		{
			var value = context.GetText();

			AddValue( context, value );
		}

		public override void EnterPair( JASONParser.PairContext context )
		{
			var name = GetStringValue( context.STRING() );
			XElement element = new XElement( name );

			XElement ParentElement = GetParentXml( context );

			ParentElement.Add( element );
			SetXml( context, element );
		}

		public override void EnterJson( JASONParser.JsonContext context )
		{
			Root = new XElement( "JSON" );
			SetXml( context, Root);
		}

		#endregion

		#region private

		private string GetStringValue( ITerminalNode terminal )
		{
			return terminal.GetText().Trim( '"' );
		}

		private void AddValue( ANTLR_CSV.JASONParser.ValueContext context, string value )
		{
			var parent = GetParentXml( context );

			if ( context.Parent.RuleIndex == JASONParser.RULE_array )
			{
				XElement element = new XElement( "elemnt" );
				element.Value = value;

				parent.Add( element );

				SetXml( context, element );
			}
			else
				parent.Value = value;
		}

		#endregion

	}

EnterJson соответствует входу в узел описанный в грамматике так:

json: object
	| array
	;

ExitString соответствует выходу из узла описанного в грамматике так:

STRING	# String

В отличии от оригинального примера я не использую всех прелестей Enter и Exit. За то есть ParseTreeProperty признанный хранить пары [поддерево, значение], наверное лучше это заменить на обычный словарь (хуже точно не будет).

Пример Посетителя:

class XmlVisitor : JASONBaseVisitor<XElement>
	{
		#region fields

		private XElement _result;

		ParseTreeProperty<XElement> xml = new ParseTreeProperty<XElement>();

		#endregion

		#region xml api

		XElement GetXml( IParseTree ctx )
		{
			return xml.Get( ctx );
		}

		XElement GetParentXml( IParseTree ctx )
		{
			var parent = ctx.Parent;

			XElement result = GetXml( parent );

			if ( result == null )
				result = GetParentXml( parent );

			return result;
		}

		void SetXml( IParseTree ctx, XElement e )
		{
			xml.Put( ctx, e );
		}

		#endregion

		#region visitor

		/// <summary>
		/// значение по умолчанию - создаваемое дерево xml
		/// </summary>
		protected override XElement DefaultResult { get { return _result; } }

		public override XElement VisitJson( JASONParser.JsonContext context )
		{
			_result = new XElement( "JSON" );
			SetXml( context, _result );
			return VisitChildren( context );
		}

		public override XElement VisitString( JASONParser.StringContext context )
		{
			var value = GetStringValue( context.STRING() );

			AddValue( context, value );

			return DefaultResult;
		}

		public override XElement VisitAtom( JASONParser.AtomContext context )
		{
			var value = context.GetText();

			AddValue( context, value );

			return DefaultResult;
		}

		public override XElement VisitPair( JASONParser.PairContext context )
		{
			var name = GetStringValue( context.STRING() );
			XElement element = new XElement( name );

			XElement ParentElement = GetParentXml( context );

			ParentElement.Add( element );
			SetXml( context, element );

			return VisitChildren( context );
		}

		#endregion

		#region private

		private string GetStringValue( ITerminalNode terminal )
		{
			return terminal.GetText().Trim( '"' );
		}

		private void AddValue( ANTLR_CSV.JASONParser.ValueContext context, string value )
		{
			var parent = GetParentXml( context );

			if ( context.Parent.RuleIndex == JASONParser.RULE_array )
			{
				XElement element = new XElement( "elemnt" );
				element.Value = value;

				parent.Add( element );

				SetXml( context, element );
			}
			else
				parent.Value = value;
		}

		#endregion
	}

Как говориться “Найдите 10 отличий”, первое отличие VisitJson, управление посещением без вызова VisitChildren( context ) посещение потомков прекращается, а значит и обход. Каждый из методов посещения должен возвращать значение, то есть всегда есть результат посещения, а это удобно:

var result = visitor.Visit( tree ); 

Когда при работе со слушателем:

walker.Walk( listener, tree );
var result = listener.Root;

В оригинальном примере без Слушателя было бы довольно туго, для данного решения разницы особо нет, но я отдаю свой голос в пользу решения на Посетителе.

Ну и что бы можно было опробовать своими руками:

    private static IParseTree CreateTree()
		{
			StringBuilder sb = new StringBuilder();

			sb.AppendLine( "{" );
			sb.AppendLine( "\"description\":\"Animaginary server config file\"," );
			sb.AppendLine( "\"count\":500," );
			sb.AppendLine( "\"logs\":{\"level\":\"verbose\",\"dir\":\"/var/log\"}," );
			sb.AppendLine( "\"host\":\"antlr.org\"," );
			sb.AppendLine( "\"admin\":[\"parrt\",\"tombu\"]," );
			sb.AppendLine( "\"aliases\":[]" );
			sb.AppendLine( "}" );


			AntlrInputStream input = new AntlrInputStream( sb.ToString() );
			JASONLexer lexer = new JASONLexer( input );
			CommonTokenStream tokens = new CommonTokenStream( lexer );
			JASONParser parser = new JASONParser( tokens );
			IParseTree tree = parser.json();
			return tree;
		}

Пример JSON текста взят практически без изменений из оригинального примера:

    private static void ListenerXml()
		{
			IParseTree tree = CreateTree();

			ParseTreeWalker walker = new ParseTreeWalker();
			XmlListener listener = new XmlListener();
			walker.Walk( listener, tree );
			var result = listener.Root;
		}
     private static void VisitorXml()
		{
			IParseTree tree = CreateTree();

			XmlVisitor visitor = new XmlVisitor();
			var result = visitor.Visit( tree );
		}

Ну и результат выполнения:

<JSON>
  <description>Animaginary server config file</description>
  <count>500</count>
  <logs>
    <level>verbose</level>
    <dir>/var/log</dir>
  </logs>
  <host>antlr.org</host>
  <admin>
    <elemnt>parrt</elemnt>
    <elemnt>tombu</elemnt>
  </admin>
  <aliases />
</JSON>  

Как ни странно, но оба метода выдали одно и то же.

Далее

P.S. Слушатель vs Посетитель – 0: 1