Existem lexers reais que usam NFAs diretamente em vez de primeiro transformá-los em DFAs?

Estou participando da classe Coursera em compiladores e, na lição sobre lexers, é sugerido que existe uma troca de espaço-tempo entre o uso de autômato finito não determinístico (NFA) e autômato finito determinístico (DFA) para analisar expressões regulares. Se bem entendi, a desvantagem é que um NFA é menor, mas consome mais tempo para atravessar, porque todos os estados possíveis precisam ser considerados ao mesmo tempo e, portanto, na maioria das vezes é transformado em um DFA. Existem lexers que usam NFAs em vez de DFAs na vida "real", ou seja, algum compilador usado na produção e não apenas uma prova de conceito?

Vejo apenas dois aplicativos usando um NFA (ou melhor, seu autômato de energia sem anotá-lo) em vez de um DFA minimizado:

1. Idiomas homoicônicos , onde você pode modificar seu lexer com frequência

2. Sintaxe estranha que pode explodir seu DFA como

   identifier := [a-z][a-z0-9_]*
   indices := [0-9_]{1,256} //up to 256 times
   var := identifier "_" indices | identifier
   

   Se você tomar a última regra como precedência, seu lexer deverá verificar se um identificador contém "_" nos últimos 256 símbolos e reduzi-la neste caso.

Analisadores lexicais compilados compilam o NFA em um DFA.

Boa interpretado matchers de expressão regular, por outro lado, usar o algoritmo de Thompson, simulando a NFA com memoization. Isso é equivalente à compilação do NFA em um DFA, mas você só produz estados do DFA sob demanda, se necessário. Em cada etapa, seu estado determinístico é um conjunto de estados da NFA e, em seguida, dado o próximo caractere de entrada, você faz a transição para um novo conjunto de estados da NFA. Você armazena em cache os estados vistos anteriormente e suas transições de saída em uma tabela de hash. A tabela de hash é liberada se for preenchida, não cresce sem limite.

O motivo para você fazer dessa maneira é que converter o NFA em DFA pode levar um tempo exponencial no tamanho da expressão regular. Isso certamente não é algo que você deseja fazer se estiver avaliando apenas a expressão regular uma vez.

RE2 é um exemplo de um mecanismo de expressão regular que (essencialmente) usa o algoritmo de Thompson. Eu recomendo as brilhantes postagens do blog do autor do RE2, Russ Cox, se você quiser aprender mais (incluindo muitas informações históricas e comparações experimentais de várias abordagens diferentes para a pesquisa de expressões regulares).

Também posso recomendar a cadeia de e-mail " por que o GNU grep é rápido "? A lição 1 é: o caso comum da pesquisa de regex é a pesquisa simples de cadeias de caracteres, caso especial o seu algoritmo.

Eu ficaria surpreso se eles fizessem. A construção do lexer é feita uma vez (espero), o resultado usado milhões de vezes (pense em quantos tokens existem no seu arquivo de origem de tamanho médio). Portanto, a menos que haja circunstâncias muito incomuns, vale a pena tornar o lexer o mais rápido (e outros recursos econômico) possível, ou seja, optar por um DFA mínimo.

No sentido formal estrito, não. O não determinismo no sentido teórico / matemático permite que uma máquina escolha um caminho de computação com base no fato de eventualmente levar a um estado de aceitação ou não, sem olhar mais adiante na entrada . Portanto, nesse sentido estrito, é uma propriedade adequada apenas para o exame teórico, e não existe uma máquina não determinística real, particularmente neste caso, você não pode realmente construir um NFA, a menos que possa ver o futuro, Nesse caso, construir um compilador com esse talento é um desperdício! ;).

No entanto, não determinístico e não determinístico são freqüentemente usados ​​em um sentido mais fraco, definido de maneira obscura. Às vezes, pode significar randomizado / probabilístico - o algoritmo vira uma moeda; em um ambiente formal, isso é estudado como algoritmo probabilístico / randomizado, e não referido como não determinismo. Outro uso é para um algoritmo que não produz necessariamente a mesma saída, com duas execuções na mesma entrada - pode não ser aleatório, mas parte do seu comportamento não é especificado, portanto, pode haver várias saídas válidas (pessoalmente, acho que isso definição vem vem confundindo un -determined e não -deterministic.

No entanto, você poderia, em princípio, construir um lexer que não é determinístico em um desses sentidos informais mais fracos, no entanto, não seria um NFA (esse é um modelo formal de máquina estrito) e não consigo imaginar que seria um acidente idéia quente também - um lexer precisa ser bastante previsível.

A última opção é que você pode simular o não-determinismo por meio de backtracking ou paralelismo, mas nesse caso você perde a aparente eficiência do não-determinismo, ao transformá-lo efetivamente em um cálculo determinístico, para que não seja melhor fora do que com um DFA.