Ручное кодирование парсера

Ответ 1

То, что вы пишете, называется автоматом pushdown. Обычно это больше, чем вам нужно, чтобы написать лексер, это, безусловно, чрезмерно, если вы пишете лексер для современного языка, такого как CSS. Рекурсивный синтаксический анализатор близких по силе к автомату выталкивания, но рекурсивные парсеры спуска гораздо проще писать и понимать. Большинство генераторов парсеров генерируют автоматы толкания.

Лексеры почти всегда записываются как машины с конечным состоянием, т.е. как ваш код, кроме как избавиться от объекта "стек". Машины конечного состояния тесно связаны с регулярными выражениями (фактически, они доказуемо эквивалентны друг другу). При разработке такого синтаксического анализа обычно начинается с регулярных выражений и используется для создания детерминированного конечного автомата с некоторым дополнительным кодом в переходах для записи начала и конца каждого токена.

Есть инструменты для этого. Инструмент lex и его потомки хорошо известны и переведены на многие языки. Инструментальная цепочка ANTLR также имеет лексический компонент. Мой предпочтительный инструмент ragel на платформах, которые его поддерживают. Практически мало пользы от написания лексера вручную, и код, созданный этими инструментами, вероятно, будет быстрее и надежнее.

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

function readToken() // note: returns only one token each time
    while !eof
        c = peekChar()
        if c in A-Za-z
            return readIdentifier()
        else if c in 0-9
            return readInteger()
        else if c in ' \n\r\t\v\f'
            nextChar()
        ...
    return EOF

function readIdentifier()
    ident = ""
    while !eof
        c = nextChar()
        if c in A-Za-z0-9
            ident.append(c)
        else
            return Token(Identifier, ident)
            // or maybe...
            return Identifier(ident)

Затем вы можете написать свой парсер в качестве рекурсивного анализатора спуска. Не пытайтесь комбинировать лексер/парсер в одном, это приводит к полному беспорядку кода. (По словам автора Parsec, он медленнее тоже).

Ответ 2

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

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


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

Ответ 3

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

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

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

UPDATE

Основываясь на вашем комментарии, мне пришлось писать парсер с рекурсивным спусками в 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;
        }

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

Ответ 4

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

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

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

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

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

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

Ответ 5

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

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