Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Лексический анализ, объединение двух ДКА / 25 сообщений из 29, страница 1 из 2
26.09.2016, 13:43
    #39315595
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
Добрый день всем
вопрос по лексическому анализу

Например, у меня есть два минимальных ДКА, построенных по двум регулярным выражениям.
Если я их объединю с помощью алгоритма "Subset construction" будет ли результирующий ДКА минимальным?

PS: предположительно будет, но вот доказать не могу - не хочется алгоритм Hopcroft-а только для проверки делать
...
Рейтинг: 0 / 0
27.09.2016, 20:15
    #39316546
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
Не будет.
Возьми простейший, но не оптимальный DFA и прогони его через алгоритм конвертации. Чаще всего ты получишь еще более не оптимальный автомат.
...
Рейтинг: 0 / 0
28.09.2016, 10:38
    #39316742
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
White Owl,
но если второй раз прогнать, количество сотояний же не увеличится
дело в том что, у меня два минимальных ДКА соединяются
собственно для их получения я использую Алгоритм Бржозовского , который как раз и содержит 2 вызова Subset construction
...
Рейтинг: 0 / 0
28.09.2016, 10:55
    #39316750
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
White Owl,

т.е.
используется одно начальное или

результирующие состояния обоих ДКА в итоговом ДКА достижимы
...
Рейтинг: 0 / 0
28.09.2016, 19:18
    #39317276
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
kealon(Ruslan)White Owl,
но если второй раз прогнать, количество сотояний же не увеличится
дело в том что, у меня два минимальных ДКА соединяются
собственно для их получения я использую Алгоритм Бржозовского , который как раз и содержит 2 вызова Subset construction...ммм.... Так ты реши какой алгоритм ты используешь, Бржозовского или "Subset construction". Первый изначально оптимизатор, второй простейший конвертор.
И да, когда ты изначально используешь оптимизатор, то и результат получается оптимизированный :)
...
Рейтинг: 0 / 0
28.09.2016, 22:51
    #39317360
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
White Owlkealon(Ruslan)White Owl,
но если второй раз прогнать, количество сотояний же не увеличится
дело в том что, у меня два минимальных ДКА соединяются
собственно для их получения я использую Алгоритм Бржозовского , который как раз и содержит 2 вызова Subset construction...ммм.... Так ты реши какой алгоритм ты используешь, Бржозовского или "Subset construction". Первый изначально оптимизатор, второй простейший конвертор.
И да, когда ты изначально используешь оптимизатор, то и результат получается оптимизированный :)
видимо не так выражаюсь
Бржозовского я не могу использовать для ловли различных финальных состояний, потому я его только для каждой отдельной строки использую и получаю для каждой лексемы минимальный ДКА. "Subset construction" я применяю для объединения правил в одну итоговую ДКА и по моему предположению результат будет минимальный ДКА (во всяком случае опровержения я пока получить не могу)
...
Рейтинг: 0 / 0
29.09.2016, 18:06
    #39318068
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
kealon(Ruslan)Бржозовского я не могу использовать для ловли различных финальных состоянийммм... мне кажется ты просто не правильно делаешь NFA.

У тебя есть два DFA. Ты кладешь их на один общий лист, добавляешь новое состояние, делаешь из него эпсилон-переходы на стартовые состояния своих DFA. Обозначаешь это новое состояние стартовым. У тебя теперь имеется один цельный NFA с несколькими финальными состояниями.
Добавь теперь еще одно состояние, сделай на него эпсилон-переходы из старых финальных, обозначь это второе новое состояние финальным. И теперь у тебя есть NFA с одним стартом и одним финалом.
Всё. Можешь отдавать его на вход Бржозовскому и получать оптимизированный DFA.
...
Рейтинг: 0 / 0
29.09.2016, 21:35
    #39318172
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
White Owlkealon(Ruslan)Бржозовского я не могу использовать для ловли различных финальных состоянийммм... мне кажется ты просто не правильно делаешь NFA.

