Tworzenia parserów różnych formatów danych

Ostatnio potrzebowałem odczytać dane z CSV z czym poradziłem sobie w prosty i typowy sposób - skorzystałem z gotowej biblioteki. Wszystko fajnie, ale co w sytuacji, gdy następnym razem zajdzie konieczność wyciągnięcia danych z jakiegoś nietypowego formatu, do którego nie ma gotowców lub jeśli jakiekolwiek są to nie spełniają wszystkich potrzeb.

Stąd też pytanie do bardziej doświadczonych osób - jak zacząć z nauką przetwarzania różnych formatów danych (np. CSV, XML, HTML, YAML, customowe pliki tekstowe czy binarne...), tak właściwie jaka wiedza jest potrzebna do pisania parserów "od zera" a nie korzystanie z gotowców?

poza wiedzą o formacie, który chcesz sparsować to tylko podstawy programowania - odczyt/zapis plików, zabawa ciągami, regex, if, pętle itp

Nie wiem kim jestes i na jakim etapie kariery / edukacji.

Na pewnym etapie projektu / stopniu kompikacji ugryzie się wyrażeniami regularnymi czy prostymi "szkolnymi" technikami (gdzieś do poziomu CSV, HTML-e)
Tu również zadziała case "utalentowany samouk"

Na innym, dla bardziej skomplikowanych języków wejściowych, nie ucieknie od solidnej bazy teoretycznej, coś co bywa nazywane :"teoria translatorów", "konstrukcja kompilatorów" itd, pisze się leksykę (schemat analizy leksykalnej) , gramatykę (analiza syntaktyczna), i implementuje semantykę (co dana poprawna syntaktycznie konstrukcja językowa OZNACZA, co ROBI)

Co do konkretnych produktów, u mnie raz na kilka lat, jak jest taka potrzeba , robi się wielo językowym Antlr (mamy chodzące realizacje w językach C++, C#, Java, najstarsze produkcyjnie chodzą już kilkanaście lat)
https://www.antlr.org/
ale sądzę, że bez teorii języków szkoda się szarpać.

Na gruncie C z popularnością w światku linuxowym jest lex/yacc, jak osobiście reaguję jak na fermentowane śledzie ze Skandynawii

Co będzie potrzebne? Generalnie niezbyt wiele - jak zbudowany jest dany format, biegłość w operowaniu na stringach, jakieś obycie z state machine oraz świadomość że w programowaniu również używa się ifów :) no i dyscyplina do pisania wielu testów

ale wyjdźmy z przykładami

Może akurat nie csv, xml czy json ale weźmy na warsztat zwykły kod

namespace Test

public int Test(int a, int b)
{
	if (a > b)
	{
		return a + b;
	}
	else
	{
		return a - b;
	}
}

Na początku fajnie jakbyś zamienił tekst na jakąś abstrakcję - leksem / token / symbol / whatever

W podanym niżej podejściu prostu przechodzisz po tym inpucie i w zależności od złożoności formatu dodajesz jakąś logikę która to obsłuży, tu jakiś przykład:

public List<LexElement> Walk()
{
    Reset();

    do
    {
        if (char.IsWhiteSpace(_Current))
            _State = LexingState.WhiteCharacter;
        else if (char.IsLetter(_Current))
            _State = LexingState.Word;
        else if (char.IsNumber(_Current))
            _State = LexingState.NumericalValue;
        else if (_Current == '"')
            _State = LexingState.String;
        else if (LexingFacts.OtherTokens.Contains(_Current))
            _State = LexingState.Character;
        else
            _State = LexingState.Unknown;

        Handle(_State);
    } while (MoveNext());

    return _Elements;
}

private void Handle(LexingState state)
{
    switch(state)
    {
        case LexingState.Word:
            HandleWord();
            break;
        case LexingState.String:
            HandleString();
            break;
        case LexingState.NumericalValue:
            HandleNumericalValue();
            break;
        case LexingState.Character:
            HandleOtherCharacter();
            break;
        case LexingState.WhiteCharacter:
            HandleWhiteCharacter();
            break;
        case LexingState.Unknown:
            throw new Exception("Unrecognized token");
    }
}
    
private void HandleString()
{
	var tmp = "";

	while (MoveNext())
	{
		if (_Current == '"' && HasPreviousElement() && ElementAt(_Index - 1) != LexingFacts.EscapeChar)
		{
			var element = new LexStringLiteral(tmp, GetDiagnostics());
			_Elements.Add(element);
			return;
		}

		tmp += _Current;
	}

	Error("Unclosed string");
}

