рука, кодирующая синтаксический анализатор

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

Некоторые вещи, которые я бы порекомендовал получить для справки
1. Хороший дизайн для вашего сканера / лексера, это то, что будет маркировать ваш исходный код для вашего анализатора.
2. Следующая вещь - парсер, если у вас есть хороший ebnf для исходного языка, парсер обычно может довольно неплохо перевести в рекурсивный приличный парсер.
3. Другая структура данных, которая вам действительно понадобится, - это таблица символов. Это может быть как простая хеш-таблица, так и сложная, как древовидная структура, которая может представлять сложные структуры записей и т. Д. Я думаю, что для CSS вы можете быть где-то посередине.
4. И, наконец, вы хотите заняться генерацией кода. У вас есть много вариантов здесь. Для переводчика вы можете просто интерпретировать на лету, когда вы анализируете код. Лучшим подходом может быть создание for i-кода, для которого вы затем можете написать iterpreter, а затем даже компилятор. Конечно, для платформы .NET вы можете напрямую сгенерировать IL (вероятно, неприменимо для CSS :))


Для справки, я полагаю, вы не сильно разбираетесь в глубокая теория и я вас не виню. Действительно хорошей отправной точкой для получения основ без сложного кода, если вы не возражаете против Паскаля, который является Джек Креншоу «Давайте построим компилятор»
http://compilers.iecc.com / crenshaw /
Удачи. Уверен, вам понравится этот проект.

Вам нужно написать свой собственный рекурсивный анализатор спуска из вашего BNF / EBNF. Недавно мне пришлось написать свою собственную, и эта страница мне очень помогла. Я не совсем понимаю, что вы имеете в виду под «просто кодом». Вы имеете в виду, что хотите знать, как написать свой собственный рекурсивный синтаксический анализатор?

Если вы хотите это сделать, вам сначала нужно иметь свою грамматику. Если у вас есть EBNF / BNF, синтаксический анализатор может быть легко написан с его помощью.

Первое, что я сделал, когда написал свой синтаксический анализатор, - это прочитал все, а затем размечал текст.Таким образом, я фактически получил массив токенов, который я рассматривал как стек. Чтобы уменьшить многословие / накладные расходы, связанные с извлечением значения из стека и последующим его повторным включением, если оно вам не требуется, вы можете использовать метод peek , который просто возвращает верхнее значение в стеке, не всплывая. Это.

ОБНОВЛЕНИЕ

На основании вашего комментария мне пришлось с нуля написать парсер рекурсивного спуска в Javascript. Вы можете ознакомиться с парсером здесь . Просто найдите функцию constraints . Я написал свою собственную функцию tokenize для токенизации ввода. Я также написал еще одну удобную функцию ( peek , о которой я упоминал ранее). Синтаксический анализатор выполняет синтаксический анализ в соответствии с EBNF здесь .

Мне потребовалось некоторое время, чтобы понять это, потому что прошло много лет с тех пор, как я написал синтаксический анализатор (последний раз я писал его в школе!), Но поверьте мне, как только вы его получите, вы получите Это. Я надеюсь, что мой пример поможет вам продвинуться дальше.

ДРУГОЕ ОБНОВЛЕНИЕ

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

 function tokenize(options) {
            var str = options.str;
            var delimiters = options.delimiters.split("");
            var returnDelimiters = options.returnDelimiters || false;
            var returnEmptyTokens = options.returnEmptyTokens || false;
            var tokens = new Array();
            var lastTokenIndex = 0;

            for(var i = 0; i < str.length; i++) {
                if(exists(delimiters, str[i])) {
                    var token = str.substring(lastTokenIndex, i);

                    if(token.length == 0) {
                        if(returnEmptyTokens) {
                            tokens.push(token);
                        }
                    }

                    else {
                        tokens.push(token);
                    }

                    if(returnDelimiters) {
                        tokens.push(str[i]);
                    }

                    lastTokenIndex = i + 1;
                }
            }

            if(lastTokenIndex < str.length) {
                var token = str.substring(lastTokenIndex, str.length);
                token = token.replace(/^\s+/, "").replace(/\s+$/, "");

                if(token.length == 0) {
                    if(returnEmptyTokens) {
                        tokens.push(token);
                    }
                }

                else {
                    tokens.push(token);
                }
            }

            return tokens;
        }

Судя по вашему коду, похоже, что вы читаете, токенизируете и анализируете одновременно - я предполагаю, что это то, что делает синтаксический анализатор сдвига-уменьшения? Поток того, что у меня есть, - это сначала токенизация для создания стека токенов, а затем отправка токенов через синтаксический анализатор с рекурсивным спуском.

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

Из литературы я бы порекомендовал несколько старых работ Никлауса Вирта. Он умеет писать. Я использовал Алгоритмы + Структуры данных = Программы , но вы можете найти его Конструкция компилятора в Интернете.

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

При сдвиге-сокращении термин «сокращение» относится к операции, выполняемой над явно поддерживаемым стеком маркеров. Например, если вершина стека стала Term, Operator, Term , тогда может быть применено правило сокращения, приводящее к Expression в качестве замены шаблона.Правила сокращения явно закодированы в структуре данных, используемой синтаксическим анализатором сдвига-уменьшения; в результате все правила редукции можно найти в одном и том же месте исходного кода.

Подход с уменьшением сдвига дает несколько преимуществ по сравнению с рекурсивным спуском. На субъективном уровне я считаю, что shift-reduce легче читать и поддерживать, чем рекурсивный спуск. Более объективно сдвиг-reduce позволяет синтаксическому анализатору получать более информативные сообщения об ошибках при возникновении неожиданного токена.

В частности, поскольку синтаксический анализатор сдвиг-сокращение имеет явное кодирование правил для выполнения «сокращений», синтаксический анализатор легко расширяется, чтобы сформулировать, какие типы токенов могли бы на законных основаниях следовать. (например, "; ожидается"). Реализация рекурсивного спуска не может быть легко расширена, чтобы сделать то же самое.

Отличной книгой об обоих типах синтаксического анализатора и компромиссах при реализации различных видов сдвига-сокращения является «Введение в конструкцию компилятора» Томаса У. Парсонса .

Shift-уменьшение иногда называют синтаксическим анализом «снизу вверх», а рекурсивный спуск иногда называют синтаксическим анализом «сверху вниз». В используемой аналогии узлы, составленные с наивысшим приоритетом (например, «факторы» в выражении умножения), считаются «внизу» синтаксического анализа. Это соответствует той же аналогии, используемой в «спуске» или «рекурсивном спуске».