OBJETIVOS

• Describir la implementación de un analizador sintáctico descendente recursivo para gramáticas LL(1) expresadas en notación BNF.
• Describir la implementación del analizador sintáctico del lenguaje de programación Tinto.

CÓDIGO A UTILIZAR

El código de esta práctica contiene 9 ficheros de los cuales 7 ficheros corresponden al analizador léxico del lenguaje Tinto descrito en la práctica 3. Los ficheros añadidos corresponden al analizador sintáctico descendente recursivo del lenguaje Tinto y a la clase dedicada a describir excepciones sintácticas.

• Código de la práctica

GRAMÁTICA DE TINTO EN NOTACIÓN EBNF

A continuación se describe la gramática del lenguaje de programación Tinto en formato EBNF.

• CompilationUnit  :  ( ImportClause  )*  TintoDecl

• ImportClause  :  import  identifier  semicolon

• TintoDecl : LibraryDecl  |  NativeDecl

• LibraryDecl  :  library  identifier  lbrace  ( Function )*  rbrace

• NativeDecl  :  native  identifier  lbrace  ( NativeFunction )*  rbrace

• Function  :  Access  FunctionType   identifier   ArgumentDecl  FunctionBody

• NativeFunction  :  Access  FunctionType   identifier   ArgumentDecl  semicolon

• Access :  public  |  private

• FunctionType  :  Type  |  void

• Type : int  | char  | boolean

• ArgumentDecl  :  lparen  ( Argument ( comma  Argument )* )? rparen

• Argument  :  Type  identifier

• FunctionBody  : lbrace ( Statement )* rbrace

• Statement  :  ( Decl | IdStm | IfStm | WhileStm | ReturnStm | NoStm | BlockStm )

• Decl  :  Type  identifier  Assignement  ( comma   identifier   Assignement )*  semicolon

• Assignement  :  ( assign   Expr  )?

• IfStm  :  if   lparen   Expr  rparen   Statement  ( else  Statement )?

• WhileStm  :  while   lparen  Expr   rparen   Statement

• ReturnStm  :  return  (  Expr  )?   semicolon

• NoStm  :  semicolon

• IdStm  :  identifier  ( Assignement | FunctionCall | dot   identifier  FunctionCall )  semicolon

• BlockStm  :  lbrace  ( Statement )*  rbrace

• Expr  :  AndExpr ( or  AndExpr  )*

• AndExpr  :  RelExpr ( and  RelExpr )*

• RelExpr  :  SumExpr  ( RelOp  SumExpr  )?

• RelOp  :  ( eq  | ne  | gt  | ge  | lt  | le  )

• SumExpr  :  UnOp  ProdExpr  ( SumOp   ProdExpr )*

• UnOp  :  ( not | minus | plus )?

• SumOp  :  ( minus | plus )

• ProdExpr  :  Factor  ( MultOp  Factor  )* 

• MultOp  :  ( prod | div | mod )

• Factor  :  ( Literal   | Reference   |  lparen   Expr   rparen )

• Literal  :  ( integer_literal  |  char_literal  |  true   |  false  )

• Reference  :  identifier  ( FunctionCall  |  dot   identifier  FunctionCall )? 

• FunctionCall  :  lparen  (  Expr  ( comma  Expr  )* )?  rparen

GRAMÁTICA DE TINTO EN NOTACIÓN BNF

Al transformar la gramática EBNF de Tinto a una gramática BNF el resultado es el siguiente:

ANALIZADOR SINTÁCTICO DE TINTO

A partir de la gramática LL(1) de Tinto expresada en notación BNF y de los conjuntos de predicción calculados para cada regla de la gramática se puede desarrollar un analizador sintáctico descendente recursivo. La implementación de este analizador se encuentra en la clase TintoParser, cuyo código se muestra a continuación. La clase contiene dos miembros privados: el analizador léxico (lexer), utilizado para obtener el flujo de tokens de entrada, y el token de preanálisis (nextToken), que es el que determina la regla a ejecutar en el análisis descendente. El método principal de la clase se denomina parse() y toma como entrada el fichero a analizar devuelviendo como salida un valor boolean, que indica si el contenido del fichero es correcto. Este método genera una excepción SintaxException al encontrar un error sintáctico, detectando de esta forma los ficheros incorrectos.