private void HandleWord()
{
	var tmp = "";

	void AddElement()
	{
		LexElement element;
		if (LanguageFacts.KeywordMapper.TryGetValue(tmp, out var lexingElement))
		{
			element = new LexKeyword(tmp, lexingElement, GetDiagnosticsAtIndex(tmp.Length));
		}
		else
		{
			element = new LexWord(tmp, GetDiagnosticsAtIndex(tmp.Length));
		}

		_Elements.Add(element);
	}

	do
	{
		if (char.IsWhiteSpace(_Current) || IsLast())
		{
			if (IsLast()) tmp += _Current;

			AddElement();

			if (!IsLast())
				MoveBehind();

			return;
		}

		if (LexingFacts.OtherTokens.Contains(_Current))
		{
			AddElement();
			MoveBehind();
			return;
		}

		tmp += _Current;
	} while (MoveNext());
}

i np. po czymś takim dostajesz listę już nie znaczków, a czegoś co już ma konkretniejsze znaczenie np.

Keyword: namespace of Kind: Namespace
Word: Test
Keyword: public of Kind: AccessibilityModifier
Keyword: int of Kind: Type
Word: Test
Character: OpenParenthesis
Keyword: int of Kind: Type
Word: a
Character: Comma
Keyword: int of Kind: Type
Word: b
Character: ClosedParenthesis
Character: OpenBracket

Gdy już masz taką wstępnie przetworzoną warstwę na której łatwiej ci będzie operować, to teraz wypadałoby zrobić to, co tam potrzebujesz

w przypadku CSV to pewnie będzie budowanie obiektów, a w przypadku języku programowania budowa np. drzewka

|-Root
| \-Namespace: 'Test'
|   \-TypedFunction: 'Test'(int32). Args: (int32), (int32).
|     \-Body
|       \-TypedIf - ComplexTyped: bool; Operator: GreaterThan
|         |-Body
|         | \-TypedReturnStatement
|         |   \-ComplexTyped: int32; Operator: Addition
|         |     |-Typed Variable Use: a
|         |     \-Typed Variable Use: b
|         \-Body
|           \-TypedReturnStatement
|             \-ComplexTyped: int32; Operator: Substraction
|               |-Typed Variable Use: a
|               \-Typed Variable Use: b

ale to już się o wiele bardziej komplikuje i wymaga praktyki

więc pewnie jakbyś wyszedł od prostych formatów typu ini, później jakieś csvki mniej oraz bardziej skomplikowane (np. wartości ze średnikami oraz znakami nowej linii, etc)

podstawowy css może, jakiś podzbiór html/xml, następnie może json?

Obczaj sobie parser-combinators. Zapewne istnieje biblioteka dla Twojego języka programowania. Wtedy pisanie parserow staje się podobne do pisania wyrażeń regularnych, z tą różnicą, że kombinatory mogą więcej.

Dodam tylko, że zamiast pisania parserów do poszczególnych formatów, można napisać parser parserów, któremu podaje się w formie tekstowej składnię formatu i parsuje niezależnie od późniejszych zmian – bez przepisywania od nowa kodu. Właśnie coś takiego zrobiłem u siebie i działa skutecznie.

overcq napisał(a):

Dodam tylko, że zamiast pisania parserów do poszczególnych formatów, można napisać parser parserów, któremu podaje się w formie tekstowej składnię formatu i parsuje niezależnie od późniejszych zmian – bez przepisywania od nowa kodu. Właśnie coś takiego zrobiłem u siebie i działa skutecznie.

Wyprowadź mnie z błędu ... co jest osiągalne, gdy semantycznie klasa zagadnień jest albo
a) bardzo prosta (strzelam: pliki CVS-podobne), albo
b) różniące się syntaxy są czapą na (prawie) taka samą semantyką.

Ogólnie, moim zdaniem semantyka jest kłopotem. O ile lexer / syntax można wygenerować z jakiś gramatyk, to semantyka wymaga świadomego "ręcznego" programowania, i to przez kogoś kto myśli abstrakcyjnie.

@ZrobieDobrze: Być może. Jestem jeszcze przed napisaniem kompilatora, ale wydaje się, że można by zdefiniować biblioteki dla klas języków i wtedy zagadnienie byłoby o wiele łatwiejsze. A może problem tkwi w tym, że zaczyna się od składni i oczekuje, że znaczenie kodu będzie następnym krokiem złożoności, a tak naprawdę powinno się budować znaczenie „od zakończenia”, tylko używając składni do korekty znaczeń...

