Генератор анализатора flex / lex: минимизация DFA

Выполняет ли flex или lex минимизацию DFA?

Если да, то у меня есть следующие вопросы:

  1. какой алгоритм используется?

  2. скажем, у нас есть спецификация, как показано ниже

%{
#include <stdio.h>
%}

%%
a printf("a\n");
b printf("b\n");
%%

Это соответствует регулярному выражению a|b, и конструкция DFA может привести к DFA с 3 состояниями, которые анализируют это выражение (в формате JSON):

{states: [0, 1, 2],
 moves: [
   {from: 0, char: 'a', to: 1},
   {from: 0, char: 'b', to: 2}
 ],
 start: 0,
 final: [1, 2]
}

Хотя этот DFA работает хорошо и для каждого принимающего состояния он правильно вызывает необходимое действие, алгоритм Хопкрофта для минимизации DFA объединит два принимающих состояния в одно, что приведет к DFA с двумя состояниями. Это может быть проблемой, потому что тогда мы не будем знать, какое действие вызывать в принимающем состоянии. Как с этим справляются flex или lex?


flex-lexer lex
person akonsu    schedule 28.10.2015    source источник

Ответы (1)


arrow_upward
3
arrow_downward

  1. Flex не минимизирует DFA, как и исходный lex. Я не могу говорить обо всех возможных реализациях lex, которые существуют.

  2. Алгоритм Хопкрофта начинается с разделения состояний ровно на два набора: принимающие и не принимающие состояния. Эти множества, очевидно, различны, и остальная часть алгоритма продолжается путем уточнения разделов. Из-за фундаментального свойства алгоритма только один из этих разделов требует повторной проверки.

    В случае лексических спецификаций принимающее состояние также имеет номер действия, в результате чего набор принимающих состояний нельзя считать однородным. Вместо этого начальное разделение должно быть на N+1 подмножества, где N - количество действий лексера. Если нет только одного действия, это не будет двоичным уточнением, поэтому основное свойство не применяется, и все разделы необходимо повторно проверить.

    Кроме того, классический алгоритм Хопкрофта предполагает, что DFA завершен; каждое состояние имеет переход на каждом входе. Это не относится к (f) созданным lex DFA. Существуют модификации алгоритма, которые могут решить эту проблему, или вы можете просто добавить одно состояние приемника к набору состояний (все переходы из которого являются циклическими).

person rici    schedule 28.10.2015
comment
Фактически, (f) DFA, сгенерированные lex, ЯВЛЯЮТСЯ завершенными - любая входная строка будет генерировать какое-либо действие, даже если только действие ECHO по умолчанию для входных данных, которые не соответствуют никакому определенному пользователем шаблону. Кроме того, основной смысл упаковки состояний flex - минимизировать пространство, необходимое для хранения таблиц перехода состояний, а не минимизировать количество состояний. Однако эта упаковка состояний представляет собой настраиваемый алгоритм гибкости, имеющий мало отношения (если таковое имеется) к алгоритму Хопкрофта, поэтому ваши основные положения остаются в силе. - person Chris Dodd; 28.10.2015
comment
@ChrisDodd: это не завершает DFA; это просто означает, что будет принят некоторый префикс каждого ввода. Если сканер гибкости достигает состояния, в котором нет перехода с текущим входным символом, он выполняет резервное копирование до последнего записанного состояния приема. В некотором смысле это делает эффективную машину завершенной, поскольку для каждого ввода существует действие, но в вычисленном DFA отсутствуют переходы. Речь шла не об упаковке состояний, а о минимизации состояний, поэтому я не стал разбираться в упаковке состояний. Алгоритм упаковки не имеет абсолютно никакого отношения к минимизации Хопкрофта. - person rici; 28.10.2015
comment
@ChrisDodd: вопрос об отсутствующем состоянии приемника кажется тривиальным, но он требует модификации алгоритма Хопкрофта, потому что этот алгоритм полагается на возможность разделения полного набора состояний. Это означает, что вы не можете использовать оптимизацию, предполагающую, что начальный раздел является двоичным. Но, как я уже отмечал, вы все равно не можете этого сделать. - person rici; 28.10.2015
comment
Моя точка зрения состоит в том, что flex (и я предполагаю, что другие реализации lex - flex - единственный, с которым я хорошо знаком с внутренними функциями) действительно создает это состояние приемника, поскольку оно необходимо для правильной поддержки обратного отслеживания, чтобы найти правильное совпадение для испускания, даже если ни один пользовательский шаблон не совпадает. Причина, по которой алгоритм Хопкрофта неприменим, заключается в вашем пункте 2 - необходим номер действия (и информация для обратного отслеживания), связанный с конкретным состоянием принятия. - person Chris Dodd; 28.10.2015
comment
@ChrisDodd: Может быть, это семантическая проблема. Afaik, flex использует переходы заедания, чтобы указать, что переход для входящего символа является последним. Целевой объект перехода из целевого состояния технически является номером состояния, но он используется только в качестве индекса в таблице действий, поскольку переходы из целевого состояния никогда не могут быть выполнены. 0 в таблице действий указывает на то, что требуется резервное копирование, а их обычно довольно много. Существует простой процесс, который может превратить это в полноценный DFA, но я не уверен, что это можно сделать во всех случаях, не изобретая новое состояние ... - person rici; 28.10.2015
comment
... В любом случае нет проблем с адаптацией алгоритма Хопкрофта для минимизации состояний; необходимо только создать соответствующую начальную секцию и рабочую очередь уточнения. Я сделал это, начав с таблиц, сгенерированных flex, и это немного уменьшило размер таблицы, но я думаю, что первоначальное суждение о том, что выигрыш не стоит затраченных усилий, вероятно, было верным. Моя реализация действительно изобрела состояние стока, но, возможно, в этом не было необходимости. - person rici; 28.10.2015