ANTLR – ANother Tool for Language Recognition

Na pewno spotkałeś się kiedyś z niestandardowymi strukturami danych, które ciężko przetworzyć w konwencjonalny sposób. W tym wpisie postaram się pokazać jak możesz poradzić sobie z takim problemem.

Czym jest ANTLR?

ANTLR – to generator parsera do czytania, wykonywania lub tłumaczenia binarnych oraz tekstowych struktur danych. Standardowy projekt procesowania danej struktury danych składa się z pliku Grammar zawierającego reguły dla Lexera oraz Parsera, które zaś używane są do tokenizacji oraz przetwarzania danych według wcześniej stworzonych reguł.

Ciekawostka

Zastanawiałeś się kiedyś jak działa analiza składni, dla przykładu w Netbeans? Jeśli tak, to pewnie nie zaskoczę Cię informacją, że używany jest tam między innymi ANTLR do analizy składni języka C++.

Ponad to, znany pewnie wszystkim Twitter, używa ANTLR do przetwarzania zapytań dla wyszukiwania. Są to ponad 2 miliardy zapytań na dzień. Ilość robi wrażenie? Na mnie tak.

Do czego możemy użyć ANTLR w praktyce?

Do wielu rzeczy, począwszy od przetwarzania niestandardowych strukturalnie plików konfiguracyjnych, przez konwertery tzw. ,,legacy code”, po różnego rodzaju parsery, renderowanie znaczników i tym podobne. Możliwości jest na prawdę sporo.

W jakich językach programowania można tego użyć?

W zasadzie we wszystkich najpopularniejszych językach: Java, C#, C++, Python, Swift, Go (po za PHP, chociaż swego czasu widziałem gdzieś, zrobiony port dla tego języka). Dla każdego z tych języków ,,kompilator” gramatyczny wygeneruje parser oraz lexer do przetwarzania zdefiniowanej przez nas struktury danych.

Przykład użycia

Na potrzeby tego wpisu, językiem programowania przy użyciu, którego będę prezentować możliwości ANLTR to C# (miłośnicy Javy muszą mi wybaczyć 🙂 ). Natomiast samo narzędzie ANLTR wykorzystam w jego najnowszej wersji, na dzień tworzenia tego wpisu czyli V4.

*Procesowanie przykładowej prostej struktury danych:

bq. # Comment
TypeId = 860
Name        = "Example Item"
Description = "Description of example item"
Attributes  = {Waypoint=0, Class=1}
Flags       = {Block, Pickable}

Struktura dosyć prosta, zapewne można by bez większego problemu przetworzyć takie dane przy użyciu choćby regexów. Jednak, chciałbym na tym dosyć trywialnym przykładzie pokazać jak działa ANTLR.

Plik grammar (.g4) wygląda w ten sposób:

grammar Objects;
 
root:
    items+
    ;
 
items:
    ('TypeId' '=' typeId) ('Name' '=' name) ('Description' '=' description)? ('Attributes' '=' attributes)? ('Flags' '=' flags)?
    ;
typeId:
     NUMBER
    ;
name:
    TEXT
    ;
description:
    TEXT
    ;
flags:
    ('{') flag+ ('}')
    ;
flag:
    STRING
    ;
attributes:
    ('{')  attribute+ ('}')
    ;
attribute:
    attributeName STRING?'=' attributeValue
    ;
attributeName:
    STRING;
attributeValue:
    NUMBER;
 
fragment DIGIT:
   ('-')? '0'..'9'
;
 
TEXT:
    '"' .*? '"'
;
 
STRING:
    ('a'..'z' | 'A'..'Z')+
;
 
NUMBER:
    DIGIT+
;
 
WHITESPACE:
    ' ' -> skip
;
 
COMMA_SEPARATOR :
    ',' -> skip
;
 
NEWLINE :
    ('\n' | '\r' | '\r\n') -> skip
;
 
COMMENT     :
    '#' ~( '\r' | '\n' )* -> skip
    ;

