Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Написание парсера. / 4 сообщений из 4, страница 1 из 1
03.09.2014, 23:43
    #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
| Ответить | Цитировать | Написать  
04.09.2014, 02:06
    #38736960
White Owl
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Написание парсера.
Читать про CFG . Там рассказано как задавать зависимости между for, скобочками, выражениями и всем остальным. В терминах CFG то что ты уже наваял это зачаток поиска "терминалов". Это обычно называют лексером или токенайзером.
Теперь тебе надо придумать как задать их отношения между собой, собственно как задать правила грамматики. Что должно идти за токеном for? Скобка? Какая? А если там другая скобка, то что? .... задаешь ответы на все эти вопросы и получаешь собственно парсер.
Как писать этот парсер? Читать про DFA . Алфавитом для DFA будут служить токены, а текущие состояния будут показывать куда именно в строящемся дереве надо класть очередной токен.


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

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


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


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

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


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

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

см. Dragon book

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

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

Хороший edsl для этого можно полусить применяя концепцию parser combinators
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Написание парсера. / 4 сообщений из 4, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 304ms
Закрыть
start [/forum/topic.php?fid=16&tablet=1&tid=1341243]:
 0ms
get settings:
 8ms
get forum list:
 16ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 28ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 32ms
get tp. blocked users:
 1ms
others: 206ms
total:  304ms
x
x
Закрыть


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