Análise lexical sem expressões regulares

9

Eu estive observando alguns lexers em vários idiomas de nível superior ( Python , PHP , Javascript entre outros) e todos parecem usar expressões regulares de uma forma ou de outra. Embora eu tenha certeza de que as regexs são provavelmente a melhor maneira de fazer isso, eu queria saber se havia alguma maneira de obter lexing básico sem expressões regulares, talvez algum tipo de análise direta de strings ou algo assim.

Então, sim, é possível implementar algum tipo de lexing básico em uma linguagem de nível superior * sem usar expressões regulares de qualquer forma?

* Linguagens de nível superior, como Perl / PHP / Python / Javascript etc. Tenho certeza de que existe uma maneira de fazê-lo em C

theory regular-expressions lexer mancha
fonte
2
Parece que "existe um livro sobre cálculo que não usa todas aquelas letras gregas e coisas estranhas e onduladas?"
Kevin cline
@kevincline Por que as pessoas remaram através do Atlântico quando há aviões perfeitamente bons no céu?
Smudge
11
Remo e equitação têm diferentes efeitos colaterais.
Kevin Cline

Respostas:

3

Primeiro de tudo, existem bibliotecas de expressões regulares para C desde antes de suas linguagens de "nível superior" serem inventadas. Apenas dizendo, os programas em C não são tão idiotas quanto algumas pessoas parecem pensar.

Para a maioria das gramáticas, lexing é uma questão de procurar espaço em branco e alguns outros caracteres como () [] {}; para dividir as palavras e, em seguida, comparar com uma lista de palavras-chave para ver se há alguma correspondência.

Karl Bielefeldt
fonte
11
Eu não quis dizer que C não poderia fazer regex, queria dizer que ele tem recursos mais poderosos para fazer esse tipo de coisa. Eu imagino que seja mais fácil criar um lexer avançado e de alto desempenho em C do que em uma linguagem de nível superior.
Smudge
11
@ sam, a complexidade e o desempenho de um lexer ou analisador é mais uma função da complexidade do idioma que está sendo analisado do que das línguas em que o analisador é implementado, então não.
jk.
+1. Um lexer é incrivelmente simples; você só precisa de uma sequência, um tipo de dados para seus tokens e uma tabela de palavras-chave predefinidas. A parte mais complicada é lidar com espaços em branco e comentários: P
Mason Wheeler
2

Você pode estar interessado em "analisadores sem scanner", que não possuem uma etapa de tokenização separada. Uma explicação dos benefícios dos analisadores sem scanner é dada no início deste artigo: Filtros de desambiguação para analisadores LR generalizados sem scanner . (Existem também desvantagens.)

(Os PEGs, mencionados em outras respostas, também podem ser usados ​​para criar analisadores sem scanner.)

Ryan Culpepper
fonte
1

Não há nada específico sobre expressões regulares. Eles são simplesmente abreviações, o que permite gerar o código muito mais facilmente, e as implementações são normalmente enviadas. No entanto, fundamentalmente, os lexers são FSMs e expressões regulares são apenas uma maneira de atingir esse objetivo.

DeadMG
fonte
0

Claro que você pode usar outros analisadores, pois todo idioma comum também é livre de contexto. A questão realmente se resume a por que você gostaria.

Não há realmente nada mais simples do que expressões regulares (como você pode melhorar O (N)?) E tentar simplificar não ajuda. Você sempre pode usar o retorno simples, como Jetti apontou, embora eu recomendo evitá-lo, se possível.

Se você usar um analisador mais avançado para lexing, provavelmente não precisará de uma fase de lexing. De fato, as razões pelas quais temos uma fase de lexing são que é mais rápido analisar tokens flexíveis do que analisar caracteres, além de simplificar drasticamente nossa etapa de análise. Portanto, ao usar um analisador mais avançado, você simplesmente perde todos os benefícios do lexing em primeiro lugar.

Pubby
fonte
Então, como o regex faz isso? Ainda não teria que ser caractere por caractere (para a maioria dos padrões usados ​​no lexing, pelo menos)?
10132 Jetti
@ Jetti Sim, é claro.
Pubby
Seria fácil ler cada caractere e, em seguida, voltar atrás, se necessário, para retirar um token. Seria mais código, mas não mais difícil.
10132 Jetti
@ Jetti Não consigo ver como o backtracking ingênuo é melhor.
Pubby
Eu nunca disse melhor. Mas o OP perguntou se existem outras maneiras e é outra que não é um analisador avançado.
10132 Jetti
0

Faz sentido fazer uma análise lexical com expressões regulares ou ignorar essa passagem e fazer uma análise muito mais flexível e poderosa sem lexer com PEG ou GLR.

SK-logic
fonte