Xpoint
   [напомнить пароль]

Проектирование конечного автомата (парсинг)

Метки: [без меток]
2007-12-10 13:33:00 [обр] Андрей Анатольич+(0/46)[досье]

Нужно выделить из текста лексемы.

Пример текста:

My name is {name}!

( Специально привел банальный пример. )
Лексема тут это — name.
Необходимо решить задачу с применением метода конечных автоматов. И тут у меня возникли трудности — никак не могу описать все возможные состояния автомата (мозг отказывается понимать) и, соответственно, не получается создать матрицу переходов состояний для символов.

Кто умеет это — направьте на путь (ссылок на доки не надо, т.к. перечитал уйму). Хорошо бы пример матрицы переходов, с комментариями. Буду сказочно благодарен!

спустя 1 час 5 минут [обр] Дмитрий(0/4)[досье]

Состояния

START - начало
CHAR_RECEIVED - получен символ
LBRACKET_RECEIVED - получена левая скобка
RBRACKET_RECEIVED - получена правая скобка
CHAR_INBRACKET_RECEIVED - получен символ внутри скобок
END - получен символ конца строки

Входные символы делить на 4 типа:
CHAR, LBRACKET, RBRACKET, EOF - это входные слова автомата

таблица переходов

CHARLBRACKETRBRACKETEOF
STARTCHAR_RECEIVEDLBRACKET_RECEIVED-END
CHAR_RECEIVEDCHAR_RECEIVEDLBRACKET_RECEIVED-END
LBRACKET_RECEIVEDCHAR_INBRACKET_RECEIVED-RBRACKET_RECEIVED-
RBRACKET_RECEIVEDCHAR_RECEIVEDLBRACKET_RECEIVED-END
CHAR_INBRACKET_RECEIVEDCHAR_INBRACKET_RECEIVED-RBRACKET_RECEIVED-

прочерки стоят в переходах, определяющих синтаксическую ошибку.

По состояниям CHAR_RECEIVED, CHAR_INBRACKET_RECEIVED следует копить входящие символы и по сотсояниям EOF, RBRACKET_RECEIVED и LBRACKET_RECEIVED выкидывать их (последнее состоянии свидетельствует о типе выдаваемого слова - внутри скобок или нет)

спустя 5 минут [обр] Андрей Анатольич+(0/46)[досье]

Вау! Реально, сказочно благодарен за развёрнутый ответ! Спасибо, Дмитрий[досье]!

Буду разбираться!

спустя 7 минут [обр] Андрей Анатольич+(0/46)[досье]
Дмитрий[досье], крайняя левая колонка таблицы — это первоначальные состояния автомата, ведь так?
спустя 10 минут [обр] Дмитрий(0/4)[досье]
Это все состояния автомата. Первоначальное одно - START
спустя 1 день 1 час [обр] Андрей Анатольич+(0/46)[досье]

Еще вопрос.

Если в тексте встречаются блоки, допустим, такие:

{block variable_name}
   some text
{/block}

Как строить автомат сканера в таких случаях? Нужно ведь знать, что у блока должен быть и конец блока. Что то не соображу )-8

спустя 5 минут [обр] Dennis F. Latypoff aka funky_dennis(0/84)[досье]
Андрей Анатольич[досье]
стек
спустя 1 минуту [обр] Андрей Анатольич+(0/46)[досье]

Я подумал — а все таки более правильно будет, сначала разбивать текст на токены, а затем уже отдельной функцией со своим автоматом проверять синтаксис? То есть:

  • Токенизация (разбиение текста на токены без проверки синтаксиса)
  • Проверка синтаксиса
  • Трансляция текста во что-нибудь нужное

Я ничего не путаю?

спустя 1 минуту [обр] Андрей Анатольич+(0/46)[досье]
стек
Dennis F. Latypoff aka funky_dennis[досье]
А подробнее? Интересует реализация или, хотя бы, словесное описание.
спустя 1 минуту [обр] Дмитрий(0/4)[досье]

Читайте"автоматы с магазинной памятью"

Я подумал — а все таки более правильно будет, сначала разбивать текст на токены, а затем уже отдельной функцией со своим автоматом проверять синтаксис?

Правильно, вы ничего не путаете. Классически принято разбивать синтаксический и лексический анализ

спустя 2 минуты [обр] Dennis F. Latypoff aka funky_dennis(0/84)[досье]
Андрей Анатольич[досье]
подробнее в гугле
спустя 1 минуту [обр] Дмитрий(0/4)[досье]

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

Т.е. синтаксический анализ - автоматом, лексический анализ - чем-то другим (возможно рожденным из автомата)

спустя 7 минут [обр] Андрей Анатольич+(0/46)[досье]

Дмитрий[досье]
В смысле, нерегулярность заключается в том, что variable_name может быть как массивом так и bool переменной?


Простите, что так много возможно глупых вопросов, просто я гуманитарий и полез непонятно куда (-:

спустя 17 минут [обр] Дмитрий(0/4)[досье]
Нерегулярность - воспринимай как невозможность описать язык регулярным выражением (опять же классическим).
Применительно к этому примеру - нет такого регулярного выражения, которое бы обеспечило совпадение "block" в открывающем и закрывающем теге.
спустя 20 часов [обр] Андрей Анатольич+(0/46)[досье]
лексический анализ - чем-то другим (возможно рожденным из автомата)
Чем? Я в ступоре. Залезть, что-ли в исходники Firefox'a? =)
спустя 1 час 33 минуты [обр] Дмитрий(0/4)[досье]
Я тоже пока не знаю. В простейшем случае можно придумать что-то корявое, чтобы построить дерево документа. Разумеется это что-то должно использовать стек.
спустя 18 минут [обр] Андрей Анатольич+(0/46)[досье]

Дмитрий[досье] В принципе да, тут без дерева не обойтись. По дереву легче будет проверять синтаксис блоков.

OFF:

Порылся в исходных кодах Firefox (в HTML токенайзере). Это жесть (практически ничего не понял =) ).

спустя 22 часа [обр] Андрей Анатольич+(0/46)[досье]
Т.е. синтаксический анализ - автоматом, лексический анализ - чем-то другим

Так ведь получается что лексический анализ (токенизацию) запросто можно сделать и автоматом, блоки тут н помеха.

И, я придумал, как организовать синтаксический анализ:

Автомат находит начало блока и запоминает - нашли начало блока.
Если после начала блока находим еще одно начало блока, но не находим
конца блока - инкрементируем переменную запоминаний.

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

Вот таким образом можно проанализировать синтаксис блоков.

спустя 1 час 36 минут [обр] Дмитрий(0/4)[досье]
Вы косвенно описали работу автомата с магазинной памятью. Запоминание происходит в стек.
Но как только автомат начинает оперировать такими понятиями, как "начало блока X" или "конец блока X", он уже перестает быть автоматом, если только это не является входным словом. Если словарь "тегов" заранее известен - то достаточно сделать их выходными словами (по 2 на каждый тег) и описать матрицу переходов для автомата с магазинной памятью и задача будет решена. Если же не известно какие могут быть теги, то автомат тут не сработает - он не сможет сопоставить какой закрывающий тег должен соответствовать открывающему. В этом заключается нерегулярность такого языка.
Можно построить что-то напоминающее автомат (обладающее состояниями, входными словами и схемой переходов), но это "что-то" не будет автоматом
Powered by POEM™ Engine Copyright © 2002-2005