У тебя есть два DFA. Ты кладешь их на один общий лист, добавляешь новое состояние, делаешь из него эпсилон-переходы на стартовые состояния своих DFA. Обозначаешь это новое состояние стартовым. У тебя теперь имеется один цельный NFA с несколькими финальными состояниями.
Добавь теперь еще одно состояние, сделай на него эпсилон-переходы из старых финальных, обозначь это второе новое состояние финальным. И теперь у тебя есть NFA с одним стартом и одним финалом.
Всё. Можешь отдавать его на вход Бржозовскому и получать оптимизированный DFA.
и зачем он такой нужен без определения типа результата? "Алгоритм Бржозовского" всё в кучу смешает
...
Рейтинг: 0 / 0
29.09.2016, 22:01
    #39318189
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
kealon(Ruslan)и зачем он такой нужен без определения типа результата?Ну во первых, никаких "типов результата" быть не может. Смотри определение конечных автоматов. Они либо кончаются, либо нет. Для определения "как именно" закончилась работа, надо брать уже как минимум полноценную Машину Тьюринга, которая не только читает входную строку, но и пишет.
А во вторых, с чего вдруг тебе понадобились разные финальные состояния? У тебя ж вроде изначальная задача была оптимизировать регулярное выражение через представление его в виде конечного автомата. Так? А регулярки и отвечают всего-лишь на вопрос "совпадает" или "не совпадает". Нету там нужды во множественных финалах.
...
Рейтинг: 0 / 0
29.09.2016, 22:16
    #39318196
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
White Owl А регулярки и отвечают всего-лишь на вопрос "совпадает" или "не совпадает". Нету там нужды во множественных финалах. лексеру это нужно. не все финалы одинаковы
...
Рейтинг: 0 / 0
29.09.2016, 22:17
    #39318197
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
White Owl, в общем ответ нашёлся на простом примере, к сожалению отрицательный :-(
'ID1', 'a+b'
Код: plaintext
1.
2.
3.
4.
5.
6.
Alphabet:
  #1: 'a'
  #2: 'b'
Table:
 *0:#1-> [1]
  1:#1-> [1]
  1:#2-> [2[0]]


'ID2', 'ab+'
Код: plaintext
1.
2.
3.
4.
5.
6.
Alphabet:
  #1: 'a'
  #2: 'b'
Table:
 *0:#1-> [1]
  1:#2-> [2[0]]
  2:#2-> [2[0]]

совмещение:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
Alphabet:
  #1: 'a'
  #2: 'b'
Table:
 *0:#1-> [1]
  1:#1-> [2]
  1:#2-> [3[ID1, ID2]]
  2:#1-> [2]
  2:#2-> [4[ID1]]
  3:#2-> [5[ID2]]
  5:#2-> [5[ID2]]
3, 5 - одинаковые состояния
...
Рейтинг: 0 / 0
29.09.2016, 22:21
    #39318199
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
хотя нет, вру - разные
...
Рейтинг: 0 / 0
29.09.2016, 22:30
    #39318203
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
kealon(Ruslan)White Owl А регулярки и отвечают всего-лишь на вопрос "совпадает" или "не совпадает". Нету там нужды во множественных финалах. лексеру это нужно. не все финалы одинаковыНо лексер это не конечный автомат.
Лексер это простой перебор начала потока на соответствие нескольким шаблонам. И как только первый подходящий шаблон найден - запуск очередного раунда парсера с найденным токеном. После чего лексер стартует заново.
Лексер по архитектуре это классическая TM с двумя лентами (ну или push-down automata которая в итоге всегда оставляет один элемент на стеке). Но в любом случае к нему нельзя подходить как к D/N конечным автоматам.
...
Рейтинг: 0 / 0
29.09.2016, 22:36
    #39318207
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
White Owlkealon(Ruslan)пропущено...
лексеру это нужно. не все финалы одинаковыНо лексер это не конечный автомат.
Лексер это простой перебор начала потока на соответствие нескольким шаблонам. И как только первый подходящий шаблон найден - запуск очередного раунда парсера с найденным токеном. После чего лексер стартует заново.
Лексер по архитектуре это классическая TM с двумя лентами (ну или push-down automata которая в итоге всегда оставляет один элемент на стеке). Но в любом случае к нему нельзя подходить как к D/N конечным автоматам.
да.... ?
а lex и flex по вашему как работают?
...
Рейтинг: 0 / 0
29.09.2016, 22:53
    #39318215
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
kealon(Ruslan)White Owlпропущено...
Но лексер это не конечный автомат.
Лексер это простой перебор начала потока на соответствие нескольким шаблонам. И как только первый подходящий шаблон найден - запуск очередного раунда парсера с найденным токеном. После чего лексер стартует заново.
Лексер по архитектуре это классическая TM с двумя лентами (ну или push-down automata которая в итоге всегда оставляет один элемент на стеке). Но в любом случае к нему нельзя подходить как к D/N конечным автоматам.
да.... ?
а lex и flex по вашему как работают?А так и работают. Перебирают все известные шаблоны, пока не найдут первый подходящий и потом пишут в выходной поток идентификатор токена, либо сразу запускают парсер.
...
Рейтинг: 0 / 0
29.09.2016, 23:15
    #39318218
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
White OwlПеребирают все известные шаблоны, пока не найдут первый подходящий
это формально, в реальности там один ДКА на все шаблоны
...
Рейтинг: 0 / 0
29.09.2016, 23:49
    #39318225
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
kealon(Ruslan)White OwlПеребирают все известные шаблоны, пока не найдут первый подходящий
это формально, в реальности там один ДКА на все шаблоныТы ошибаешься.
Ты не видишь разницы между Машиной Тьюринга и Детерминированным Конечным Автоматом?
...
Рейтинг: 0 / 0
30.09.2016, 06:58
    #39318282
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
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.
program ab_test;
{$I ab.inc}
  function GetTocken(var Cur: PAnsiChar): integer;
  var
    SS: PAnsiChar;
    tmpID: integer;
    S: integer;
    c: integer;
  begin
    SS := nil;
    // начальное состояние
    S := 0;
    repeat
      repeat
        // Класс символа
        c := LEX_CHAR_CLASSES[Cur^];
        Inc(Cur);
        // Новое состояние
        S := LEX_TABLE[S][c];
      until (S < 0);
      S := not S;
      tmpID := LEX_RESULT[S];
      if tmpID >= 0 then
      begin
        // запоминаем и идём на следующий цикл
        Result := tmpID;
        SS := Cur;
      end
      else
      begin
        // если не было полученных состояний выходим с ошибкой
        if SS = nil then
          Exit(tmpID);
        // возвращаем найденую лексему
        Cur := SS;
        Exit;
      end;
    until False;
  end;
var
  // текст для разбора
  Text: ansistring = 'aaaaababbbbbbaaabbbabbb';
  S, N: PAnsiChar;
  t: integer;
  tStr: string;
begin
  // цикл разбора
  S := PAnsiChar(Text);
  repeat
    N := S;
    t := GetTocken(N);
    case t of
      ID1: Write('ID1: ');
      ID2: Write('ID2: ');
      else
        Write('Unknown:');
    end;
    SetString(tStr, S, UIntPtr(N) - UIntPtr(S));
    Writeln(tStr);
    S := N;
  until (N^ = #0);
end.


типичный вывод программы, аналогичной 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.
// Autogenerate code, don't change
const
  {$DEFINE HAS_ALPHABET}
  CHAR_CLASS_COUNT = 3;
  STATE_COUNT = 6;
// Tockens:
  ID1 = 0;
  ID2 = 1;
  LEX_RESULT: array[0..STATE_COUNT] of Integer = (
    -1, -1, -1, ID1, ID1, ID2, -1
  );
type
  TLexState = array[0..CHAR_CLASS_COUNT-1] of Integer;
const
  LEX_CHAR_CLASSES: array[AnsiChar] of Integer = (
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
  );
  LEX_TABLE: array[0..(STATE_COUNT-1)] of TLexState = (
    (-7, 1, -7),
    (-7, 2, -4),
    (-7, 2, -5),
    (-7, -7, -6),
    (-7, -7, -7),
    (-7, -7, -6)
  );


вывод с программы:
Код: plaintext
1.
2.
3.
4.
5.
ID1: aaaaab
ID2: abbbbbb
ID1: aaab
Unknown:b
Unknown:b
ID2: abbb
...
Рейтинг: 0 / 0
30.09.2016, 10:23
    #39318369
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
White Owl,
это LR(n) лексер, lex работает с LR(1)- там чуток проще
Компиляция. 1: лексер
...
Рейтинг: 0 / 0
03.10.2016, 20:55
    #39319923
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
kealon(Ruslan),

И чё? Что ты пытаешься доказать?
Еще раз спрашиваю: Ты не видишь разницы между Машиной Тьюринга и Детерминированным Конечным Автоматом?
Да, алгоритм Бржозовского к ТМ не применим. Вообще, до сих пор не существует полноценных оптимизаторов для ТМ.

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

А если хочешь смешать несколько слов в один общий автомат, то придется резать свой NFA на сегменты типа "первый сегмент распознает начало лексем от первой по десятую", "второй сегмент А занимается средними сегментами лексем с первой по пятую, а Второй-Б средними сегментами лексем с шестой по девятую". И на каждый из хвостов лексем выделяешь по своему сегменту. Потом каждый из сегментов по отдельности оптимизируешь.
Примерно так, для твоих a+b и ab+:
DFA1: a
DFA2: a*
DFA3: b
DFA4: b*
и отдельная схема переходов между автоматами, по достижению финального "Ок" в каждом.
...
Рейтинг: 0 / 0
04.10.2016, 11:12
    #39320147
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
White Owlkealon(Ruslan),

И чё? Что ты пытаешься доказать?
Еще раз спрашиваю: Ты не видишь разницы между Машиной Тьюринга и Детерминированным Конечным Автоматом?
Да, алгоритм Бржозовского к ТМ не применим. Вообще, до сих пор не существует полноценных оптимизаторов для ТМ.

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

А если хочешь смешать несколько слов в один общий автомат, то придется резать свой NFA на сегменты типа "первый сегмент распознает начало лексем от первой по десятую", "второй сегмент А занимается средними сегментами лексем с первой по пятую, а Второй-Б средними сегментами лексем с шестой по девятую". И на каждый из хвостов лексем выделяешь по своему сегменту. Потом каждый из сегментов по отдельности оптимизируешь.
Примерно так, для твоих a+b и ab+:
DFA1: a
DFA2: a*
DFA3: b
DFA4: b*
и отдельная схема переходов между автоматами, по достижению финального "Ок" в каждом.
при чём тут машина Тьюринга, читайте пост Компиляция. 1: лексер внимательно
часть "Как это работает?"
нету никаких частей отдельных, всё в одном ДКА
...
Рейтинг: 0 / 0
04.10.2016, 17:51
    #39320493
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
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
Почитай любой из них, будет очень полезно.
...
Рейтинг: 0 / 0
04.10.2016, 20:04
    #39320568
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
White OwlНу вообще-то, автор статьи ошибается. Он так же как и ты не видит разницы между разными типами автоматов.
"Работа flex заключается в том, что он строит ДКА по заданному набору регэкспов;" вот это как раз ложь. Оно не ДКА строит, а Машину Тьюринга.
У TM, так же как и у DFA, есть таблица состояний и переходов между состояниями в зависимости от очередного символа во входящем потоке. Но в отличие от DFA, TM может внутри состояния сделать "еще что-то" кроме ожидания следующего символа. Это "еще что-то" чрезвычайно широко, это может быть и вывод символа на выходную ленту, и замена символа во входной ленте, и команда "сдвинуться обратно/вперед по входной ленте". И в том числе это может быть и сигнал "лексема найдена".
Их (TM и DFA) различить очень просто: если находясь в каком-то состоянии мы просто ждем следующего символа на входе, то это DFA, а если внутри состояния что-то происходит - значит это уже TM.

На Хабре бывает много хороших статей, но их далеко не всегда пишут люди с образованием...

автор статьи фактически расшифровывает "книгу дракона" главу 3-ю "Лексический анализ"
Код: plaintext
"Шаблоны в этом языке опредялютя регулярными выражениями, а компилятор LEX генерирует эффективный конечный автомат распознающий их"
(С) А. Ахо, Р. Сети, Д. Ульман - Компиляторы.

Неважно как лексер обрабатывает промежутоные состояния ДКА, сути это не меняет - тем более там только запоминание позиции и результата. Главное, что лексема идентифицируется за один проход по тексту(заглядываение вперёд не считаем - для большинства языков это один символ LR(1)), а не по всем входным регуляркам в отдельности.
Практическое следствие из этого - хоть 2, хоть 1000 регулярок будет обрабатываться на тексте одинакового размера за практически одинаковое время
...
Рейтинг: 0 / 0
04.10.2016, 20:25
    #39320575
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
  
     //Получение следущего состояния ДКА
      while ( (yy_current_state = yy_nxt[yy_current_state][yy_ec[(unsigned char)(*yy_cp)]]) > 0 )
       {
       //проверка результирующего состояния
       if ( yy_accept[yy_current_state] )
           {
           // запоминание последнего результирующего состояния
           yy_last_accepting_state = yy_current_state;
           // запоминание позиции
           yy_last_accepting_cpos = yy_cp;
           }
         // считывание следующего символа
         yy_cp;
       }

   yy_current_state = -yy_current_state;
...
Рейтинг: 0 / 0
05.10.2016, 00:17
    #39320626
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лексический анализ, объединение двух ДКА
kealon(Ruslan)автор статьи фактически расшифровывает "книгу дракона" главу 3-ю "Лексический анализ"
Код: plaintext
"Шаблоны в этом языке опредялютя регулярными выражениями, а компилятор LEX генерирует эффективный конечный автомат распознающий их"
(С) А. Ахо, Р. Сети, Д. Ульман - Компиляторы.мммм... не верю. Не может в Драконей Книге быть такого ляпа. Впрочем, возможно это переводчик наврал. Конкретно, скажи где находится эта фраза, попытаюсь найти ее в оригинале.


kealon(Ruslan)Неважно как лексер обрабатывает промежутоные состояния ДКА, сути это не меняет - тем более там только запоминание позиции и результата.Должен тебя огорчить, но это как раз важно. Ты же хочешь провести оптимизацию состояний и переходов между ними, верно? А это без понимания сути ты сделать не сможешь никак.
И вот для этого тебе и надо понять во первых, что нету такой вещи как "промежуточные состояния ДКА". Ну не важно для ДКА ничего кроме стартового и финального состояний. Просто по сути самого конечного автомата - он стартует и останавливается, но он никогда не прерывается. Не предусмотрено в теории автоматов такой сущности как "промежуточное" состояние для конечного автомата. А как только ты эту сущность введешь, то ты сразу получишь машину тьюринга и мы опять придем к тому от чего начали.

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


kealon(Ruslan)Главное, что лексема идентифицируется за один проход по тексту(заглядываение вперёд не считаем - для большинства языков это один символ LR(1)), а не по всем входным регуляркам в отдельности.
Практическое следствие из этого - хоть 2, хоть 1000 регулярок будет обрабатываться на тексте одинакового размера за практически одинаковое время Да. И? В современных лексерах действительно все шаблоны проверяются одной общей TM. И ей действительно нет большой разницы 2 или 1000 шаблонов.
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Лексический анализ, объединение двух ДКА / 25 сообщений из 29, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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