@overcq:

A może problem tkwi w tym, że zaczyna się od składni i oczekuje, że znaczenie kodu będzie następnym krokiem złożoności, a tak naprawdę powinno się budować znaczenie „od zakończenia”, tylko używając składni do korekty znaczeń...

co masz na myśli?

Tzn. najpierw założyć gotowy program wynikowy kompilacji, a następnie z postępem analizy składniowej programu zmieniać jego elementy. W przypadku konstrukcji ogólnej programu (funkcja typu main i deklaracje globalne) to wydaje się oczywiste, ale na przykład w przypadku deklaracji zmiennych takie rozumienie sprowadza się do tego, że skoro zmienna została nagle zadeklarowana, to dołącza do gotowego programu wynikowego i tylko oczekujemy jej użycia. Odwrotnie, tzn. tak jak zwykle się robi, to po wystąpieniu użycia szuka się zmiennej. Innymi słowy opis składni chyba musiałby być uzupełniany/modyfikowany w trakcie budowania znaczenia programu. A może nie i wystarczyłyby zmienne pomocnicze. To tylko takie luźne rozważania.

@overcq

Jak założyć gotowy program wynikowy kompilacji jeżeli jeszcze właściwie nic nie wiesz o nim?

i właściwie po co, jeżeli cały / większość ulegnie zmianie prawdopodobnie?

Wydaje mi się, że najpopularniejsze podejście jest takie:

Input (fragment):

public int Test(int a, int b)

Po leksykalnej masz jakieś uproszczenie oraz jakąś abstrakcję nad literkami:

Keyword: public of Kind: AccessibilityModifier
Keyword: int of Kind: Type
Word: Test
Character: OpenParenthesis
Keyword: int of Kind: Type
Word: a
Character: Comma
Keyword: int of Kind: Type
Word: b
Character: ClosedParenthesis

Z tego składasz drzewko i np. w/w node wygląda jakoś tak

oraz przechodzisz po nim X razy wykonując tzw. "passes", bo np. przy 1 przejściu jeszcze pewnych informacji nie masz.

I kolejny etap to emitowanie kodu na podstawie drzewka, np:

define dso_local i32 @Test(i32 %0, i32 %1)
{
  ...
}

Jakbyś mógł mi na przykładzie pokazać to, co opisujesz, bo nie widzę tego

Za­cz­nę od te­go, że od­no­szę się do in­ne­go pa­r­se­ra: bez po­dzia­łu na lek­se­my, tyl­ko od razu skła­d­nia, ta­ka jak na przyk­ład dla ko­du HTML tu­taj. Wte­dy po­d­czas pa­r­so­wa­nia jest dla każde­go entity w tym pliku opisu składni wywoływana procedura (funkcja) obsługi, która otrzymuje nazwę tego entity (w postaciu unikalnego identyfikatora) oraz tekst zawarty w tym entity. Jak łatwo zauważyć, procedura obsługi jest wywoływana dla każdego entity tak jak przechodzi się przez drzewo: najpierw ogólne entity, a później szczególne, aż do najbardziej szczegółowego.
Jeśli w trakcie nie zakończonej analizy składniowej (która jest wykonywana w jednym programie, a nie krokowo) zmieniać opis składni, to można by dostawać konkretne definicje dla danego konkretnego programu, np. procedura obsługi dostałaby deklarację zmiennej, zmodyfikowałaby opis składni o tę deklarację (albo użyła zmiennych pomocniczych bez modyfikacji opisu składni) i następnie dostawałaby odrębne entity z użyciem zmiennej.
Dlaczego na początku założyć gotowy program? Ponieważ to co powyżej, i wiadomo, jaki rodzaj programu wynikowego programista chce. To jest informacja dodatkowa na początku.
Przykładowo w tworzonym przeze mnie środowisku programowania OUX/C+ wyeliminowałem deklaracje plików nagłówkowych dla wywołań procedur systemowych; są one dodawane automatycznie na podstawie znalezionych w plikach źródłowych wywołań procedur systemowych. Czy to nie jest właśnie podejście typu: wiem, jaki program chcę mieć wynikowy? Ponieważ dla programu użytkowego można założyć, że chce się zadeklarować plik nagłówkowy dla procedury systemowej znajdującej się w przestrzeni globalnej, a nadawanie własnym procedurom nazw procedur systemowych jest błędem. Ale to taka dygresja.

@overcq:

Zdecydowanie piliśmy coś innego