Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
Добрый день всем вопрос по лексическому анализу Например, у меня есть два минимальных ДКА, построенных по двум регулярным выражениям. Если я их объединю с помощью алгоритма "Subset construction" будет ли результирующий ДКА минимальным? PS: предположительно будет, но вот доказать не могу - не хочется алгоритм Hopcroft-а только для проверки делать ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.09.2016, 13:43 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
Не будет. Возьми простейший, но не оптимальный DFA и прогони его через алгоритм конвертации. Чаще всего ты получишь еще более не оптимальный автомат. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.09.2016, 20:15 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
White Owl, но если второй раз прогнать, количество сотояний же не увеличится дело в том что, у меня два минимальных ДКА соединяются собственно для их получения я использую Алгоритм Бржозовского , который как раз и содержит 2 вызова Subset construction ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.09.2016, 10:38 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
White Owl, т.е. используется одно начальное или результирующие состояния обоих ДКА в итоговом ДКА достижимы ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.09.2016, 10:55 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan)White Owl, но если второй раз прогнать, количество сотояний же не увеличится дело в том что, у меня два минимальных ДКА соединяются собственно для их получения я использую Алгоритм Бржозовского , который как раз и содержит 2 вызова Subset construction...ммм.... Так ты реши какой алгоритм ты используешь, Бржозовского или "Subset construction". Первый изначально оптимизатор, второй простейший конвертор. И да, когда ты изначально используешь оптимизатор, то и результат получается оптимизированный :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.09.2016, 19:18 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
White Owlkealon(Ruslan)White Owl, но если второй раз прогнать, количество сотояний же не увеличится дело в том что, у меня два минимальных ДКА соединяются собственно для их получения я использую Алгоритм Бржозовского , который как раз и содержит 2 вызова Subset construction...ммм.... Так ты реши какой алгоритм ты используешь, Бржозовского или "Subset construction". Первый изначально оптимизатор, второй простейший конвертор. И да, когда ты изначально используешь оптимизатор, то и результат получается оптимизированный :) видимо не так выражаюсь Бржозовского я не могу использовать для ловли различных финальных состояний, потому я его только для каждой отдельной строки использую и получаю для каждой лексемы минимальный ДКА. "Subset construction" я применяю для объединения правил в одну итоговую ДКА и по моему предположению результат будет минимальный ДКА (во всяком случае опровержения я пока получить не могу) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.09.2016, 22:51 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan)Бржозовского я не могу использовать для ловли различных финальных состоянийммм... мне кажется ты просто не правильно делаешь NFA. У тебя есть два DFA. Ты кладешь их на один общий лист, добавляешь новое состояние, делаешь из него эпсилон-переходы на стартовые состояния своих DFA. Обозначаешь это новое состояние стартовым. У тебя теперь имеется один цельный NFA с несколькими финальными состояниями. Добавь теперь еще одно состояние, сделай на него эпсилон-переходы из старых финальных, обозначь это второе новое состояние финальным. И теперь у тебя есть NFA с одним стартом и одним финалом. Всё. Можешь отдавать его на вход Бржозовскому и получать оптимизированный DFA. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.09.2016, 18:06 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
White Owlkealon(Ruslan)Бржозовского я не могу использовать для ловли различных финальных состоянийммм... мне кажется ты просто не правильно делаешь NFA. У тебя есть два DFA. Ты кладешь их на один общий лист, добавляешь новое состояние, делаешь из него эпсилон-переходы на стартовые состояния своих DFA. Обозначаешь это новое состояние стартовым. У тебя теперь имеется один цельный NFA с несколькими финальными состояниями. Добавь теперь еще одно состояние, сделай на него эпсилон-переходы из старых финальных, обозначь это второе новое состояние финальным. И теперь у тебя есть NFA с одним стартом и одним финалом. Всё. Можешь отдавать его на вход Бржозовскому и получать оптимизированный DFA. и зачем он такой нужен без определения типа результата? "Алгоритм Бржозовского" всё в кучу смешает ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.09.2016, 21:35 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan)и зачем он такой нужен без определения типа результата?Ну во первых, никаких "типов результата" быть не может. Смотри определение конечных автоматов. Они либо кончаются, либо нет. Для определения "как именно" закончилась работа, надо брать уже как минимум полноценную Машину Тьюринга, которая не только читает входную строку, но и пишет. А во вторых, с чего вдруг тебе понадобились разные финальные состояния? У тебя ж вроде изначальная задача была оптимизировать регулярное выражение через представление его в виде конечного автомата. Так? А регулярки и отвечают всего-лишь на вопрос "совпадает" или "не совпадает". Нету там нужды во множественных финалах. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.09.2016, 22:01 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
White Owl А регулярки и отвечают всего-лишь на вопрос "совпадает" или "не совпадает". Нету там нужды во множественных финалах. лексеру это нужно. не все финалы одинаковы ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.09.2016, 22:16 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
White Owl, в общем ответ нашёлся на простом примере, к сожалению отрицательный :-( 'ID1', 'a+b' Код: plaintext 1. 2. 3. 4. 5. 6. 'ID2', 'ab+' Код: plaintext 1. 2. 3. 4. 5. 6. совмещение: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.09.2016, 22:17 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
хотя нет, вру - разные ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.09.2016, 22:21 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan)White Owl А регулярки и отвечают всего-лишь на вопрос "совпадает" или "не совпадает". Нету там нужды во множественных финалах. лексеру это нужно. не все финалы одинаковыНо лексер это не конечный автомат. Лексер это простой перебор начала потока на соответствие нескольким шаблонам. И как только первый подходящий шаблон найден - запуск очередного раунда парсера с найденным токеном. После чего лексер стартует заново. Лексер по архитектуре это классическая TM с двумя лентами (ну или push-down automata которая в итоге всегда оставляет один элемент на стеке). Но в любом случае к нему нельзя подходить как к D/N конечным автоматам. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.09.2016, 22:30 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
White Owlkealon(Ruslan)пропущено... лексеру это нужно. не все финалы одинаковыНо лексер это не конечный автомат. Лексер это простой перебор начала потока на соответствие нескольким шаблонам. И как только первый подходящий шаблон найден - запуск очередного раунда парсера с найденным токеном. После чего лексер стартует заново. Лексер по архитектуре это классическая TM с двумя лентами (ну или push-down automata которая в итоге всегда оставляет один элемент на стеке). Но в любом случае к нему нельзя подходить как к D/N конечным автоматам. да.... ? а lex и flex по вашему как работают? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.09.2016, 22:36 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan)White Owlпропущено... Но лексер это не конечный автомат. Лексер это простой перебор начала потока на соответствие нескольким шаблонам. И как только первый подходящий шаблон найден - запуск очередного раунда парсера с найденным токеном. После чего лексер стартует заново. Лексер по архитектуре это классическая TM с двумя лентами (ну или push-down automata которая в итоге всегда оставляет один элемент на стеке). Но в любом случае к нему нельзя подходить как к D/N конечным автоматам. да.... ? а lex и flex по вашему как работают?А так и работают. Перебирают все известные шаблоны, пока не найдут первый подходящий и потом пишут в выходной поток идентификатор токена, либо сразу запускают парсер. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.09.2016, 22:53 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
White OwlПеребирают все известные шаблоны, пока не найдут первый подходящий это формально, в реальности там один ДКА на все шаблоны ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.09.2016, 23:15 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan)White OwlПеребирают все известные шаблоны, пока не найдут первый подходящий это формально, в реальности там один ДКА на все шаблоныТы ошибаешься. Ты не видишь разницы между Машиной Тьюринга и Детерминированным Конечным Автоматом? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.09.2016, 23:49 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
White Owl, типичный код любого адекватного лексера, в переменной Text текст для разбора Код: pascal 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. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. типичный вывод программы, аналогичной lex (ab.inc) лексика: 'ID1', 'a+b' 'ID2', 'ab+' Код: pascal 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. вывод с программы: Код: plaintext 1. 2. 3. 4. 5. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.09.2016, 06:58 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.09.2016, 10:23 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan), И чё? Что ты пытаешься доказать? Еще раз спрашиваю: Ты не видишь разницы между Машиной Тьюринга и Детерминированным Конечным Автоматом? Да, алгоритм Бржозовского к ТМ не применим. Вообще, до сих пор не существует полноценных оптимизаторов для ТМ. В общем, если ты хочешь оптимизировать распознавание лексем "оптимальным" автоматом - то тебе придется иметь несколько отдельных оптимальных автоматов и запускать каждый с нулевого состояния, если предыдущие не распознали свою лексему. А если хочешь смешать несколько слов в один общий автомат, то придется резать свой NFA на сегменты типа "первый сегмент распознает начало лексем от первой по десятую", "второй сегмент А занимается средними сегментами лексем с первой по пятую, а Второй-Б средними сегментами лексем с шестой по девятую". И на каждый из хвостов лексем выделяешь по своему сегменту. Потом каждый из сегментов по отдельности оптимизируешь. Примерно так, для твоих a+b и ab+: DFA1: a DFA2: a* DFA3: b DFA4: b* и отдельная схема переходов между автоматами, по достижению финального "Ок" в каждом. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.10.2016, 20:55 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
White Owlkealon(Ruslan), И чё? Что ты пытаешься доказать? Еще раз спрашиваю: Ты не видишь разницы между Машиной Тьюринга и Детерминированным Конечным Автоматом? Да, алгоритм Бржозовского к ТМ не применим. Вообще, до сих пор не существует полноценных оптимизаторов для ТМ. В общем, если ты хочешь оптимизировать распознавание лексем "оптимальным" автоматом - то тебе придется иметь несколько отдельных оптимальных автоматов и запускать каждый с нулевого состояния, если предыдущие не распознали свою лексему. А если хочешь смешать несколько слов в один общий автомат, то придется резать свой NFA на сегменты типа "первый сегмент распознает начало лексем от первой по десятую", "второй сегмент А занимается средними сегментами лексем с первой по пятую, а Второй-Б средними сегментами лексем с шестой по девятую". И на каждый из хвостов лексем выделяешь по своему сегменту. Потом каждый из сегментов по отдельности оптимизируешь. Примерно так, для твоих a+b и ab+: DFA1: a DFA2: a* DFA3: b DFA4: b* и отдельная схема переходов между автоматами, по достижению финального "Ок" в каждом. при чём тут машина Тьюринга, читайте пост Компиляция. 1: лексер внимательно часть "Как это работает?" нету никаких частей отдельных, всё в одном ДКА ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2016, 11:12 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan)при чём тут машина Тьюринга, читайте пост Компиляция. 1: лексер внимательно часть "Как это работает?" нету никаких частей отдельных, всё в одном ДКАНу вообще-то, автор статьи ошибается. Он так же как и ты не видит разницы между разными типами автоматов. "Работа flex заключается в том, что он строит ДКА по заданному набору регэкспов;" вот это как раз ложь. Оно не ДКА строит, а Машину Тьюринга. У TM, так же как и у DFA, есть таблица состояний и переходов между состояниями в зависимости от очередного символа во входящем потоке. Но в отличие от DFA, TM может внутри состояния сделать "еще что-то" кроме ожидания следующего символа. Это "еще что-то" чрезвычайно широко, это может быть и вывод символа на выходную ленту, и замена символа во входной ленте, и команда "сдвинуться обратно/вперед по входной ленте". И в том числе это может быть и сигнал "лексема найдена". Их (TM и DFA) различить очень просто: если находясь в каком-то состоянии мы просто ждем следующего символа на входе, то это DFA, а если внутри состояния что-то происходит - значит это уже TM. На Хабре бывает много хороших статей, но их далеко не всегда пишут люди с образованием... В общем, если хочешь понимать что такое конечные автоматы, почитай соответствующую литературу. Меня учили на основе вот этого учебника: https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X/ref=pd_sim_14_3?ie=UTF8&psc=1&refRID=5V3P1TR0K6GGPX1XS9A3 А сейчас Ахо преподает на основе другого учебника (я сам его не читал): https://www.amazon.com/Introduction-Automata-Theory-Languages-Computation/dp/0321455363/ref=sr_1_1?ie=UTF8&qid=1475591017&sr=8-1&keywords=9780321462251 Почитай любой из них, будет очень полезно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2016, 17:51 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
White OwlНу вообще-то, автор статьи ошибается. Он так же как и ты не видит разницы между разными типами автоматов. "Работа flex заключается в том, что он строит ДКА по заданному набору регэкспов;" вот это как раз ложь. Оно не ДКА строит, а Машину Тьюринга. У TM, так же как и у DFA, есть таблица состояний и переходов между состояниями в зависимости от очередного символа во входящем потоке. Но в отличие от DFA, TM может внутри состояния сделать "еще что-то" кроме ожидания следующего символа. Это "еще что-то" чрезвычайно широко, это может быть и вывод символа на выходную ленту, и замена символа во входной ленте, и команда "сдвинуться обратно/вперед по входной ленте". И в том числе это может быть и сигнал "лексема найдена". Их (TM и DFA) различить очень просто: если находясь в каком-то состоянии мы просто ждем следующего символа на входе, то это DFA, а если внутри состояния что-то происходит - значит это уже TM. На Хабре бывает много хороших статей, но их далеко не всегда пишут люди с образованием... автор статьи фактически расшифровывает "книгу дракона" главу 3-ю "Лексический анализ" Код: plaintext Неважно как лексер обрабатывает промежутоные состояния ДКА, сути это не меняет - тем более там только запоминание позиции и результата. Главное, что лексема идентифицируется за один проход по тексту(заглядываение вперёд не считаем - для большинства языков это один символ LR(1)), а не по всем входным регуляркам в отдельности. Практическое следствие из этого - хоть 2, хоть 1000 регулярок будет обрабатываться на тексте одинакового размера за практически одинаковое время ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2016, 20:04 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2016, 20:25 |
|
||
|
Лексический анализ, объединение двух ДКА
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan)автор статьи фактически расшифровывает "книгу дракона" главу 3-ю "Лексический анализ" Код: plaintext kealon(Ruslan)Неважно как лексер обрабатывает промежутоные состояния ДКА, сути это не меняет - тем более там только запоминание позиции и результата.Должен тебя огорчить, но это как раз важно. Ты же хочешь провести оптимизацию состояний и переходов между ними, верно? А это без понимания сути ты сделать не сможешь никак. И вот для этого тебе и надо понять во первых, что нету такой вещи как "промежуточные состояния ДКА". Ну не важно для ДКА ничего кроме стартового и финального состояний. Просто по сути самого конечного автомата - он стартует и останавливается, но он никогда не прерывается. Не предусмотрено в теории автоматов такой сущности как "промежуточное" состояние для конечного автомата. А как только ты эту сущность введешь, то ты сразу получишь машину тьюринга и мы опять придем к тому от чего начали. Не, я понимаю что учебники по теории читать скучно, но увы. Хочешь манипулировать автоматами состояний - придется их все-же прочитать. В Драконей Книге дается только их практическое применение в приложении к компилятором и совсем нет теории языков. Что в принципе не очень хорошо, но никто не заставляет жить только на ней одной. kealon(Ruslan)Главное, что лексема идентифицируется за один проход по тексту(заглядываение вперёд не считаем - для большинства языков это один символ LR(1)), а не по всем входным регуляркам в отдельности. Практическое следствие из этого - хоть 2, хоть 1000 регулярок будет обрабатываться на тексте одинакового размера за практически одинаковое время Да. И? В современных лексерах действительно все шаблоны проверяются одной общей TM. И ей действительно нет большой разницы 2 или 1000 шаблонов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.10.2016, 00:17 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=39318196&tid=1340263]: |
0ms |
get settings: |
10ms |
get forum list: |
16ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
195ms |
get topic data: |
13ms |
get forum data: |
3ms |
get page messages: |
65ms |
get tp. blocked users: |
2ms |
| others: | 15ms |
| total: | 327ms |

| 0 / 0 |
