java - regulares - Haciendo un analizador léxico
construir un analizador lexico (6)
CookCC ( https://github.com/coconut2015/cookcc ) genera un lexer muy rápido, pequeño y sin dependencia para Java.
Estoy trabajando con un programa Lexical Analyzer ahora mismo y estoy usando Java. He estado buscando respuestas sobre este problema, pero hasta ahora no he podido encontrar ninguna. Aquí está mi problema:
Entrada:
System.out.println ("Hello World");
Salida deseada:
Lexeme----------------------Token
System [Key_Word]
. [Object_Accessor]
out [Key_Word]
. [Object_Accessor]
println [Key_Word]
( [left_Parenthesis]
"Hello World" [String_Literal]
) [right_Parenthesis]
; [statement_separator]
Todavía soy un principiante, así que espero que ustedes puedan ayudarme en esto. Gracias.
El análisis léxico es un tema en sí mismo que generalmente se combina con el diseño y análisis del compilador. Deberías leer sobre esto antes de intentar codificar algo. Mi libro favorito sobre este tema es el libro del Dragón , que debería proporcionarle una buena introducción al diseño del compilador e incluso proporciona pseudocódigos para todas las fases del compilador que puede traducir fácilmente a Java y pasar de allí.
En resumen, la idea principal es analizar la entrada y dividirla en tokens que pertenecen a ciertas clases (paréntesis o palabras clave, por ejemplo, en la salida deseada) utilizando una máquina de estados finitos. El proceso de construcción de máquinas de estado es en realidad la única parte difícil de este análisis y el libro del Dragón le proporcionará una gran visión de esto.
Escriba un programa para hacer un analizador léxico simple que construirá una tabla de símbolos a partir de un flujo dado de caracteres. Deberá leer un archivo llamado "input.txt" para recopilar todos los caracteres. Para simplificar, el archivo de entrada será un programa C / Java / Python sin encabezados ni métodos (cuerpo del programa principal). Luego identificará todos los valores numéricos, identificadores, palabras clave, operadores matemáticos, operadores lógicos y otros [distintos]. Vea el ejemplo para más detalles. Puede suponer que habrá un espacio después de cada palabra clave.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(){
/* By Ashik Rabbani
Daffodil International University,CSE43 */
keyword_check();
identifier_check();
math_operator_check();
logical_operator_check();
numerical_check();
others_check();
return 0;
}
void math_operator_check()
{
char ch, string_input[15], operators[] = "+-*/%";
FILE *fp;
char tr[20];
int i,j=0;
fp = fopen("input.txt","r");
if(fp == NULL){
printf("error while opening the file/n");
exit(0);
}
printf("/nMath Operators : ");
while((ch = fgetc(fp)) != EOF){
for(i = 0; i < 6; ++i){
if(ch == operators[i])
printf("%c ", ch);
}
}
printf("/n");
fclose(fp);
}
void logical_operator_check()
{
char ch, string_input[15], operators[] = "&&||<>";
FILE *fp;
char tr[20];
int i,j=0;
fp = fopen("input.txt","r");
if(fp == NULL){
printf("error while opening the file/n");
exit(0);
}
printf("/nLogical Operators : ");
while((ch = fgetc(fp)) != EOF){
for(i = 0; i < 6; ++i){
if(ch == operators[i])
printf("%c ", ch);
}
}
printf("/n");
fclose(fp);
}
void numerical_check()
{
char ch, string_input[15], operators[] ={''0'',''1'',''2'',''3'',''4'',''5'',''6'',''7'',''8'',''9''};
FILE *fp;
int i,j=0;
fp = fopen("input.txt","r");
if(fp == NULL){
printf("error while opening the file/n");
exit(0);
}
printf("/nNumerical Values : ");
while((ch = fgetc(fp)) != EOF){
for(i = 0; i < 6; ++i){
if(ch == operators[i])
printf("%c ", ch);
}
}
printf("/n");
fclose(fp);
}
void others_check()
{
char ch, string_input[15], symbols[] = "(){}[]";
FILE *fp;
char tr[20];
int i,j=0;
fp = fopen("input.txt","r");
if(fp == NULL){
printf("error while opening the file/n");
exit(0);
}
printf("/nOthers : ");
while((ch = fgetc(fp)) != EOF){
for(i = 0; i < 6; ++i){
if(ch == symbols[i])
printf("%c ", ch);
}
}
printf("/n");
fclose(fp);
}
void identifier_check()
{
char ch, string_input[15];
FILE *fp;
char operators[] ={''0'',''1'',''2'',''3'',''4'',''5'',''6'',''7'',''8'',''9''};
int i,j=0;
fp = fopen("input.txt","r");
if(fp == NULL){
printf("error while opening the file/n");
exit(0);
}
printf("/nIdentifiers : ");
while((ch = fgetc(fp)) != EOF){
if(isalnum(ch)){
string_input[j++] = ch;
}
else if((ch == '' '' || ch == ''/n'') && (j != 0)){
string_input[j] = ''/0'';
j = 0;
if(isKeyword(string_input) == 1)
{
}
else
printf("%s ", string_input);
}
}
printf("/n");
fclose(fp);
}
int isKeyword(char string_input[]){
char keywords[32][10] = {"auto","break","case","char","const","continue","default",
"do","double","else","enum","extern","float","for","goto",
"if","int","long","register","return","short","signed",
"sizeof","static","struct","switch","typedef","union",
"unsigned","void","volatile","while"};
int i, flag = 0;
for(i = 0; i < 32; ++i){
if(strcmp(keywords[i], string_input) == 0){
flag = 1;
break;
}
}
return flag;
}
void keyword_check()
{
char ch, string_input[15], operators[] = "+-*/%=";
FILE *fp;
char tr[20];
int i,j=0;
printf(" Token Identification using C /n By Ashik-E-Rabbani /n 161-15-7093/n/n");
fp = fopen("input.txt","r");
if(fp == NULL){
printf("error while opening the file/n");
exit(0);
}
printf("/nKeywords : ");
while((ch = fgetc(fp)) != EOF){
if(isalnum(ch)){
string_input[j++] = ch;
}
else if((ch == '' '' || ch == ''/n'') && (j != 0)){
string_input[j] = ''/0'';
j = 0;
if(isKeyword(string_input) == 1)
printf("%s ", string_input);
}
}
printf("/n");
fclose(fp);
}
No necesita ANTLR ni el libro del Dragón para escribir un simple analizador léxico a mano. Incluso los analizadores léxicos para lenguajes más completos (como Java) no son terriblemente complicados de escribir a mano. Obviamente, si tiene una tarea industrial, es posible que desee considerar herramientas de fuerza industrial como ANTLR o alguna variante lex, pero para aprender cómo funciona el análisis léxico, escribir una a mano probablemente resultaría ser un ejercicio útil. Supongo que este es el caso, ya que dijiste que aún eres un principiante.
Aquí hay un simple analizador léxico, escrito en Java, para un subconjunto de un lenguaje de tipo Esquema, que escribí después de ver esta pregunta. Creo que el código es relativamente fácil de entender, incluso si nunca antes has visto un lexer, simplemente porque dividir una secuencia de caracteres (en este caso una String ) en una secuencia de tokens (en este caso una List<Token> ) no está no es tan dificil Si tienes preguntas puedo tratar de explicar con más profundidad.
import java.util.List;
import java.util.ArrayList;
/*
* Lexical analyzer for Scheme-like minilanguage:
* (define (foo x) (bar (baz x)))
*/
public class Lexer {
public static enum Type {
// This Scheme-like language has three token types:
// open parens, close parens, and an "atom" type
LPAREN, RPAREN, ATOM;
}
public static class Token {
public final Type t;
public final String c; // contents mainly for atom tokens
// could have column and line number fields too, for reporting errors later
public Token(Type t, String c) {
this.t = t;
this.c = c;
}
public String toString() {
if(t == Type.ATOM) {
return "ATOM<" + c + ">";
}
return t.toString();
}
}
/*
* Given a String, and an index, get the atom starting at that index
*/
public static String getAtom(String s, int i) {
int j = i;
for( ; j < s.length(); ) {
if(Character.isLetter(s.charAt(j))) {
j++;
} else {
return s.substring(i, j);
}
}
return s.substring(i, j);
}
public static List<Token> lex(String input) {
List<Token> result = new ArrayList<Token>();
for(int i = 0; i < input.length(); ) {
switch(input.charAt(i)) {
case ''('':
result.add(new Token(Type.LPAREN, "("));
i++;
break;
case '')'':
result.add(new Token(Type.RPAREN, ")"));
i++;
break;
default:
if(Character.isWhitespace(input.charAt(i))) {
i++;
} else {
String atom = getAtom(input, i);
i += atom.length();
result.add(new Token(Type.ATOM, atom));
}
break;
}
}
return result;
}
public static void main(String[] args) {
if(args.length < 1) {
System.out.println("Usage: java Lexer /"((some Scheme) (code to) lex)/".");
return;
}
List<Token> tokens = lex(args[0]);
for(Token t : tokens) {
System.out.println(t);
}
}
}
Ejemplo de uso:
~/code/scratch $ java Lexer ""
~/code/scratch $ java Lexer "("
LPAREN
~/code/scratch $ java Lexer "()"
LPAREN
RPAREN
~/code/scratch $ java Lexer "(foo)"
LPAREN
ATOM<foo>
RPAREN
~/code/scratch $ java Lexer "(foo bar)"
LPAREN
ATOM<foo>
ATOM<bar>
RPAREN
~/code/scratch $ java Lexer "(foo (bar))"
LPAREN
ATOM<foo>
LPAREN
ATOM<bar>
RPAREN
RPAREN
Una vez que hayas escrito uno o dos lexers simples como este, obtendrás una buena idea de cómo se descompone este problema. Entonces sería interesante explorar cómo usar herramientas automatizadas como lex. La teoría detrás de los emparejadores basados en expresiones regulares no es demasiado difícil, pero lleva un tiempo comprenderla completamente. Creo que escribir lexers a mano motiva ese estudio y te ayuda a enfrentar el problema mejor que sumergirte en la teoría detrás de convertir expresiones regulares en automatización finita (primero NFA, luego NFA a DFA), etc. ser mucho para tomar a la vez, y es fácil sentirse abrumado.
Personalmente, si bien el libro del Dragón es bueno y muy completo, la cobertura podría no ser la más fácil de entender porque pretende ser completa, no necesariamente accesible. Es posible que desee probar otros textos de compilador antes de abrir el libro del Dragón. Aquí hay algunos libros gratuitos, que tienen una buena cobertura introductoria, IMHO:
http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf
http://www.diku.dk/~torbenm/Basics/
Algunos artículos sobre la implementación de expresiones regulares (el análisis léxico automatizado usualmente usa expresiones regulares)
Espero que eso ayude. Buena suerte.
Puede usar bibliotecas como Lex & Bison en C o Antlr en Java. El análisis léxico se puede hacer haciendo autómatas. Te voy a dar un pequeño ejemplo:
Supongamos que necesita tokenizar una cadena donde las palabras clave (idioma) son {''echo'', ''.'', '' '', ''end'') . Por palabras clave quiero decir que el lenguaje consiste en seguir solo palabras clave. Así que si yo escribo
echo .
end .
Mi lexer debería salir
echo ECHO
SPACE
. DOT
end END
SPACE
. DOT
Ahora, para construir autómatas para un tokenizador de este tipo, puedo comenzar por
->(SPACE) (Back)
|
(S)-------------E->C->H->O->(ECHO) (Back)
| |
.->(DOT)(Back) ->N->D ->(END) (Back to Start)
El diagrama anterior es bastante malo, pero la idea es que tienes un estado de inicio representado por S ahora consumes E y pasas a otro estado, ahora esperas que N o C vengan para END y ECHO respectivamente. Sigues consumiendo caracteres y alcanzando diferentes estados dentro de esta simple máquina de estados finitos. Finalmente, alcanza cierto estado de Emit , por ejemplo, después de consumir E , N , D , alcanza el estado de emisión para END que emite el token out y luego vuelve al estado de start . Este ciclo continúa para siempre en la medida en que el flujo de caracteres llegue a su tokenizer. En un carácter no válido, puede lanzar un error o ignorarlo según el diseño.
ANTLR 4 hará exactamente esto con la gramática de referencia Java.g4 . Tiene dos opciones dependiendo de qué tan cerca desea que el manejo de las secuencias de escape de Unicode siga la especificación del idioma.
- https://github.com/antlr/grammars-v4/blob/master/java/Java.g4 : esta gramática solo maneja las secuencias de escape de Unicode como caracteres dentro de una cadena o literal de caracteres.
- https://github.com/antlr/antlr4/blob/master/tool/test/org/antlr/v4/test/Java-LR.g4 (debe cambiar su nombre a Java.g4 antes de usarlo): esta gramática requiere que
ANTLRInputStreamsuANTLRInputStreamen unJavaUnicodeInputStream, que procesa las secuencias de escape de Unicode de acuerdo con el JLS antes de enviarlas al lexer.
Edición: los nombres de los tokens producidos por esta gramática difieren ligeramente de su tabla.
- Su token
Key_WordesIdentifier - Su token de
Object_AccessoresDOT - Su
left_ParenthesisLPARENesLPAREN - Su token
StringLiteralesStringLiteral - Tu token de
RPARENesRPAREN - Su token de
statement_separatoresSEMI