пропускал содержимое внутреннего блока, а приступал к следующему за ним токену?

Не понятно.

ну, при вызове

// вызов 1
lex("{ 
   some;
   {
      some2;
   }
   some3;
}");

//вызов 2
lex("{
          some2;
       } // - тут он выходит
     some3;
}")

Теперь я вообще в растерянности. После выхода из «вызов2», следующим токеном в потоке будет «some3», каким образом он снова начнет с «{some2}»?

да, не совсем корректный пример привел сначала.

{ some; { some2; some4; } some3; }

На данный момент у меня он после выхода из вызова 2 возвращается к след токену, в данном случае some4. А должен к some3.

он после выхода из вызова 2 возвращается к след токену, в данном случае some4.

Каким образом???

Берем токен -> some
Берем токен -> { -> call2
    Берем токен -> some2
    Берем токен -> some4
    Берем токен -> } -> return from call2
Берем токен -> some3

У тебя точно *поток* токенов? Иначе я не представляю как можно что-то сделать не так.

он когда видит «{» входит в lex(оставшаяся часть строки). Потом, когда видит «}» выходит. И list->next становится токеном, следующим за «{» и «{»->next, в данном случае - some4

Да поток, в виде списка. И я его обхожу последовательно.

lex(оставшаяся часть строки)

Я понял. Сделай отдельно лексер, который будет разбирать строку. Грубо говоря, функция get_next_token(). И парсер, который ей пользуется. Построение дерева получится само-собой.

тут много лишнего кода, использую для отладки, потом почищу, но принцип должен быть понятен.

item_list* lex(token_list *lst, int struct_inside) {
	struct item_struct *struc;
	struct item_variable *variable;
	struct item_pointer *pointer;
	struct item_array *array;
	item_list *itm_lst;
	int struct_level = 0;
	char* space;
	space = (char *)malloc(20);
	space[0] = '\0';
	if (struct_inside == 0) 
		lst = lst->head;
	// TODO: add zero fills here too
	struc = (struct item_struct*)malloc(sizeof(struct item_struct));
	variable = (struct item_variable*)malloc(sizeof(struct item_variable));
	pointer = (struct item_pointer*)malloc(sizeof(struct item_pointer));
	array = (struct item_array*)malloc(sizeof(struct item_array));
	itm_lst = (item_list*)malloc(sizeof(item_list));
	do {
		if ((lst->tok->type == COMPLEX_STRUCT) && (lst->next != NULL)) {
			struc->name = lst->next->tok->value;
			struc->level = struct_level;
			if ((lst->next->next != NULL) & (lst->next->next->tok->type == BRACKET_LFIGURE)) {
				printf("Entering struct definition...\n");
				struct_inside++;
				// goto inside subtree - substructure
				struc->items = lex(lst->next->next, struct_inside);
			} else {
				printf("Error: empty structure!\n");
			}
			//if (struc->level == 0) {
			struc->items->head = struc->items;
			item_add(itm_lst, struc, ITEM_STRUCT);
			//}
		} else if ((lst->tok->type == TYPE_CHAR) || (lst->tok->type == TYPE_SHORT) ||
			(lst->tok->type == TYPE_INT) || (lst->tok->type == TYPE_LONG)) {

			if (is_array(lst->next->tok->value)) {
				array->name = lst->next->tok->value;
				array->type = lst->tok->type;
				array->count = array_size(lst->next->tok->value);
				switch (array->type) {
					case TYPE_CHAR:
						array->size = array->count * sizeof(char);
						break;
					case TYPE_SHORT:
						array->size = array->count * sizeof(short);
						break;
					case TYPE_INT:
						array->size = array->count * sizeof(int);
						break;
					case TYPE_LONG:
						array->size = array->count * sizeof(long);
						break;
				}
				array_name_clear(array->name);
				//if (struc->level) {
				//	struc->items->item_type = ITEM_ARRAY;
				//	item_add(struc->items, array, ITEM_ARRAY);
				//}
				item_add(itm_lst, array, ITEM_ARRAY);
				printf("%sarray: %s [%ld] type: %d; size: %ld bytes\n", space, array->name, array->count, array->type, array->size);
			
			} else if (is_pointer(lst->next->tok->value) || (is_pointer(lst->tok->value))) {
				pointer->name = pointer_name_clear(lst->next->tok->value);
				pointer->type = lst->tok->type;
				switch (pointer->type) {
					case TYPE_CHAR:
						pointer->size = sizeof(char *);
						break;
					case TYPE_SHORT:
						pointer->size = sizeof(short *);
						break;
					case TYPE_INT:
						pointer->size = sizeof(int *);
						break;
					case TYPE_LONG:
						pointer->size = sizeof(long *);
						break;
				}
				//if (struc->level) {
				//	struc->items->item_type = ITEM_POINTER;
				//	item_add(struc->items, pointer, ITEM_POINTER);
				//}
				item_add(itm_lst, pointer, ITEM_POINTER);
				printf("%sptr: %s type: %d; size %d bytes\n", space, pointer->name, pointer->type, pointer->size);
			
			} else {
				variable->name = lst->next->tok->value;
				variable->type = lst->tok->type;
				switch (variable->type) {
					case TYPE_CHAR:
						variable->size = sizeof(char);
						break;
					case TYPE_SHORT:
						variable->size = sizeof(short);
						break;
					case TYPE_INT:
						variable->size = sizeof(int);
						break;
					case TYPE_LONG:
						variable->size = sizeof(long);
						break;
				}
				//if (struc->level) {
				//	struc->items->item_type = ITEM_VARIABLE;
				//	item_add(struc->items, variable, ITEM_VARIABLE);
				//}
				item_add(itm_lst, variable, ITEM_VARIABLE);
				printf("%svar: %s type: %d; size %d bytes\n", space, variable->name, variable->type, variable->size);
			}

		} else if (lst->tok->type == BRACKET_LFIGURE) {
			struct_level++;
			str_append(space, '\t');
		
		} else if (lst->tok->type == BRACKET_RFIGURE) {
			struct_level--;
			struct_inside--;
			space[strlen(space) - 1] = '\0';
			return itm_lst;
		
		} else if (lst->tok->type == IDENTIFIER) {
			/* Try to determine is it pointer or not */
		}
		
		lst = lst->next;
	} while (lst->tok != NULL);
	return itm_lst;
}

так у меня уже есть токенайзер. Он сделал мне связный список токенов. Обхожу как обычный список. В коде это видно.

Тебе нужен поиск в ширину?

как хорошо что я пишу на питоне

не совсем. Это же не поиск. Это обычный обход

> Это же не поиск. Это обычный обход

И что? При поиске делается «обычный обход». Алгоритм «обычного обхода» тот же.

Обхожу как обычный список

Если при обходе попадаешь на уже обработанные токены, то ты что-то неправильно делаешь.

Да, это я и так понимаю, вот и пытаюсь понять, что я делаю неправильно :)

а можно поинтересоваться, почему вы при входе во вложенную структуру (COMPLEX_STRUCT) не плюсуете struct_level, а при выходе минусуете? Впрочем, это не очень важно. Так же вы плюсуете в случае вложенной структуры (COMPLEX_STRUCT) struct_inside, однако минусуете его всегда. Я конечно не знаю, что у вас там за дерево строится, но, имхо, со счетчиками у вас беда.

Присмотритесь вот к этому условию в свете моего предыдущего поста:

if (struct_inside == 0) 
		lst = lst->head;

struct_inside плюсую при входе - минусую перед выходом из функции (когда находит правую фигурную скобку)

У вас две точки входа. И работают они по разному, а выход один и работает всегда одинаково.

не пиши такие длинные функции, в них трудно ловить ошибки и трудно анализировать

Изначально тупой вопрос, имхо

>Как сделать так, чтобы лексер входил в екурсию, парсил содержимое внутренного блока

Задача и смысл существования лексера - бить вход на токены.
Парсингом должен заниматься парсер.

Куда более корректно вопрос звучал бы:
Какую грамматику должен реализовать парсер чтобы, он «пропускал содержимое внутреннего блока, а приступал к следующему за ним токену?»

Ну как-то так имхо. И ответ и код на поставленный вопрос довольно просты.

из исходников компилятора я выделил токенайзер (тот кто бьет на токены) и лексер (тот кто сортирует лексемы). Парсер - это все вместе, имхо.

«все вместе» обычно зовется «транслатором»

Ну ладно, забыли про термины.

У тебя вроде бы логическая накладка:
раз: вложенность неограничена.
два:внутренного блока
три: пропускал содержимое внутреннего блока
пропускать содержимое какого из внутренних блоков?

Рекурсивный обход. Деревья. (комментарий)

Рекурсивный обход. Деревья. (комментарий)

То есть, он после ухода «в глубину» он должен пропускать вложение {} и приступать к следующему не вложенному токену.

Ты после вызова «2» что-нибудь типа позиции в потоке возвращаешь в вызов «1»?

нет, не возвращаю. Возвращаю только поддерево.

Ого! Ты физическое АСТ построил!
Это практически необходимо???

Короче, походу не совсем верная последовательность действий, имхо.Я бы делал так:
1. сформировать вход для парсера
2. рекурсивно выделить в анализируемом потоке диапазон, соответствующий вложению
3. для каждого или некоторого из диапазонов выстроить дереао.

У тебя вроде как наоборот - ты сделал дерево и теперь не знаешь что с ним делать, ну в смысле - стопорнулся на алгоритме перехода к ближайшему листу из заданного узла.

Да, это практическая необходимость. Если делать 1-2-3, то это медленнее и больше памяти надо, вроде. Я пытаюсь совмещать все, значит надо просто передавать параметр указатель на следующую позицию, после выхода из рекурсии. Попробую так.

Ну так это обычная рекурсия, на чем пишешь?

Ясно

Если делать 1-2-3, то это медленнее и больше памяти надо

вроде

Именно! Зачем тебе хранить список токенов?

> пытаюсь понять, что я делаю неправильно :)

