lunes, 8 de septiembre de 2014

¿Como realizar el análisis en Irony?

Este es un ejemplo muy sencillo, pero indispensable al momento de querer utilizar nuestra gramática definida en Irony. Vamos a considerar las siguientes clases para el ejemplo:
  • Gramatica.cs : es donde se encuentran todas las reglas gramaticales definidas en Irony(ver Ejemplo de gramática en Irony.net).
  • Analizador.cs: es una nueva clase que se crea con el objetivo de realizar el análisis.
  • Formulario.cs: clase de la interfaz gráfica en la cual tendremos un área de texto de la clase RichTextBox y un botón de la clase Button.

Crearemos un método en la clase Analizador.cs llamado "Validar_cadena" el cual necesita dos parámetros para su ejecución que son la cadena a analizar y la gramática que se utilizara para dicho análisis. Retornara un valor booleano dependiendo si es valida o no la cadena. El método podría ser de la siguiente forma:

public bool Validar_cadena(string Cadena, Grammar Mi_gramatica) {
            LanguageData lenguaje = new LanguageData(Mi_gramatica);
            Parser parser = new Parser(lenguaje);          
            try
            {
                ParseTree arbol = parser.Parse(Cadena); // el análisis devuelve un árbol abstracto
                return arbol.Root != null; //si el arbol no tiene raíz significa que la cadena no es valida
            }
            catch (Exception e)
            {
                MessageBox.Show(e.ToString()); //por errores de programacion en Gramatica.cs
                return false;
            }
         
        }

Nota: es indispensable agregar la librería de Irony a la clase Analizador.cs

using Irony.Parsing;



Para analizar el texto colocado en el RichTextBox estas serian las acciones en el boton:

private void Boton_analizar(object sender, EventArgs e)
        {                      
            if (AreaDeTexto.Text != null)
            {
                Analizador analizador = new Analizador();//creamos instancia de Analizador
                Gramatica mi_gramatica = new Gramatica();//creamos instancia de Gramática
                if (analizador.Validar_cadena(AreaDeTexto.Text, mi_gramatica))//Ejecución
                {
                    MessageBox.Show("Cadena Correcta");
                }
                else
                {
                    MessageBox.Show("Cadena incorrecta");
                }              
             
            }
        }


domingo, 7 de septiembre de 2014

Usando Herramienta Grammar Explorer

Al descargar Irony la carpeta incluye una herramienta llamada Grammar Explorer la cual puede ser de utlilidad para analizar como funcionan las gramáticas ya que genera un árbol de análisis y un AST y lo muestra en pantalla. Aquí están las instrucciones para utilizarlo:

  • Abrir solución Irony_All.sln en Visual Studio.
  • Hacer click derecho en el proyecto "030.Irony.GrammarExplorer" y seleccionar "Set as StartUp project".
  • Correr el proyecto.
  • !!!Importante:Si se esta corriendo el programa por primera vez y se observa que la lista de gramáticas no está vacía debe limpiarse: para esto hacer click en el botón a la par de el combobox y seleccionar "Remove all"
  • Si el combobox está vacio, hacer click hacer click en el botón y seleccionar "Add grammar". En la ventana emergente navegar a (root)\Irony.Samples\bin\debug folder y seleccionar Irony.Samples.dll. La aplicación mostrará todas las gramáticas dentro del archivo seleccionado.
    Dejar todas llenas y presionar "OK". Las gramáticas agregadas aparecerán en el combobox.
  • Seleccionar un lenguaje/gramática del combobox
  • Los datos de la gramática se encuentran en las diferentes pestañas.
  • Para compilar código de prueba moverse a la pestaña "Test". Hacer click en el botón "Load...".
  • Navegar a <root>\Irony.Samples\SourceSamples y seleccionar el archivo de prueba apropiado para la gramática electa.
  • El código se mostrará en pantalla y para compilarlo basta con presionar el boton "Parse"
  • A la derecha se mostrará el Árbol del parsing.
  • Haciendo click en el botón "Run" también puede visualizarse el AST.
  • Alternativamente puede también pegarse el código propio dentro del área de Código.
  • Repetir para las otras gramáticas en el combobox.

Ejemplo Gramática JSON en Irony .NET

 Otro ejemplo que puede servir para entender el funcionamiento de Irony es esta gramática para lenguaje JSON:
Un ejemplo del lenguaje para poder entender mejor la gramática:

EJEMPLO JSON:

{
    "glossary": {
        "title": "example glossary",
        "GlossDiv": {
            "title": "S",
            "GlossList": {
                "GlossEntry": {
                    "ID": "SGML",
                    "SortAs": "SGML",
                    "GlossTerm": "Standard Generalized Markup Language",
                    "Acronym": "SGML",
                    "Abbrev": "ISO 8879:1986",
                    "GlossDef": {
                        "para": "A meta-markup language, used to create markup languages such as DocBook.",
                        "GlossSeeAlso": ["GML", "XML"]
                    },
                    "GlossSee": "markup"
                }
            }
        }
    }
}



GRAMATICA:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Irony.Parsing;

namespace Irony.Samples.Json {
  [Language("JSON", "1.0", "JSON data format")]
  public class JsonGrammar : Grammar {


//COMO SE HA VISTO EN EL CONSTRUCTOR ES DONDE SE DECLARA LA GRAMÁTICA
    public JsonGrammar() {


      //TERMINALES
      var jstring = new StringLiteral("string", "\""); //cadena de strings encerrados por "
      var jnumber = new NumberLiteral("number"); //numeros
      var comma = ToTerm(",");  //coma
     
      //NO TERMINALES

      var jobject = new NonTerminal("Object");
      var jobjectBr = new NonTerminal("ObjectBr");
      var jarray = new NonTerminal("Array");
      var jarrayBr = new NonTerminal("ArrayBr");
      var jvalue = new NonTerminal("Value");
      var jprop = new NonTerminal("Property");

      //REGLAS
      jvalue.Rule = jstring | jnumber | jobjectBr | jarrayBr | "true" | "false" | "null";
      jobjectBr.Rule = "{" + jobject + "}";
      jobject.Rule = MakeStarRule(jobject, comma, jprop);
      jprop.Rule = jstring + ":" + jvalue;
      jarrayBr.Rule = "[" + jarray + "]";
      jarray.Rule = MakeStarRule(jarray, comma, jvalue);

      //SE COLOCA LA RAÍZ
      this.Root = jvalue;
      MarkPunctuation("{", "}", "[", "]", ":", ",");


      //ESTA DIRECTIVA SE COLOCA PARA QUE ESTOS NO TERMINALES NO APAREZCAN EN EL ARBOL YA QUE SON PARTE DE LA GRAMÁTICA PERO NO SE UTILIZARÁN EN EL ANÁLISIS POSTERIOR DEL ÁRBOL (PARA ESTE EJEMPLO NO SE CREÓ AST)
      this.MarkTransient(jvalue, jarrayBr, jobjectBr);

    }//constructor
  }//class
}//namespace

Definición de algunos Terminales y No-Terminales en Irony .NET

TERMINALES

Para definir un comentario se utiliza CommentTerminal y en el Constructor se envian 3 parametros:

  1. Nombre que se le dará al termino comentario
  2. Símbolo Inicial del Comentario
  3. Símbolo Final del Comentario

//TERMINALES DE COMENTARIO
CommentTerminal COMENTARIO_LINEA = 
new CommentTerminal("COMENTARIO_LINEA", "//", "\n");
CommentTerminal COMENTARIO_LINEAS = 
new CommentTerminal("COMENTARIO_LINEAS", "/*", "*/");

Es importante que se agreguen a la definicion para que no se tomen como terminales:
       
base.NonGrammarTerminals.Add(COMENTARIO_LINEA);
base.NonGrammarTerminals.Add(COMENTARIO_LINEAS);

Hay algunos terminales que hay por defecto en Irony, tales como definir uhn Identificador, un numero o una cadena:


  • Identificador
        IdentifierTerminal ID = new IdentifierTerminal("ID");
  • Numero
        NumberLiteral NUMERO = new NumberLiteral("NUMERO");
  • Cadenas

        StringLiteral CADENA = new StringLiteral("CADENA", "\"");
                   
             Donde el segundo parametro del constructor es el simbolo con el que                empieza y termina la cadena

Ademas se pueden crear algunos terminales personalizados y para ello se utilizan expresiones regulares: Ejemplo:

RegexBasedTerminal palabra 
= new RegexBasedTerminal("palabra", "[a-zA-Z]+");



NO TERMINALES

Los no terminales se definen de la siguiente manera:

 //2. NO TERMINALES
 NonTerminal nonTerminal = new NonTerminal("nonTerminal");

Para definir las producciones en un no Terminal se utilizan las reglas y los terminales y no terminales se concatenan por medio de el signo +:

Ejemplo:


