简单DAG生成算法的一个性质

首先定义语言的语法，尽量定义得简单些：

Bnf代码　　

E ->
    E '+' ID
  | ID
  | '(' E ')'

或者化简掉左递归后以EBNF表示：

Ebnf代码　　

E ->
    ID ( '+' ID )*
  | '(' E ')'

其中ID为单字符的英文字母。

那么可以简单的实现解析器如下：

C#代码　　

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

public enum NodeKind {
  Add,
  Id
}

public abstract class Expression : IEquatable<Expression> {
  // DAG node cache
  static List<Expression> _cache;
  
  // lazily initialize the cache for creating DAG nodes
  protected static List<Expression> Cache {
    get {
      if ( null == _cache ) {
        _cache = new List<Expression>( );
      }
      return _cache;
    }
  }
  
  public virtual NodeKind NodeKind {
    get { throw new NotSupportedException( ); }
  }
  
  // Create a BinaryExpression node representing an add operation
  public static BinaryExpression Add( Expression left, Expression right, bool useCache ) {
    var tempExpr = new BinaryExpression( left, right );
    if ( useCache ) {
      return LookupCache( tempExpr ) as BinaryExpression;
    } else {
      return tempExpr;
    }
  }
  
  // Create an IdExpression representing an ID access
  public static IdExpression Id( char id, bool useCache ) {
    var tempExpr = new IdExpression( id );
    if ( useCache ) {
      return LookupCache( tempExpr ) as IdExpression;
    } else {
      return tempExpr;
    }
  }
  
  static Expression LookupCache( Expression expr ) {
    var cachedExpr = Cache.FirstOrDefault( e => e.Equals( expr ) );
    if ( null == cachedExpr ) {
      Cache.Add( expr );
      cachedExpr = expr;
    }
    return cachedExpr;
  }
  
  #region IEquatable<Expression> members and related methods
  
  public override bool Equals( object other ) {
    if ( !( other is Expression ) ) return false;
    return Equals( other as Expression );
  }
  
  public override int GetHashCode( ) {
    return GetHashCodeCore( );
  }
  
  public abstract bool Equals( Expression other );
  protected abstract int GetHashCodeCore( );

  #endregion
}

public class BinaryExpression : Expression {
  Expression _left;
  Expression _right;
  
  public BinaryExpression( Expression left, Expression right ) {
    _left = left;
    _right = right;
  }
  
  public override NodeKind NodeKind {
    get { return NodeKind.Add; }
  }
  
  public Expression Left {
    get { return _left; }
  }
  
  public Expression Right {
    get { return _right; }
  }
  
  public override bool Equals( Expression other ) {
    if ( ! ( other is BinaryExpression ) ) return false;
    var otherExpr = other as BinaryExpression;
    return otherExpr.Left == _left
      &&  otherExpr.Right == _right;
  }
  
  protected override int GetHashCodeCore( ) {
    return _left.GetHashCode( ) * 37 + _right.GetHashCode( ) + 17;
  }
  
  public override string ToString( ) {
    return string.Format( "(+ {0} {1})", _left.ToString( ), _right.ToString( ) );
  }
}

public class IdExpression : Expression {
  char _id;
  
  public IdExpression( char id ) {
    _id = id;
  }
  
  public override NodeKind NodeKind {
    get { return NodeKind.Id; }
  }
  
  public string IdString {
    get { return _id.ToString( ); }
  }
  
  public override bool Equals( Expression other ) {
    if ( ! ( other is IdExpression ) ) return false;
    return _id == ( other as IdExpression )._id;
  }
  
  protected override int GetHashCodeCore( ) {
    return _id.GetHashCode( );
  }
  
  public override string ToString( ) {
    return IdString;
  }
}

public class SyntaxException : Exception {
  public SyntaxException( ) {
  }
  
  public SyntaxException( string message )
    : base( message ) {
  }
}

public class Scanner : IEnumerable, IEnumerable<int> {
  
  public const int EOS = -1;
  
  string _input;
  
  public Scanner( string input ) {
    _input = input;
  }
  
