¿Usando ANTLR 3.3?

Digamos que desea analizar expresiones simples que consisten en los siguientes tokens:

• - resta (también unaria);
• + adición;
• * multiplicación;
• / división;
• (...) agrupando (sub) expresiones;
• números enteros y decimales.

Una gramática ANTLR podría verse así:

grammar Expression;

options {
  language=CSharp2;
}

parse
  :  exp EOF 
  ;

exp
  :  addExp
  ;

addExp
  :  mulExp (('+' | '-') mulExp)*
  ;

mulExp
  :  unaryExp (('*' | '/') unaryExp)*
  ;

unaryExp
  :  '-' atom 
  |  atom
  ;

atom
  :  Number
  |  '(' exp ')' 
  ;

Number
  :  ('0'..'9')+ ('.' ('0'..'9')+)?
  ;

Ahora para crear un AST propio, agrega output=AST; en tu sección options { ... }, y mezcla un poco de " árbol operadores " en su gramática definiendo qué tokens deben ser la raíz de un árbol. Hay dos maneras de hacer esto:

1. añade ^ y ! después de tus fichas. El ^ hace que el token se convierta en una raíz y el ! excluye el token del ast;
2. usando "reglas de reescritura": ... -> ^(Root Child Child ...).

Tomemos la regla foo por ejemplo:

foo
  :  TokenA TokenB TokenC TokenD
  ;

Y digamos que quieres TokenB convertirse en la raíz y TokenA y TokenC convertirse en sus hijos, y quieres excluir TokenD del árbol. He aquí cómo hacerlo usando la opción 1:

foo
  :  TokenA TokenB^ TokenC TokenD!
  ;

Y aquí está cómo hacerlo usando la opción 2:

foo
  :  TokenA TokenB TokenC TokenD -> ^(TokenB TokenA TokenC)
  ;

Así que, aquí está la gramática con los operadores de árbol en ella:

grammar Expression;

options {
  language=CSharp2;
  output=AST;
}

tokens {
  ROOT;
  UNARY_MIN;
}

@parser::namespace { Demo.Antlr }
@lexer::namespace { Demo.Antlr }

parse
  :  exp EOF -> ^(ROOT exp)
  ;

exp
  :  addExp
  ;

addExp
  :  mulExp (('+' | '-')^ mulExp)*
  ;

mulExp
  :  unaryExp (('*' | '/')^ unaryExp)*
  ;

unaryExp
  :  '-' atom -> ^(UNARY_MIN atom)
  |  atom
  ;

atom
  :  Number
  |  '(' exp ')' -> exp
  ;

Number
  :  ('0'..'9')+ ('.' ('0'..'9')+)?
  ;

Space 
  :  (' ' | '\t' | '\r' | '\n'){Skip();}
  ;

También agregué una regla Space para ignorar cualquier espacio en blanco en el archivo de origen y agregué algunos tokens y espacios de nombres adicionales para el lexer y el analizador sintáctico. Tenga en cuenta que el orden es importante (options { ... } primero, luego tokens { ... } y finalmente las declaraciones @... {}-namespace).

Eso es se.

Ahora genera un lexer y un parser a partir de tu archivo gramatical:

java -cp antlr-3.2.jar org.antlr.Tool Expression.g

Y coloque los archivos .cs en su proyecto junto con las DLL de tiempo de ejecución de C# .

Puedes probarlo usando la siguiente clase:

using System;
using Antlr.Runtime;
using Antlr.Runtime.Tree;
using Antlr.StringTemplate;

namespace Demo.Antlr
{
  class MainClass
  {
    public static void Preorder(ITree Tree, int Depth) 
    {
      if(Tree == null)
      {
        return;
      }

      for (int i = 0; i < Depth; i++)
      {
        Console.Write("  ");
      }

      Console.WriteLine(Tree);

      Preorder(Tree.GetChild(0), Depth + 1);
      Preorder(Tree.GetChild(1), Depth + 1);
    }

    public static void Main (string[] args)
    {
      ANTLRStringStream Input = new ANTLRStringStream("(12.5 + 56 / -7) * 0.5"); 
      ExpressionLexer Lexer = new ExpressionLexer(Input);
      CommonTokenStream Tokens = new CommonTokenStream(Lexer);
      ExpressionParser Parser = new ExpressionParser(Tokens);
      ExpressionParser.parse_return ParseReturn = Parser.parse();
      CommonTree Tree = (CommonTree)ParseReturn.Tree;
      Preorder(Tree, 0);
    }
  }
}

Que produce la siguiente salida:

ROOT
  *
    +
      12.5
      /
        56
        UNARY_MIN
          7
    0.5

Que corresponde a la siguiente AST:

(diagrama creado usando graph.gafol.net)

Tenga en cuenta que ANTLR 3.3 acaba de ser lanzado y el objetivo de CSharp está "en beta". Es por eso que usé ANTLR 3.2 en mi ejemplo.

En el caso de lenguajes bastante simples (como mi ejemplo anterior), también podría evaluar el resultado sobre la marcha sin crear un AST. Puede hacerlo incrustando código C # dentro de su archivo de gramática y dejando que las reglas del analizador devuelvan un valor específico.

Aquí hay un ejemplo:

grammar Expression;

options {
  language=CSharp2;
}

@parser::namespace { Demo.Antlr }
@lexer::namespace { Demo.Antlr }

parse returns [double value]
  :  exp EOF {$value = $exp.value;}
  ;

exp returns [double value]
  :  addExp {$value = $addExp.value;}
  ;

addExp returns [double value]
  :  a=mulExp       {$value = $a.value;}
     ( '+' b=mulExp {$value += $b.value;}
     | '-' b=mulExp {$value -= $b.value;}
     )*
  ;

mulExp returns [double value]
  :  a=unaryExp       {$value = $a.value;}
     ( '*' b=unaryExp {$value *= $b.value;}
     | '/' b=unaryExp {$value /= $b.value;}
     )*
  ;

unaryExp returns [double value]
  :  '-' atom {$value = -1.0 * $atom.value;}
  |  atom     {$value = $atom.value;}
  ;

atom returns [double value]
  :  Number      {$value = Double.Parse($Number.Text, CultureInfo.InvariantCulture);}
  |  '(' exp ')' {$value = $exp.value;}
  ;

Number
  :  ('0'..'9')+ ('.' ('0'..'9')+)?
  ;

Space 
  :  (' ' | '\t' | '\r' | '\n'){Skip();}
  ;

Que puede ser probado con la clase:

using System;
using Antlr.Runtime;
using Antlr.Runtime.Tree;
using Antlr.StringTemplate;

namespace Demo.Antlr
{
  class MainClass
  {
    public static void Main (string[] args)
    {
      string expression = "(12.5 + 56 / -7) * 0.5";
      ANTLRStringStream Input = new ANTLRStringStream(expression);  
      ExpressionLexer Lexer = new ExpressionLexer(Input);
      CommonTokenStream Tokens = new CommonTokenStream(Lexer);
      ExpressionParser Parser = new ExpressionParser(Tokens);
      Console.WriteLine(expression + " = " + Parser.parse());
    }
  }
}

Y produce la siguiente salida:

(12.5 + 56 / -7) * 0.5 = 2.25

EDITAR

En los comentarios, Ralph escribió:

Consejo para aquellos que usan Visual Studio: puede poner algo como java -cp "$(ProjectDir)antlr-3.2.jar" org.antlr.Tool "$(ProjectDir)Expression.g" en los eventos de pre-compilación, luego puede modificar su gramática y ejecutar el proyecto sin tener que preocuparse por reconstruir el lexer/parser.