Kompilator na podstawie gramatyki zawartej w pliku grammar utworzy w docelowym języku (w naszym przypadku C#) parser oraz lexer przy użyciu których możemy skorzystać z możliwości przetworzenia wskazanych danych.

Powstałe drzewo wygląda dosyć prosto i przejrzyście. Oczywiście w przypadku większej ilości danych, drzewo rozszerzy się o kolejne elementy.

Jak z wydajnością takiego rozwiązania? To zależy od skomplikowania danych, ale mogę z czystym sumieniem powiedzieć, że w większości przypadków, przy odpowiednio stworzonej gramatyce, wydajność jest na zadowalającym poziomie.

Przykładowa klasa Reader

using Antlr4.Runtime;
using Objects.Antlr;
using Antlr.Visitor;
using Objects.Domain;
 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace Objects
{
    class ObjectsReader
    {
        private readonly string objectsFilePath;
 
        public ObjectsReader(string objectsFilePath)
        {
            this.objectsFilePath = objectsFilePath;
        }
 
        public List Read()
        {
            var objectsFileContent = System.IO.File.ReadAllText(objectsFilePath);
 
            var inputStream = new AntlrInputStream(objectsFileContent);
            var objectsLexer = new ObjectsLexer(inputStream);
            var commonTokenStream = new CommonTokenStream(objectsLexer);
 
            var objectsParser = new ObjectsParser(commonTokenStream);
            var itemsContext = objectsParser.root().items();
 
            var visitor = new ItemVisitor();
 
            foreach(var itemContext in itemsContext)
            {
                visitor.Visit(itemContext);
            }
 
            // Do something with parsed item's
        }
    }
}

Klasa Visitor z implementacją interfejsu z biblioteki ANTLR. Visitor służy do procesowania określonej części powstałego drzewa, danej struktury danych.

using Antlr4.Runtime.Misc;
using Objects.Domain;
 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace Antlr.Visitor
{
    class ItemVisitor : ObjectsBaseVisitor
    {
        public override Item VisitItems([NotNull] ObjectsParser.ItemsContext context)
        {
            var typeId = context.typeId().GetText();
            var name = context.name().GetText();
            var flags = context.flags();
            var description = context.description();
            var attributes = context.attributes();
 
            // Container
            var Item = new Item {
                Id = Convert.ToInt32(typeId),
                Name = name
            };
 
            if (null != description)
            {
                var descriptionText = description.GetText();
                Item.Description = descriptionText;
            }
 
            if (null != flags)
            {
                var _flags = flags.flag();
 
                foreach (var _flag in _flags)
                {
                    var flagText = _flag.GetText();
 
                    try
                    {
                        ItemFlag itemFlag = (ItemFlag)Enum.Parse(typeof(ItemFlag), flagText);
                        Item.AddFlag(itemFlag);
                    }
                    catch(ArgumentException)
                    {
                        Console.WriteLine("Undefined flag: {0}", flagText);
                    }
                }
            }
 
            if (null != attributes)
            {
                var _attributes = attributes.attribute();
 
                foreach(var _attribute in _attributes)
                {
                    var attributeType = _attribute.attributeName().GetText();
                    var attributeValue = _attribute.attributeValue().GetText();
 
                    try
                    {
                        ItemAttributeType itemAttributeType = (ItemAttributeType)Enum.Parse(typeof(ItemAttributeType), attributeType);
                        Item.AddAttribute(new ItemAttribute(itemAttributeType, Convert.ToInt32(attributeValue)));
                    }
                    catch (ArgumentException)
                    {
                        Console.WriteLine("Undefined attribute: {0}", attributeType);
                    }
                }
            }
 
            // Do something with parsed data
 
            return base.VisitItems(context);
        }
    }
}

Kod w klasach jest jedynie przykładem użycia parsera niżeli działającą wersją.

Po więcej informacji zapraszam na stronę projektu: http://www.antlr.org/index.html

Autorem tekstu jest Miłosz Lenczewski.