noTerminal.Rule = terminal + nonTerminal2
                  | terminal2 + nonTermial2;

 Hay reglas especiales en Irony que simplifican las reglas:



  • CREACION DE LISTAS
    • Listas sin simbolo de separacion
              palabras.Rule = MakePlusRule(palabras, palabra);
              
              Reconoce:
                           palabra palabra1 palabra2  palabra3


                        Donde el primer parametro es el no terminal que define la lista,                         y el segundo es el elemento de la lista

    • Listas con simbolo de separacion

            l_ids.Rule = this.MakeListRule(l_ids, ToTerm(","), ID);
            
            Reconoce:
                           id, id, id , id

Donde el primer parametro es el no terminal que define la lista, y el segundo es el simbolo separador de la lista y el tercero es el elemento de la lista.

Implementación de AstNodes (Árbol de Sintaxis Abstracta) en Irony .NET

El parser de Irony por defecto genera un árbol de análisis pero es bastante difícil trabajar con este debido a que tiene muchos nodos "de relleno" por lo tanto utilizaremos el Árbol de Sintaxis Abstracta:
En este ejemplo se muestra una forma de implementar los AstNodes en Irony:

El Código Fuente

Esta imagen muestra la funcionalidad que tiene el programa.


Como se observa Realiza la Operacion Aritmetica 4+5*8-20 la diferencia es que en lugar de recorrer el arbol que genera por default irony se utiliza ast nodes de manera que la forma de recorrerlo se hace mas natural con los astnodes

El arbol generado por astnodes para la entrada de la imagen es.
El arbol generado por default por irony para la entrada es
Al observar los 2 arboles se puede ver que con la ayuda de astnodes podemos practicamente eliminar los nodos que no nos sirven y poder colocarlos a nuestra manera para una implementacion mas sencilla y mas eficiente.

En el archivo se hace el comentario de que la instrucción:

this.LanguageFlags = LanguageFlags.CreateAst;

es muy importante ya que es la directiva para crear el Árbol.
Cabe mencionar que se tiene que añadir como referencia los dos dll mencionados en publicaciones anteriores:
1)Irony.dll
2)Irony.Interpreter.dll

Si la descarga no se realiza correctamente Este es el codigo principal de la generacion del arbol ast:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Irony.Parsing;
using Irony.Ast;
using Irony.Interpreter.Ast;
using System.Collections;
/**
 * PROYECTO QUE REALIZA SUMAS RESTAS MULTIPLICACIONES Y DIVICIONES DE NUMEROS IMPLEMENTANDO IRONY
 * */
namespace WindowsFormsApplication1
{
    /**
     * CLASE ARBOL
     * HEREDA DE ASTNODE PARA QUE SE PUEDA IMPLEMENTAR EN LOS NO TERMINALES
     * EL METODO A SOBREESCRIBIR ES INIT QUE SE EJECUTARA AL REDUCIR POR EL NOTERMINAL QUE IMPLEMENTE ESTA CLASE
     * LOS PARAMETROS SERA EL CONTEXTO Y EL PARSETREENODE QUE SE REDUJO
     * */
    public class Arbol : AstNode
    {
        public Object Name;
        public List<Arbol> hijos;
        public override void Init(Irony.Ast.AstContext context, Irony.Parsing.ParseTreeNode treeNode)
        {
            hijos = new List<Arbol>();//inicializamos la lista
            base.Init(context, treeNode);
            switch ((String)treeNode.Term.Name) 
            {           //  0 1 2
                case "E":// E + E | E - E | E * E  | num
                    if (treeNode.ChildNodes.Count > 1) 
                    {
                        Name = treeNode.ChildNodes[1].FindTokenAndGetText(); //SIGNO
                        hijos.Add((Arbol)treeNode.ChildNodes[0].AstNode); // PRIMER VALOR
                        hijos.Add((Arbol)treeNode.ChildNodes[2].AstNode); // SEGUNDO VALOR
                    } else 
                    {
                        Name = treeNode.ChildNodes[0].FindTokenAndGetText(); //OBTENEMOS EL NUMERO
                    }
                    break;
                case "number": 
                    Name =   treeNode.Token.Text;
                    break;
                default:
                    break;
                
            }
        }
    }

    class analizador : Grammar
    {
        //METODO QUE RECORRERA EL ARBOL AST          
        public Double Valor(Arbol arbol)
        {
            Double entero1;
            Double entero2;
            switch ((String)arbol.Name)
            {
                case "+":
                    entero1 = Valor(arbol.hijos[0]);
                    entero2 = Valor(arbol.hijos[1]);
                    return entero1 + entero2;
                case "-":
                    entero1 = Valor(arbol.hijos[0]);
                    entero2 = Valor(arbol.hijos[1]);
                    return entero1 - entero2;
                case "*":
                    entero1 = Valor(arbol.hijos[0]);
                    entero2 = Valor(arbol.hijos[1]);
                    return entero1 * entero2;
                case "/":
                    entero1 = Valor(arbol.hijos[0]);
                    entero2 = Valor(arbol.hijos[1]);
                    return entero1 / entero2;
                default:
                    return Convert.ToDouble(arbol.Name);
            }
        }
     
