Witam,
mam takie pytanie ze swiata parserów.
Piszę sobie taki mały parser i dla wygody podzieliłem go na dwie części:
Tokenizer i Parser.
W mojej składni występuje znaczek nawiasu klamrowego { i teraz, jeżeli jest
on po dolarze $, to znaczy, że jest to początek nazwy zmiennej, natomiast
jeżeli nie jest po dolarze, to jest po prostu elementem tekstu,
przykładowo:

abra { cos ${zmienna}

Pierwszy nawias to tekst, a kolejne, to już elementy zmiennej.

I teraz tak się zastanawiam (czysto koncepcyjnie), czy w tym przypadku
tokenami powinny być:

LITERAŁ: abra { coś
ZNACZNIK ZMIENNEJ
POCZĄTEK ZMIENNEJ
LITERAŁ: zmienna
KONIEC ZMIENNEJ

czy raczej
LITERAŁ: abra
NAWIAS
LITERAŁ: coś
ZNACZNIK ZMIENNEJ
NAWIAS OTWIERAJĄCY
LITERAŁ: zmienna
NAWIAS ZAMYKAJĄCY

i dopiero w parserze to sklejać dalej.

Rozwiązanie 1 ma taką zaletę, że od razu otrzymujemy sensowne tokeny (i jak
tak patrzę na dokumentację różnych parserów do C++ np. to wygląda, że tak
właśnie jest to robione), jednak trzeba pamiętać jeszcze kontekst, np. że
do tej pory nie było dolara $, więc to jest nawias, a nie początek
zmiennej, a to się może szybko przekształcić w bałagan nie do utrzymania.
Rorwiązanie 2 ma natomiast taką wadę, że na parserze spoczywa obowiązek
łączenia tokenów w większe tokeny (np. LITERAŁ: abra, NAWIAS, LITERAŁ: coś
w LITERAŁ: abra { coś), jednakże łatwiej jest tutaj zarządzać stanem
poprzez odpowiednie zchodzenie w dół drzewa z accept i expect.

Więc jakbyście wy to zrobili?

Ps. Chciałbym zaznaczyć, że wiem, że istnieją setki gotowych bibliotek i
tak dalej, jednak ja się pytam dla wiedzy, a nie dla praktycznego
rozwiązania.

Ps. Na internecie jest sporo na ten temat, jednakże poruszane są tylko
przykłady łatwe, w których takie dylematy nie występują :] Ale jakby gdzieś
ktoś miał linka, to też się nie obrażę.


--
Pozdrawiam
Zbyszek Malec

do góry

On Mon, 7 Feb 2011 21:23:26 +0100 Zbigniew Malec
<a...@i...invalid> wrote:

> Witam,
> mam takie pytanie ze swiata parserów.
> Piszę sobie taki mały parser i dla wygody podzieliłem go na dwie
> części: Tokenizer i Parser.
> W mojej składni występuje znaczek nawiasu klamrowego { i teraz,
> jeżeli jest on po dolarze $, to znaczy, że jest to początek nazwy
> zmiennej, natomiast jeżeli nie jest po dolarze, to jest po prostu
> elementem tekstu, przykładowo:
>
> abra { cos ${zmienna}
>
> Pierwszy nawias to tekst, a kolejne, to już elementy zmiennej.
>
> I teraz tak się zastanawiam (czysto koncepcyjnie), czy w tym przypadku
> tokenami powinny być:
>
> LITERAŁ: abra { coś
> ZNACZNIK ZMIENNEJ
> POCZĄTEK ZMIENNEJ
> LITERAŁ: zmienna
> KONIEC ZMIENNEJ
>
> czy raczej
> LITERAŁ: abra
> NAWIAS
> LITERAŁ: coś
> ZNACZNIK ZMIENNEJ
> NAWIAS OTWIERAJĄCY
> LITERAŁ: zmienna
> NAWIAS ZAMYKAJĄCY
>
> i dopiero w parserze to sklejać dalej.
>
> Rozwiązanie 1 ma taką zaletę, że od razu otrzymujemy sensowne tokeny
> (i jak tak patrzę na dokumentację różnych parserów do C++ np. to
> wygląda, że tak właśnie jest to robione), jednak trzeba pamiętać
> jeszcze kontekst, np. że do tej pory nie było dolara $, więc to jest
> nawias, a nie początek zmiennej, a to się może szybko przekształcić w
> bałagan nie do utrzymania. Rorwiązanie 2 ma natomiast taką wadę, że
> na parserze spoczywa obowiązek łączenia tokenów w większe tokeny (np.
> LITERAŁ: abra, NAWIAS, LITERAŁ: coś w LITERAŁ: abra { coś), jednakże
> łatwiej jest tutaj zarządzać stanem poprzez odpowiednie zchodzenie w
> dół drzewa z accept i expect.
>
> Więc jakbyście wy to zrobili?

Parser przecież i tak tworzy jakieś drzewo rozbioru gramatycznego.
Więc czy masz do sprawdzania wariant ZMIENNA/NAWIAS/LITERAŁ/NAWIAS,
czy POCZĄTEK ZM./LITERAŁ/KONIEC ZM. to raczej mała różnica, bo
ostatecznie interesuje Cię nazwa zmiennej. Bardziej kwestia, jak
bardzo ułatwi (lub skomplikuje) to inne działania.

Ale jeślibyś zdecydował się na pierwszy wariant, tzn. trochę więcej
pracy w tokenizerze, to zastanów się, czy wtedy w ogóle warto wypisywać
aż cztery tokeny dla zmiennej. Wiesz, gdzie jest początek i koniec
zmiennej, znasz jej nazwę - może wyprowadź jeden token ZMIENNA i już
nie kłopocz parser duperelami. ;-)

w.

do góry

Dnia 07-02-2011 o 21:23:26 Zbigniew Malec <a...@i...invalid>
napisał(a):
(...)

W moim parserze wyrażeń matematycznych zastosowałem wariant ze wstępną
(uproszczoną) analizą składniową. Fragment pliku wejściowego dla
generatora tokenizera wygląda tak:

# Stan 1 - Oczekiwanie na obiekt numeryczny

1,integer->2=[0-9]+
1,unaryoperator->1=(\-)|(\!)
1,variable->2=[a-zA-Z][a-zA-Z0-9]*
1,function->1=[a-zA-Z][a-zA-Z0-9]*\(
1,openparenthesis->1=\(
(...)

# Stan 2 - Oczekiwanie na operator

2,closeparenthesis->2=\)
2,operator->1=(\+)|(\-)|(\*)|(\/)|(\\)|(\%)|(\^)|(\<
\<)|(\>\>)|(\<)|(\>)|(\<\=)|(\>\=)|(\=\=)|(\!\=)|(\&
)|(\|)|(\#)
(...)

Czyli na przykład f(x*(3+4)) zostanie rozpoznane jako:

function, variable, operator, openparenthesis, integer, operator, integer,
closeparenthesis, closeparenthesis.

Analogicznie -2-3 jako:

unaryoperator integer operator integer

Moim zdaniem taka wstępna analiza składniowa jest bardzo wygodna, bo
pozwala na wczesne wykrycie podstawowych błędów składniowych. Jeśli na
przykład ktoś postawi operator binarny zaraz za nawiasem otwierającym -
gdzie oczekiwany jest obiekt numeryczny - pierwszy zaprotestuje tokenizer,
zgłaszając nie rozpoznany obiekt.

Jest też minus tego rozwiązania: błąd zgłoszony użytkownikowi nie jest
zbyt czytelny ("Nie rozpoznany token" lub "Nieprawidłowe wyrażenie" kontra
"Nieoczekiwane wystąpienie operatora binarnego"). Wszystko jednak zależy
od potrzeb :)

Pozdrawiam -- Spook.

--
Używam klienta poczty Opera Mail: http://www.opera.com/mail/

do góry

On Mon, 07 Feb 2011 23:30:31 +0100, Wojciech "Spook" Sura wrote:

> Moim zdaniem taka wstępna analiza składniowa jest bardzo wygodna, bo
> pozwala na wczesne wykrycie podstawowych błędów składniowych. Jeśli na
> przykład ktoś postawi operator binarny zaraz za nawiasem otwierającym -
> gdzie oczekiwany jest obiekt numeryczny - pierwszy zaprotestuje tokenizer,
> zgłaszając nie rozpoznany obiekt.

W sumie, jak za bardzo uproszczę tokenizer, to mi z niego wyjdzie po prostu
lekser.

--
Pozdrawiam
Zbyszek Malec

do góry