La implementación del analizador sintáctico descendente recursivo consiste en generar un método por cada símbolo no terminal de la gramática. El código de estas funciones es similar para todos los símbolos por lo que solo se muestra como ejemplo la función asociada al símbolo CompilationUnit. El reconocimiento de los tokens se representa mediante llamadas al método match(), que verifica que el token de preanálisis corresponde al token esperado y lo consume solicitando al analizador léxico el siguiente token de entrada.

public class TintoParser implements TokenConstants {

  /**
   * Analizador léxico
   */
  private TintoLexer lexer;

  /**
   * Siguiente token de la cadena de entrada
   */
  private Token nextToken;

  /**
   * Método de análisis de un fichero
   * 
   */
  public boolean parse(File file) throws IOException, SintaxException 
  {
    this.lexer = new TintoLexer(file);
    this.nextToken = lexer.getNextToken();
    parseCompilationUnit();
    if(nextToken.getKind() == EOF) return true;
    else return false;
  }

  /**
   * Método que consume un token de la cadena de entrada
   */
  private void match(int kind) throws SintaxException 
  {
    if(nextToken.getKind() == kind) nextToken = lexer.getNextToken();
    else throw new SintaxException(nextToken,kind);
  }

  /**
   * Analiza el símbolo CompilationUnit
   * @throws SintaxException
   */
  private void parseCompilationUnit() throws SintaxException 
  {
    int[] expected = { IMPORT, LIBRARY };
    switch(nextToken.getKind()) 
    {
      case IMPORT:
      case LIBRARY:
        parseImportClauseList();
        parseTintoDecl();
        break;
      default:
        throw new SintaxException(nextToken,expected);
    }
  }
	
  ...
}
            

La clase SintaxException permite representar un error sintáctico. Estos errores se producen cuando el token analizado no corresponde a ninguno de los tokens esperados. Este tipo de excepciones se pueden lanzar en los métodos parse...() cuando el siguente token no pertenence al conjunto de predicción de ninguna de las reglas del símbolo y en el método match() cuando el siguente token no corresponde al token que se desea reconocer. El primer constructor mostrado corresponde a la excepción lanzada por el método match() mientras que el segundo constructor es el que se utiliza en los métodos parse...().

public class SintaxException extends Exception implements TokenConstants {

  /**
   * Mensaje de error
   */
  private String msg;
	
  /**
   * Constructor con un solo tipo esperado
   * @param token
   * @param expected
   */
  public SintaxException(Token token, int expected) 
  {
    this.msg = "Sintax exception at row "+token.getRow();
    msg += ", column "+token.getColumn()+".\n";
    msg += "  Found "+token.getLexeme()+"\n";
    msg += "  while expecting "+getLexemeForKind(expected)+".\n";
  }
	
  /**
   * Constructor con una lista de tipos esperados
   * @param token
   * @param expected
   */
  public SintaxException(Token token, int[] expected) 
  {
    this.msg = "Sintax exception at row "+token.getRow();
    msg += ", column "+token.getColumn()+".\n";
    msg += "  Found "+token.getLexeme()+"\n";
    msg += "  while expecting one of\n";
    for(int i=0; i<expected.length; i++) 
    {
      msg += "    "+getLexemeForKind(expected[i])+"\n";
    }
  }
	
  ...
}
          

Por último, la clase TintoCompiler ha sido modificada para incorporar el análisis sintáctico. La nueva versión busca el fichero "Main.tinto" en el directorio de trabajo y lo analiza sintácticamente. Si el análisis sintáctico resulta correcto se genera un fichero "TintocOutput.txt" con el mensaje "Correcto".  Si se detecta una excepción se genera el fichero "TintocOutput.txt" con el mensaje "Incorrecto" y el fichero "TintocError.txt" con la descripción de la excepción.

public class TintoCompiler {

  /**
   * Punto de entrada de la aplicación
   * @param args
   */
  public static void main(String[] args) 
  {
    // Busca el directorio de trabajo
    String path = (args.length == 0 ? System.getProperty("user.dir") : args[0]);
    File workingdir = new File(path);
		
    try
    {
      File mainfile = new File(workingdir, "Main.tinto");
      TintoParser parser = new TintoParser();
      if(parser.parse(mainfile))
      {
        printOutput(workingdir,"Correcto");
      } 
      else 
      {
        printOutput(workingdir,"Incorrecto");
      }
    } 
    catch(Error err) 
    {
      printError(workingdir, err);
      printOutput(workingdir,"Incorrecto");
    }
    catch(Exception ex) 
    {
      printError(workingdir, ex);
      printOutput(workingdir,"Incorrecto");
    }
  }
	
  ...
}