        public analizador() {
            var number = new RegexBasedTerminal("number", "[0-9]+");
            var singleLineComment = new CommentTerminal("SingleLineComment", "//", "\r", "\n", "\u2085", "\u2028", "\u2029");
            var delimitedComment = new CommentTerminal("DelimitedComment", "/*", "*/");
            var p = new StringLiteral("p", "\"");

            p.AstConfig.NodeType = typeof(Arbol);
            number.AstConfig.NodeType = typeof(Arbol);
            NonTerminal E = new NonTerminal("E",typeof(Arbol));

            E.Rule = E + ToTerm("+") + E
                | E + ToTerm("-") + E
                | E + ToTerm("*") + E
                | E + ToTerm("/") + E
                | number;
            RegisterOperators(1, "+", "-");//ESTABLESEMOS PRESEDENCIA
            RegisterOperators(2, "*", "/");
            
            this.Root = E;
            NonGrammarTerminals.Add(singleLineComment); // QUITAMOS LOS COMENTARIOS DE LA GRAMATICA
            NonGrammarTerminals.Add(delimitedComment);
            LanguageFlags = LanguageFlags.CreateAst;    //IMPORTANTE PARA CREAR EL ARBOL SIN ESTO NO LO CREARA
        }

        public Double Obtener_Resultado(string sourceCode)
        {
            LanguageData language = new LanguageData(this);
            Parser parser = new Parser(language);
            ParseTree parseTree = parser.Parse(sourceCode);
            ParseTreeNode root = parseTree.Root;
            Arbol a = (Arbol)root.AstNode;
            return Valor(a); //OBTENEMOS EL VALRO DE LA ENTRADA
        }
        
    }

}

Estableciendo orden y precedencia de operadores en Irony .NET

Como sabemos, en los lenguajes de programación es necesario que se establezca el orden en el que se opera y se analiza el código.
El ejemplo más común, y tal vez el más acertado para aprender sobre el tema es al utilizar operaciones aritméticas, como en la siguiente gramática (escrita para Irony):

/* Terminales */
         RegexBasedTerminal mas   = new RegexBasedTerminal("suma", "[+]");
         RegexBasedTerminal menos = new RegexBasedTerminal("resta", "[-]");
         RegexBasedTerminal por   = new RegexBasedTerminal("multiplicacion","[*]");
         RegexBasedTerminal div   = new RegexBasedTerminal("division", "[/]");
         RegexBasedTerminal mod   = new RegexBasedTerminal("mod", "[%]");
         RegexBasedTerminal neg   = new RegexBasedTerminal("mod", "[~]");

/* No terminales */
VALOR.Rule
                = VALOR + por + VALOR
                | VALOR + div + VALOR
                | VALOR + mod + VALOR
                | VALOR + exp + VALOR
                | VALOR + mas + VALOR
                | VALOR + menos + VALOR
                | id
                | entero
                | neg + VALOR ;


El problema con esta gramática es que el árbol se puede generar de varias formas para la misma entrada (la gramática tiene ambigüedad) por lo que para la entrada:
1 + 2 * 3 - 4 % ~5

Se puede generar el árbol:


El cual ejecutando realizaría como resultado:
((((1+2) * 3) - 4) % ~5) = 0

Para lo cual escribimos la precedencia de operadores:

/* Precedencia */
            RegisterOperators(1, smas, smenos);
            RegisterOperators(2, spor, sdiv, mod);

            RegisterOperators(3, Associativity.Left, neg);

Lo cual nos generaría un árbol que si da el resultado esperado:

((1 +( 2 * 3)) - (4 % (~5)))

Como es de notar se puede establecer que un signo tenga asociatividad por la izquierda o por la derecha, de la siguiente forma:

            RegisterOperators(3, Associativity.Left, neg);
          RegisterOperators(3, Associativity.Right, neg);

Y de esta forma establecemos prioridades y precedencia en Irony .net...

Ayuda con Identación en Irony .NET