  public IEnumerator GetEnumerator( ) {
    return ( this as IEnumerable<int> ).GetEnumerator( );
  }
  
  IEnumerator<int> IEnumerable<int>.GetEnumerator( ) {
    return EnumerateChars( ).GetEnumerator( );
  }
  
  static readonly int[ ] _punctuations = new int[ ] {
    '+', '(', ')'
  };
  
  IEnumerable<int> EnumerateChars( ) {
    var reader = new StringReader( _input );
    int intChar;
    while ( 0 < ( intChar = reader.Read( ) ) ) {
      var c = Convert.ToChar( intChar );
      if ( Char.IsWhiteSpace( c ) ) continue;
      if ( _punctuations.Contains( intChar ) || Char.IsLetter( c ) ) {
        yield return intChar;
      } else {
        throw new SyntaxException(
          string.Format( "Invalid character: {0}", c.ToString( ) ) );
      }
    }
    yield return EOS;
  }
}

public class Parser {
  
  Scanner _scanner;
  IEnumerator<int> _input;
  
  public Parser( Scanner scanner ) {
    _scanner = scanner;
  }
  
  public Expression ParseToDag( ) {
    _input = ( _scanner as IEnumerable<int> ).GetEnumerator( );
    return Parse( true );
  }
  
  public Expression ParseToAst( ) {
    _input = ( _scanner as IEnumerable<int> ).GetEnumerator( );
    return Parse( false );
  }
  
  Expression Parse( bool useCache ) {
    _input.MoveNext( );
    var expr = ParseExpression( useCache );
    Match( Scanner.EOS );
    _input = null;
    return expr;
  }
  
  Expression ParseExpression( bool useCache ) {
    Expression expr = null;
    
    // E -> ID | '(' E ')'
    switch ( _input.Current ) {
    case '(':
      Match( '(' );
      expr = ParseExpression( useCache );
      Match( ')' );
      break;
    case Scanner.EOS:
      throw new SyntaxException( "Unexpected end of string" );
    default:
      expr = Expression.Id( Convert.ToChar( _input.Current ), useCache );
      _input.MoveNext( );
      break;
    }
    
    // ( '+' ( ID | '(' E ')' ) )*
    while ( _input.Current == '+' ) {
      Match( '+' );
      Expression right = null;
      switch ( _input.Current ) {
      case '(':
        Match( '(' );
        right = ParseExpression( useCache );
        Match( ')' );
        break;
      case Scanner.EOS:
        throw new SyntaxException( "Unexpected end of string" );
      default:
        right = Expression.Id( Convert.ToChar( _input.Current ), useCache );
        _input.MoveNext( );
        break;
      }
      expr = Expression.Add( expr, right, useCache );
    }
    
    return expr;
  }
  
  void Match( int charCodeToMatch ) {
    if ( _input.Current == charCodeToMatch ) {
      _input.MoveNext( );
    } else {
      throw new SyntaxException(
        string.Format(
          "Expecting {0}, but found {1}",
          CharCodeToString( charCodeToMatch ),
          CharCodeToString( _input.Current ) ) );
    }
  }
  
  string CharCodeToString( int charCode ) {
    return 0 < charCode ? Convert.ToChar( charCode ).ToString( ) : "End-Of-String";
  }
}

class DotGenerator {
  Queue<Expression> _lastRank;
  Queue<Expression> _thisRank;
  TextWriter _writer;
  IEnumerator<string> _nameMaker;
  Dictionary<Expression, string> _nameMap;
  
  public DotGenerator( ) {
    _lastRank = new Queue<Expression>( );
    _thisRank = new Queue<Expression>( );
  }
  
  public string Generate( Expression root ) {
    _lastRank.Enqueue( root );
    _nameMap = new Dictionary<Expression, string>( IdentityComparer<Expression>.Instance );
    _nameMaker = GetNameMaker( ).GetEnumerator( );
    _writer = new StringWriter( );
    _writer.WriteLine( "digraph {" );
    _writer.WriteLine( "  node [fontsize=12, font=Courier, shape=plaintext]" );
    GenerateCore( );
    _writer.WriteLine( "}" );
    var dot = _writer.ToString( );
    
    _nameMap.Clear( );
    _nameMap = null;
    _nameMaker = null;
    _writer = null;
    return dot;
  }
  
