Cómo analizar una cadena sin expresiones regulares

Question

Actualmente estoy tratando de crear un componente de software que sea capaz de interpretar cuerdas dinámicas, tales como:

%TO_LOWER%(%DELETE_WHITESPACES%("A SAMPLE TEXT")) 

lo que resultaría en esta cadena:

asampletext 

Me gustaría poder definir un conjunto de funciones disponibles, con parámetros semánticos, etc. Ya sé (más o menos) cómo hacerlo usando expresiones regulares.

Mis preguntas son:

• Es léxico/análisis de expresión regular mucho mejor que para tal fin, o debería ir sólo con expresiones regulares y olvidarse de eso?
• ¿Esa biblioteca ya existe en Java?
• ¿Conoces algún tutorial que muestre algunos algoritmos de análisis/lexing de muestra?

Gracias!

Answer 1

¿Es el lexing/el análisis mucho mejor que la expresión regular para tal fin, o debería simplemente ir con regexp y olvidarse de eso?

Regexes no puede expresar una gramática recursiva, y su sintaxis parece requerir una gramática recursiva. Si este es el caso, entonces las expresiones regulares simplemente no resolverán el problema.

¿Esa biblioteca ya existe en Java?

Esto no es un problema que una biblioteca podría resolver. O necesita utilizar un sistema de generador de analizador (como Antlr o Javacc) para generar el lexer y el analizador, o escribirlo/virtualmente desde cero. El primer enfoque es probablemente mejor ... a menos que hayas tomado un tema de nivel Uni que cubra este campo, o estés preparado para leer en profundidad.

¿Conoce algún tutorial que muestre algunos algoritmos de análisis/lexing de muestra?

Tanto Antlr como Javacc tienen un extenso material tutorial y ejemplos.

Answer 2

Cuando no está vinculado solo a Java, puede usar el analizador PEG de otro idioma o Rebol (tiene un "dialecto" de análisis que es PEG-equivalente) - o alcanzar WAY para Icon o Unicon o ahora incluso Object Icon en code.google.com/p/objecticon

Fue un momento lamentable cuando me di cuenta de que el lenguaje de contenido web MIT Curl (www.curl.com) había optado por la expresión regular para los usuarios a pesar de que Curl tiene macros y ofrece acceso a un AST.

tema general: Grafica de expresión de analizador (PEG) y análisis sintáctico de paquetes en general.

El uso de Perl nos ha legado PCRE, entonces ¿qué podemos hacer sino evitarlo cuando no es necesario (hay antlr y bisonte ...y sin duda también tienen su lugar donde encajan fácilmente)

Nota: Rebol, Icon y Curl son idiomas basados ​​en expresiones (el icono tiene un retroceso limitado).

Otras opciones hacia fuera-a-la forma en que incluyen Oz y Mercurio (este último Erlang puede hacer salir)

No estoy usando pyPEG porque yo estoy confinado a Python 2.6.6; el parse de Python Lepl ya no es compatible, pero se instalará para 2.6

Las opciones de análisis en Python incluyen YAPPS en http://theory.stanford.edu/~amitp/yapps/ y varias otras; Nota: pyparsing no se puede instalar en algunos pitón de env

Y para Scala/Java existe este proyecto PEG: https://github.com/sirthias/parboiled/wiki

Usted puede encontrar un equivalente Java para PEG y la pierna por http://piumarta.com/software/peg/

CiteSeer tiene la Ralph Artículo de Becket sobre el análisis de packrat y Mercury (google para PEG parse mercury site: psu.edu)

También hay una serie de 3 publicaciones de blog en el blog AdventuresInMercury.

Answer 3

Puede intentar usar Scala en la JVM. It makes it very easy to create DSLs.