En una Gramática como la de Phyton es muy importante el uso de las identaciones para la agrupación de las instrucciones y es posible analizarlas mediante Irony, aquí presentamos un link a un ejemplo de MiniPython , cabe resaltar la implementación de las identaciones en el ejemplo utilizando el siguiente método sobreescrito:

 public override void CreateTokenFilters(LanguageData language, 
TokenFilterList filters) 
{ 
var outlineFilter = new CodeOutlineFilter(language.GrammarData, 
OutlineOptions.ProduceIndents | OutlineOptions.CheckBraces, ToTerm(@"\")); 
filters.Add(outlineFilter); 
}

Ejemplo de Gramática en Irony .NET


Al contrario que la mayoría de analizadores yacc/lex Irony no emplea generación de código para parser o scanner basado en un meta lenguaje específico.
Irony utiliza la gramática codificada como una clase c# para controlar el proceso de parsing
Aquí mostramos un ejemplo: 
using System;
using System.Collections.Generic;
using System.Text;
using Irony.Parsing;
using Irony.Ast;

namespace Irony.Samples {
  // Esta gramática describe programas que reconocen expresiones
  //simples y asignaciones
  // por Ej:
  // x = 3
  // y = -x + 5

  [Language("ExpressionEvaluator", "1.0", "Multi-line expression evaluator")]

  public class ExpressionEvaluatorGrammar : Irony.Parsing.Grammar {
    public ExpressionEvaluatorGrammar() {

      // 1. Terminales
      var number = new NumberLiteral("number");
      number.DefaultIntTypes = new TypeCode[] { TypeCode.Int32,
TypeCode.Int64, NumberLiteral.TypeCodeBigInt };
      var identifier = new IdentifierTerminal("identifier");
      var comment = new CommentTerminal("comment", "#", "\n", "\r");
      //los comentarios deben agregarse a la lista NonGrammarTerminals;
      //no se utiliza directamente en la gramática,
      // asi que debemos agregarlo para que el Scanner sepa que es
      //un terminal válido.
      base.NonGrammarTerminals.Add(comment);

      // 2. No-terminales
      var Expr = new NonTerminal("Expr");
      var Term = new NonTerminal("Term");
      var BinExpr = new NonTerminal("BinExpr", typeof(BinExprNode));
      var ParExpr = new NonTerminal("ParExpr");
      var UnExpr = new NonTerminal("UnExpr", typeof(UnExprNode));
      var UnOp = new NonTerminal("UnOp");
      var BinOp = new NonTerminal("BinOp", "operator");
      var PostFixExpr = new NonTerminal("PostFixExpr", typeof(UnExprNode));
      var PostFixOp = new NonTerminal("PostFixOp");
      var AssignmentStmt = new NonTerminal("AssignmentStmt", typeof(AssigmentNode));
      var AssignmentOp = new NonTerminal("AssignmentOp", "assignment operator");
      var Statement = new NonTerminal("Statement");
      var ProgramLine = new NonTerminal("ProgramLine");
      var Program = new NonTerminal("Program", typeof(StatementListNode));

      // 3. Reglas en formato BNF
      Expr.Rule = Term | UnExpr | BinExpr | PostFixExpr;
      Term.Rule = number | ParExpr | identifier;
      ParExpr.Rule = "(" + Expr + ")";
      UnExpr.Rule = UnOp + Term;
      UnOp.Rule = ToTerm("+") | "-" | "++" | "--";
      BinExpr.Rule = Expr + BinOp + Expr;
      BinOp.Rule = ToTerm("+") | "-" | "*" | "/" | "**";
      PostFixExpr.Rule = Term + PostFixOp;
      PostFixOp.Rule = ToTerm("++") | "--";
      AssignmentStmt.Rule = identifier + AssignmentOp + Expr;
      AssignmentOp.Rule = ToTerm("=") | "+=" | "-=" | "*=" | "/=";
      Statement.Rule = AssignmentStmt | Expr | Empty;
      ProgramLine.Rule = Statement + NewLine;
      Program.Rule = MakeStarRule(Program, ProgramLine);
      this.Root = Program;       // Se coloca la Raiz

      // 4. Precedencia de Operadores
      RegisterOperators(1, "+", "-");
      RegisterOperators(2, "*", "/");
      RegisterOperators(3, Associativity.Right, "**");

      // 5. Terminos de puntuación
      RegisterPunctuation("(", ")");
      RegisterBracePair("(", ")");
      MarkTransient(Term, Expr, Statement, BinOp, UnOp, PostFixOp,
AssignmentOp, ProgramLine, ParExpr);

      //añade automáticamente un salto de línea antes del EOF para
      //que las reglas funcionen correctamente cuando no haya salto
      //de linea al final del archivo
      this.LanguageFlags = LanguageFlags.CreateAst
| LanguageFlags.NewLineBeforeEOF | LanguageFlags.CanRunSample;
    }
  }
}//namespace