Код не читал. Ты при входе/выходе не сохраняешь/восстанавливаешь контекст.

Лексеры (lex или что у тебя там) работают с регулярными(или т.н. автоматными) языками, то есть, грубо говоря с «плоскими», которые парсятся однопроходными DFA.

http://en.wikipedia.org/wiki/Regular_language

Рекурсии, потенциально требующей бэктрекинга в регулярных языках быть не может просто по определению!

Парсингом языков, в которых есть такие рекурсивно вложенные блоки, как ты описал, должны заниматься парсеры.

Про парсеры иди смотри википедию:

http://en.wikipedia.org/wiki/Recursive_descent_parser

http://en.wikipedia.org/wiki/LL_parser

http://en.wikipedia.org/wiki/LR_parser

http://en.wikipedia.org/wiki/GLR_parser

http://en.wikipedia.org/wiki/Parsing_expression_grammar

lovesan

щас ты его научишь, он еще LR «изобретет»

Суй везде &lst (вместо lst), чтобы весь стек вызовов двигал /один и тот же/ лист, а не только локальные указатели.

А вообще тут нужен yacc.

%token SOME
%start mb_items
%%
item: SOME ';'
    | '{' mb_items '}'
    ;
mb_items:
        | mb_items item
        ;
%%

yacc генерирует слишком большой код, я пробовал.