  // breadth-first traverse
  void GenerateCore( ) {    
    while ( 0 < _lastRank.Count ) {
      /*if ( 1 < _lastRank.Count ) {
        string[ ] rank = _lastRank.Select( e => _nameMap[ e ] ).ToArray( );
        _writer.WriteLine( "  {0} [ordering=out, style=invis]",
          string.Join( " -> ", rank ) );
        _writer.WriteLine( "  {{rank=same; {0} }}",
          string.Join( " ", rank ) );
      }*/
      
      while ( 0 < _lastRank.Count ) {
        var expr = _lastRank.Dequeue( );
        DeclareNode( expr );
        
        switch ( expr.NodeKind ) {
        case NodeKind.Add:
          var addExpr = expr as BinaryExpression;
          var left = addExpr.Left;
          var right = addExpr.Right;
         
          if ( !_thisRank.Contains( left, IdentityComparer<Expression>.Instance ) ) {
            DeclareNode( addExpr.Left );
            _thisRank.Enqueue( left );
          }
          if ( !_thisRank.Contains( right, IdentityComparer<Expression>.Instance ) ) {
            DeclareNode( addExpr.Right );
            _thisRank.Enqueue( right );
          }
          _writer.WriteLine( "  {0} -> {1}",
            _nameMap[ expr ], _nameMap[ left ] );
          _writer.WriteLine( "  {0} -> {1}",
            _nameMap[ expr ], _nameMap[ right ] );
          
          break;
        case NodeKind.Id:
          // DO NOTHING
          break;
        }
      }
      
      // swap the two queues
      var tempQueue = _lastRank;
      _lastRank = _thisRank;
      _thisRank = tempQueue;
    }
  }
  
  void DeclareNode( Expression expr ) {
    if ( !_nameMap.ContainsKey( expr ) ) {
      _nameMaker.MoveNext( );
      var name = _nameMaker.Current;
      _nameMap.Add( expr, name );
      switch ( expr.NodeKind ) {
      case NodeKind.Add:
        _writer.WriteLine( "  {0} [label="+"]", name );
        break;
      case NodeKind.Id:
        var idExpr = expr as IdExpression;
        _writer.WriteLine( "  {0} [label="{1}"]", name, idExpr.IdString );
        break;
      }
    }
  }
  
  IEnumerable<string> GetNameMaker( ) {
    for ( var count = 0; ; ++count ) {
      yield return string.Format( "node_{0}", count.ToString( ) );
    }
  }
  
  class IdentityComparer<T> : EqualityComparer<T> {
    static IdentityComparer<T> _instance;
    
    static IdentityComparer( ) {
      _instance = new IdentityComparer<T>( );
    }
    
    public static IdentityComparer<T> Instance {
      get { return _instance; }
    }
    
    public override bool Equals( T first, T second ) {
      return object.ReferenceEquals( first, second );
    }
    
    public override int GetHashCode( T obj ) {
      return obj.GetHashCode( );
    }
  }
}

static class Program {
  static void Main( string[ ] args ) {
    string input = null;
    switch ( args.Length ) {
    case 0:
      Console.WriteLine( "Enter an expression on a line:" );
      Console.WriteLine( "(or give the expression as " +
                         "the first argument in command prompt)" );
      input = Console.ReadLine( );
      break;
    default:
      input = args[ 0 ];
      break;
    }
    
    var scanner = new Scanner( input );
    var parser = new Parser( scanner );
    var dotGen = new DotGenerator( );
    
    var ast = parser.ParseToAst( );
    var astDot = dotGen.Generate( ast );
    Console.WriteLine( "// DOT script for AST:" );
    Console.WriteLine( astDot );
    
    var dag = parser.ParseToDag( );
    var dagDot = dotGen.Generate( dag );
    Console.WriteLine( "// DOT script for DAG:" );
    Console.WriteLine( dagDot );
  }
}

	 
	 
	
上一页  1 2 3 4 5 6 7 8  下一页