He estado viendo algunos lexers en varios idiomas de nivel superior ( Python , PHP , Javascript , entre otros) y todos parecen usar expresiones regulares de una forma u otra. Si bien estoy seguro de que las expresiones regulares son probablemente la mejor manera de hacer esto, me preguntaba si había alguna forma de lograr lexing básico sin expresiones regulares, tal vez algún tipo de análisis directo de cadenas o algo así.
Entonces, sí, ¿es posible implementar algún tipo de lexing básico en un lenguaje de nivel superior * sin usar expresiones regulares de ninguna forma?
* Los lenguajes de nivel superior son cosas como Perl / PHP / Python / Javascript, etc. Estoy seguro de que hay una manera de hacerlo en C
theory
regular-expressions
lexer
Mancha
fuente
fuente
Respuestas:
En primer lugar, ha habido bibliotecas de expresiones regulares para C desde antes de que se inventaran los lenguajes de "nivel superior". Solo digo que los programas C no son tan aburridos como algunas personas parecen pensar.
Para la mayoría de las gramáticas, el lexing es una cuestión de buscar espacios en blanco y algunos otros caracteres como () [] {}; para dividir las palabras y luego compararlas con una lista de palabras clave para ver si hay alguna coincidencia.
fuente
Es posible que le interesen los "analizadores sin escáner", que no tienen un paso de tokenización separado. Una explicación de los beneficios de los analizadores sin escáner se da al comienzo de este artículo: Filtros de desambiguación para analizadores LR generalizados sin escáner . (Sin embargo, también hay desventajas).
(Los PEG, que se han mencionado en otras respuestas, también se pueden usar para construir analizadores sin escáner).
fuente
No hay nada específico sobre las expresiones regulares. Son simplemente una forma abreviada que le permite generar el código mucho más fácil, y las implementaciones se envían comúnmente. Sin embargo, fundamentalmente, los lexers son FSM y las expresiones regulares son solo una forma de lograr ese objetivo.
fuente
Por supuesto, puede usar otros analizadores, ya que cada idioma regular también está libre de contexto. La pregunta realmente se reduce a por qué querrías hacerlo.
Realmente no hay nada más simple que las expresiones regulares (¿cómo puedes mejorar O (N)?) E intentar simplificar no ayudará. Siempre puede usar el retroceso simple como lo ha señalado Jetti, aunque recomiendo evitarlo si es posible.
Si va a utilizar un analizador más avanzado para lexing, es probable que no necesite una fase de lexing. De hecho, las razones por las que tenemos una fase lexing es que es más rápido analizar tokens lexed que analizar caracteres, lo que simplifica drásticamente nuestro paso de análisis. Entonces, al usar un analizador más avanzado, simplemente pierde todos los beneficios del lexing en primer lugar.
fuente
Tiene sentido hacer un análisis léxico con expresiones regulares u omitir este paso y hacer un análisis mucho más flexible y potente sin lexer con PEG o GLR.
fuente