Что значит «слишком большой»? Посмотри на свой код сначала, это же огромная и вообще ужасная и непонятная каша, просто понос из буковок какой-то.

А вообще, yacc/bison генерируют автоматы для LALR-парсеров - снаружи выглядит м.б. жестковато, но работает быстро(O(n) от размера ввода), быстрее чем тот хлам, который ты сделал, ну а по памяти там O(n) от глубины дерева разбора, что тоже не сильно много, учитывая что внутренние структуры парсеров небольшие.

Но если так приперло _не_использовать_ генератор парсеров(хотя это просто луддитство, так как генератор будет наилучшим выбором в твоем случае), то, если язык позволяет, можно задрочиться, привести грамматику к LL(1)-виду(left-factoring плюс устранение левой рекурсии), и написать простой предиктивный рекурсивно-нисходящий парсер по LL(1); Но вот если язык к LL(1) не приводим, то придется написать рекурсивный нисходящий парсер с бэктрекингом(и это будет дико тормозить), либо с мемоизацией(т.н. packrat-парсер, и это будет дико жрать память), а ведь всего-то надо было взять генератор по LALR(1).

Просто пойми, по-другому твою задачу не решить никак. Нельзя немножко подкрутить лексер и довести его до разбора такого текста, как у тебя.

Это все-равно что пытаться распарсить HTML регексами - в итоге выйдет куча говнокода(типа как твоя куча выше), которая либо просто не работает, либо криво велосипедит один из давно известных алгоритмов, для которого и так существует куча реализаций.

Вот прислушайся уж ко мнению, сделай одолжение. Разбор текста, содержащего структуру, это одна из моих основных специализаций, и с этим связан мой будущий стартап, для которого я уже сейчас пишу код.

lovesan

Это маразм. Даже при тупом рекурсивном вызове такое поведение будет ошибочным.

в метакоде: [code] func parseToken(tokenEntity){} func parse(iterator i) { while(i.hasNext()) { var e = i.nextEntity(); parseToken(e); if(e.isComplex()) { parse(e.childsIterator()); } } } [/code]

и все! итерируя по детишкам ты ну никак, выйдя вверх по стеку не встретишь дочерний элемент.

_________

//wfrr

Это маразм. Даже при тупом рекурсивном вызове такое поведение будет ошибочным.

в метакоде:

func parseToken(tokenEntity){}
func parse(iterator i) {
  while(i.hasNext()) {
    var e = i.nextEntity();
    parseToken(e);
    if(e.isComplex()) {
      parse(e.childsIterator());
    }
  }
}

и все! итерируя по детишкам ты ну никак, выйдя вверх по стеку не встретишь дочерний элемент.

_________

//wfrr

_________

//wfrr

_________

//wfrr