Parser

Може ли някой да ми даде информация за алгоритъм за направа на Parser.
Някаква книжка или help...
Аз започнах да правя един, обаче не знам никаква теория за парсери или компилатори и стана голяма боза.

Намери си учебник по "Транслатори и операционни системи" -- преподава се в МЕИ-тата. Дано си добре с математиката.

Математика не му е необходима.
Ето едно примерно алгоритъмче за парсер:
Предварително се извинявам за възможните пропуски, но логиката е пределно простичка, и смятам, че всеки ще се сети за какво става дума.

// дефинира възможните разделители между думите
#define IsSeparator(b) ( (b == 0x09) || (b == 0x20) || (b == 0x0D) || (b == 0x0A) )

// дефинира идентификатори на думите
#define TAG_IMG 1
#define TAG_HREF 2
#define TAG_BOLD 3
#define UNKNOWN 4

char *pInputBuffer; // входния буфер
long nBufferSize; // размер на входния буфер
long nCurrChar; // текущо отместване от началото на буфера
char strCurrWord[128]; // текуща дума, максимален размер - 128 символа

....

void Compile()
{
nCurrChar = 0;

// взимаме следваща дума от потока
// при възникване на грешка цикъла се прекъсва
while(GetNextWord(&strCurrWord[0], 128))
{
// конвертираме новополучената дума до някакво значение
// което да е по-лесно аз обработка
switch (Translate(strCurrWord))
{
case TAG_IMG:
.....
break;

case TAG_HREF:
....
break;

case TAG_BOLD:
.......
break;
}
}
}

BOOL GetNextWord(char *pBuff, int nMaxSize)
{
BYTE c;
int nCount = 0;

if ( (nMaxSize < 1) ||
(nCurrChar>= nBufferSize) ||
(pInputBuffer== NULL) )
return FALSE;

pBuff[0] = 0;

while(nCurrChar <= nBufferSize)
{
c = pInputBuffer[nCurrChar++];
if (IsSeparator(c))
{
if (pBuff[0])
{
return TRUE;
}
}
else
{
if (nCount < nMaxSize)
{
pBuff[nCount++] = c;
pBuff[nCount] = 0;
}
else
{
return FALSE;
}
}
}

pBuff[0] = 0;

return FALSE;
}


int Translate(char *pWord)
{
if (strcmp(pWord, "IMG") == 0) return TAG_IMG;
if (strcmp(pWord, "HREF") == 0) return TAG_HREF;
if (strcmp(pWord, "BOLD") == 0) return TAG_BOLD;

return UNKNOWN;
}

Si Vis Pacem, Para Bellum

Важно е какво ще се парсира, ама много важно!!
Ще направя забележка на МиГ-31, че структурата която си описал доколкото видях е линейна по дефиниция.
За направата на парсера най важно е на хартия да се опише какъв ще е формалния език разпознаван от парсера,семантични правила на този език дефинирани така че да задават затворено множество от възможните изрази принадлежащи на езика.Дефиниране на разделители между думите и символи които се вчитат без да се интерпретират(те пак са вид разделители).
Парсера става сложен, ако семантиката на разпознавания език позволява вложеност на различни структури, както и рекурсивно дефинирани структури.
Абе без да обяснявам повече, щото каквото и да кажа ще е недостатъчно те съветвам преди да програмираш да прочетеш нещо свързано с "еория на изводимости и формални езици" и "Теория на моделите".
Ако искаш да се пробваш да напишеш нещо работещо, пробвай да напишеш
парсер за аритметичен израз със скоби и рекурсивно зададени функции от функции на няколко променливи.

d=my_function(a,b)+c;

Би следвало парсера като начало да започне с това:

d
=
my_function
(
a
,
b
)
+
c
;


сиреч определяне на лексемите. A в случая няма разделители, както и в общия случай. Reptile даде малко по-обстоен отговор, само че аз не се сещам за конкретно заглавие на български, а из мрежата е голяма хамалогия да се намери нещо.

Преди време имах проблем, който така и не съм разрешил още: как (мамка му) се построява таблица на предшествията по дадена граматика? Даже си я имам в Backus-Naur форма.

м?

Znachi moga da preporycham 5 neshta:
1. Imam lekciite na docent Dobrev ot FMI po "Metodi za translaciya" na tekstovo faylche, kirilica za DOS. Day e-mail-che, shte ti gi pratya.
2. "Uvod v Diskretnata matematika" ot Krasimir Manev, izdanie na NBU.
3. "Rykovodstvo po izch. tehnika" (ili neshto takova), svetlo-zeleno, izdanie na VMEI, s mnogo avtori. Za razlika ot 2., tuk gledat po-prilojno na neshtata, no za men 2. si ostava The Ultimate Source (zaedno s 4.) :-)))
4. Tetradkata mi po "Metodi za translaciya". Ne e bash syshtoto kato 1. Ako mnogo iskash, moje da se vidim da ya snimash :-)))
5. flex, bison. Tova sa generatori na parser-i - pyrvoto e za avtomatni gramatiki (leksichen analiz), vtoroto - za kontekstno-svobodni (sintaktichen). Potyrsi si gi napr. na [линк]. Ama vyprosi za tyah ne priemam, shtoto ne sym gi polzval :-)))

