ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Написание парсера.
4 сообщений из 4, страница 1 из 1
Написание парсера.
    #38736921
user199617
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
user199617
Гость
Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
function Tokenizer(patterns) {
    this.regExps = {}
    for (var p in patterns) {
        this.regExps[p] = new RegExp('^' + patterns[p], 'g');
    }  
}

Tokenizer.prototype = {
    parse: function (src) {
        var p,
            re,
            offset = 0,
            matches,
            tokens = [];
        while (src.length) {
            for (p in this.regExps) {
                re = this.regExps[p];
                matches = re.exec(src);
                if (matches) {
                    break;
                }
            }
            if (matches) {
                tokens.push({
                    type: p,
                    value: matches.shift(),
                    groups: Array.prototype.slice.call(matches),
                    offset: offset,
                });
                src = src.substr(re.lastIndex);
                offset += re.lastIndex;
                re.lastIndex = 0;     
                continue;
            }
            throw new Error('Unknown token at offset ' + offset + '.');
        }
        return tokens;
    },
};

function testTokenizer() {
    return new Tokenizer({
        'whitespace': '\\s+',
        'operator': '[-+*/()]',
        'number': '(?:\\d*\\.\\d+|\\d+)',
    }).parse('180 / 3.1415926535897932384626433832795');
}



Это пример простого (моего) токенайзера на js. Для подсветки синтаксиса или какого-нибудь простого калькулятора он подходит хорошо. Меня интересуют примеры как можно сделать управление состояними парсера. Ну например есть оператор for (expression; expression; expression). Мы в тексте программы встречаем ключевое слово for, далее должна идти открывающая скобка, потом выражение и т.д. Или встречаем кавычку (") переключаем парсер в режим парсинга строки(в строках есть escape-последовательности типа \xHH и \uHHHH). Интересуют неготовые решения, а процесс написания с нуля.
...
Рейтинг: 0 / 0
03.09.2014, 23:43
| Ответить | Цитировать | Написать  
Написание парсера.
    #38736960
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
Читать про CFG . Там рассказано как задавать зависимости между for, скобочками, выражениями и всем остальным. В терминах CFG то что ты уже наваял это зачаток поиска "терминалов". Это обычно называют лексером или токенайзером.
Теперь тебе надо придумать как задать их отношения между собой, собственно как задать правила грамматики. Что должно идти за токеном for? Скобка? Какая? А если там другая скобка, то что? .... задаешь ответы на все эти вопросы и получаешь собственно парсер.
Как писать этот парсер? Читать про DFA . Алфавитом для DFA будут служить токены, а текущие состояния будут показывать куда именно в строящемся дереве надо класть очередной токен.


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

А исполнитель уже будет рекурсивно бегать по этому дереву и смотреть: Нода с плюсиком? Мы уже высчитали всех детей этой ноды? Нет? Ныряем глубже и обрабатываем детей. Листик с цифрой? Возвращаемся на уровень вверх. Закончили с детьми? Складываем всех детей, назначаем результат нашей ноде с плюсиком и возвращаемся на уровень вверх. И повторяем пока не дойдем до корня который и будет результатом.


Все очень просто на самом деле.
...
Рейтинг: 0 / 0
04.09.2014, 02:06
| Ответить | Цитировать | Написать  
Написание парсера.
    #38737032
Фотография skyANA
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
skyANA
Участник
White OwlЧитать про CFG . Там рассказано как задавать зависимости между for, скобочками, выражениями и всем остальным. В терминах CFG то что ты уже наваял это зачаток поиска "терминалов". Это обычно называют лексером или токенайзером.
Теперь тебе надо придумать как задать их отношения между собой, собственно как задать правила грамматики. Что должно идти за токеном for? Скобка? Какая? А если там другая скобка, то что? .... задаешь ответы на все эти вопросы и получаешь собственно парсер.
Как писать этот парсер? Читать про DFA . Алфавитом для DFA будут служить токены, а текущие состояния будут показывать куда именно в строящемся дереве надо класть очередной токен.


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

А исполнитель уже будет рекурсивно бегать по этому дереву и смотреть: Нода с плюсиком? Мы уже высчитали всех детей этой ноды? Нет? Ныряем глубже и обрабатываем детей. Листик с цифрой? Возвращаемся на уровень вверх. Закончили с детьми? Складываем всех детей, назначаем результат нашей ноде с плюсиком и возвращаемся на уровень вверх. И повторяем пока не дойдем до корня который и будет результатом.


Все очень просто на самом деле.+1

Для примера можно глянуть исходники StringTemplate различных версий.
...
Рейтинг: 0 / 0
04.09.2014, 08:12
| Ответить | Цитировать | Написать  
Написание парсера.
    #38737139
WebSharper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
WebSharper
Участник
user199617Это пример простого (моего) токенайзера на js. Для подсветки синтаксиса или какого-нибудь простого калькулятора он подходит хорошо. Меня интересуют примеры как можно сделать управление состояними парсера. Ну например есть оператор for (expression; expression; expression). Мы в тексте программы встречаем ключевое слово for, далее должна идти открывающая скобка, потом выражение и т.д. Или встречаем кавычку (") переключаем парсер в режим парсинга строки(в строках есть escape-последовательности типа \xHH и \uHHHH). Интересуют неготовые решения, а процесс написания с нуля.

см. Dragon book

1. Написать грамматику языка
2. Определить к какому классу относится грамматика
3. Найти алгоритм для разбора грамматики
4. Реализовать алгоритм

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

Хороший edsl для этого можно полусить применяя концепцию parser combinators
...
Рейтинг: 0 / 0
04.09.2014, 10:09
| Ответить | Цитировать | Написать  
4 сообщений из 4, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Написание парсера.
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&fpage=42&tid=1341243]:
 0ms
get settings:
 8ms
get forum list:
 9ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 44ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 26ms
get tp. blocked users:
 1ms
others: 226ms
total:  327ms
созд. / загр.: 327ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]