Разбор вложенных структур (парсинг CSS)
 

Задача не совсем типичная, хочу написать небольшой анализатор кода для разбора вложенных структур, которые должны транслироваться в валидный CSS.
Однако не получается захватить идентификаторы родительских селекторов.

Пример вложенной структуры:

#foo {
        border: 1px;
        a {
                border: 2px;
        }
        b {
                border: 3px;
                c {
                        border: 4px; /* comment */
                }
        }
}

То, что я хочу получить в итоге:

#foo {
        border: 1px;
}
 
#foo a {
        border: 2px;
}
 
#foo b {
        border: 3px;
}
 
#foo b c {
        border: 4px; /* comment */
}

Пока что получилось добиться такого результата:

c {
	border: 4px; /* comment */
}

b {
	border: 3px;
}

a {
	border: 2px;
}

#foo {
	border: 1px;
}

Код, который выполняет разбор (на С++ правда, лень было переписывать на JS, но надеюсь будет понятно, т.к. там нужно только итератор на charAt() заменить ) :)

#include <iostream>
#include <iterator>
#include <string>

using namespace std;

int main() {

    string str = "\
    #foo {\
        border: 1px;\
        a {\
            border: 2px;\
        }\
        b {\
            border: 3px;\
            c {\
                border: 4px; /* comment */\
            }\
        }\
    }";

    string::const_iterator i = str.end(), begin = str.begin(), end;

    while (i != begin) {
        if (*i == ';' || (*i == '/' && *(i-1) == '*')) {
            end = i++;

            while (*i-- != '{');

            while (true) {
                if (*i == ';' || *i == '}' || *i == '{' || i == begin)
                    break;
                i--;
            }

            string item(++i, ++end);
            cout << item << "}" << endl;
        }
        i--;
    }

    return 0;
}

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

Иными словами мне нужно получить массив с такими селекторами:

['#foo', '#foo a', '#foo b', '#foo b c']

Если есть какие-то идеи по поводу алгоритма с удовольствием выслушаю.

мне кажется такие вещи надо писать как автомат, контролируя логику парсера матрицей переходов, а не хардкорить ее

В идеале да, так оно и будет (пример грамматики).
Сейчас же мне просто нужно понять сам алгоритм получения родительских селекторов для каждого блока, с какой стороны подобраться.

Ну есть тупой вариант, - рекурсивный реплейс снизу.
Т.е. регой типа /([^{\s]+)\s*\{([^}]+)\}/g, рекурсивно пройтись, заменяя на идентификаторы, а потом обратно - идентификаторы на дополненные значения.

А вот как умно и красиво - навскидку не скажешь.)

Не регой такие дела не далают. Согласно правилам синтаксического анализа считывать нужно посимвольно запоминая уровни. Вот только как это грамотно сделать большой вопрос.

Ну нязнанаю, парсинг обычно регой и делают.)
Посимвольно это вообще заумь будет, а на счёт скорости не ясно.
С другой стороны если не лень уйти в далёкие дали, то наверное можно.

Разбор email адресов и пр. да, но в формальной грамматике все посимвольно.
Может по тому что в С никогда не было регекстов, а в С++ они появились только в сентябре прошлого года (шутка)

Не совсем понял что ты имел ввиду, как сами идентификаторы получить, чтобы учесть дочерние уровни?

Максимально тупо. Сейчас набросаю.)

Сделано на коленке, не красиво, не оптимизировано, но суть отображает.

<div>

#foo {
        border: 1px;
        a {
                border: 2px;
        }
        b {
                border: 3px;
                c {
                        border: 4px; /* comment */
                }
        }
}


</div>
<script>
d=document.getElementsByTagName('div')[0].innerHTML;
function css(str){
  var result=[],
  re = /([^{\s]+)\s*\{[^}{]+\}/g,
  re2 = /(\d+)_array/g,
  placer = function( all , selector){
    var lower='';  
    all = all.replace( re2 ,function(x,y){
      result[y] = selector + ' ' + result[y];
      lower += x;
      return ''
    })
    return result.push( all + '\n') - 1 + '_array' + lower;
  }
  while(~str.indexOf('{'))alert( str=str.replace( re , placer ) );
  return str.replace( re2 , function(ar,ar){ return result[ar] } )
}
alert(css(d))
</script>

Хм... понял, подумаю как без регексов переписать)

Одногруппник диплом такой делал http://code.google.com/p/extcss/ может быть будет полезен код, хоть и на пхп. Эту штуку он использовал, пока работал верстальщиком.

Ага, то что надо.
Не особо важно, главное алгоритм. Мне все равно на С++ писать)

monolithed, ну, в принципе, сами регэкспы работают посимвольно. Поэтому можно считать, что вы просто сэкономили себе время)

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

В С++ нет аналогов решению с регексами, по этому придется все-таки копать по ссылке Octane, там как раз без них.

Да, уже понял, что у вас C++ (хотя наверняка есть либы под него).

В новом стандарте С++11 есть регексы, просто сама идеология очень сильно отличается

По ссылке Octane, всё тоже на регэкспах, только сложнее.)

Не совсем, фактически что мне нужно там выполняет этот кусок:

while($j>$j_begin) {
	if(preg_match('/}/', $text[$j])) {
		$j_temp_end = $j;
		
		while(1) {
			$j--;
			
			if(preg_match('/}/', $text[$j]))
				$z++;
				
			if(preg_match_all('/(.*){/U', $text[$j], $temp_vars, PREG_SET_ORDER)) {
				if(! $z) {
					$names[1] = $temp_vars[0][1];
					$recompile = 1;
					$j_temp_begin = $j;
					break;
				} 
				else {
					$z--;
				}
			}
		}
		break;
	}
 $j--;
}

А preg_match выполняет роль split'a

Правда я пока не понял как там имя селекторов получается :D