Точно де, за начало входа се разделя на думи. Reptile се увлече малко, парсера май нямаше много общо нито със синтактичния анализ, нито с ОПЛ и т.н.

Si Vis Pacem, Para Bellum

Ya vij v po-dolniya mi posting nomer 3. Tam (dokolkoto si spomnyam) pishe, i to prosto obyasneno. Moga da ti pratya i 1., ama tam ne znam dali pishe neshto po vyprosa.

На български няма нищо!!(Доколкото знам)
Най-достъпна книга, като начин на представяне на терията за формалните езици е "Теория моделей" на руски от двама англичани, доколкото си спомням(Аз никога не помня автори незнам защо?!?) единя се казва Гудман.
Предварително трябва да си запознат с основни положения в математическата логика(Не слушай тези дето казват че нетрябвало математика за да се пишат парсери).
След тази книжка, ако се интересуваш може да се поинтересуваш за резултатите на Гьодел и неговите теореми за непълнота и изводимост.
Трябва да ти кажа че прпоръчвам книгата на англичаните като най достъпна, а не акто най добра.
Най добрите неща в тази обалст са написани от руснаците от новосибирския технико-математически университет(Така мисля се казваше), но четенето на тези материали влияе зле на здравия разум:)))))

Браво бе човек ти ли си водил лекции при Добрев???
Ако наистина ги имаш всичките ми ги прати на varan@abv.bg
Ще ти бъда безкрайно благодарен защото моите лекции от този курс изчезнаха предавани между различни колеги.
Тъй като явно се интересуваш от тези неща сигурно си ги водил с акъл(или имаш написаното от самия Добрев), щото лекциите на някои колежки са трагедия...........
Въпреки всичко ти благодаря предварително.......:)))

xypodilec@dir.bg

А за снимамето на т.4 -- може. Що пък и по някоя бира да не пийнем междувременно.

Mi ako iskash - moje da se vidim ponedelnik, che utre may pak shte e jega v rabotata. Az bachkam bash na Slaveykov (v pyrviya bezisten na Solunska).

Ne, ne sym gi vodil az :-))) Makar, che tochno po tova mislya, che moga.
Toy mi e dal faylcheto. Na men mi prepodavashe R. Doncheva, shtoto tochno tazi godina (1999) Dobrev si beshe schupil kraka.
Shte gi pratya dovechera, che sa mi vkyshti. Lele, dano ne sym iztril faylcheto, ne pomnya da mi se e myarkalo skoro pred ochite, no pyk takova neshto ne bih iztril po nikyv povod.

Мноооооооооого мерси :)))

prosto sluchajno poglednah shtoto temata mi e interesna
ama i drugo me zainteresuwa:
znachi bachkash na Slavejkov, pyrwia bezisten na Solunska?
shtoto i az tam bachkam (i sym Potencialen emigrant, kato mnogo drugi)
e, javno swetyt e malyk

Там да не би да има отдел "Потенциална емиграция"? :))

Може утре да се разберем нещо за понеделник.

Извинявам се че и аз се намесвам в разговора.

-- И мен ме интересува онзи текст (1) който е текст под ДОС.
Potencialen emigrant, ако не ти е много сложно, прати ми този текст като атачмент на адреса "boiko_angelov@yahoo.com". Ще ти бъда много благодарен :)

-- За компилатори и транслатори има една хубава книга издадена през 80-те години с автор Хънтер (Hunter). Превод от ангийски на руски. Ако някой иска, нека да я потърси в библиотеките (в ЦИНТИ или НБ) и да си я снима на ксерокс. На руски Хънтер се пишеше май като Хунтер или Хантер (не си спомням точно).

В тази книга първо е дадена теория за крайни автомати, контекстно свободни граматики, . . .
След това са дадени обстойни алгоритми за парсери по методите LL(1) и LR(n). Това, което ни дава стандартния yacc (или същото -- bison в Linux) е парсер по метода LR(1).

Rosene,
Eto ti i edin oprosten podhod - otidi i si kupi knigata "Algoritmi+strukturi ot danni=programi" ot N.Wirth - prevod na bulgarski. Predi nqkolko godini se prodawashe edna kirliva prepechatka, trqbva da se namira oshte na Slaveikov, v tehn. knizharnica do Slaveikov, v knizharnicata na VMEI i t.n. Mozhe i v bibliotekata da ima. V knigata, osven vsichko drugo, na elementaren ezik se opisva metodikata na sazdavane na rekursiven parser, kato e daden i source koda na Pascal.

Wizcom?
Az sym Gbr :-)

мога да изпратя :

Parsing Techniques : A Practical Guide - Dick Grune, Ceriel J.H. Jacobs (lex/yacc)

Compilers and compiler generators an introduction with C++ - P.D. Terry


мисля че и двете книги ги има на amazon.com - така че може да погледнете анотация за тях (ако не точно там другаде разбира се :)).