Author: elleryq

ANTLR是一個用來將剖析語法轉換成語言的工具,如果你接觸過 lex/yacc 的話,就可以很容易瞭解.
這裡有一篇相當簡單的Introduction.
Step by step, 就可以做出一個計算運算式的小程式.
可是,產生出來的程式語言卻是 java, 如果要改用 c# 呢??
依照官方的說明, ANTLR 可以產出三種語言: C++, Java, c#.
所以該怎麼產生呢??需不需要另外寫甚麼??
官方網站同樣也提供了這麼一篇:Notes for using the ANTLR C# Code Generator.
這裡我們以Introduction裡面所提供的範例來作為例子,將他命名為 “expr.g.txt”:

class ExprParser extends Parser;
expr returns [int value=0]
{int x;}
: value=mexpr
( PLUS x=mexpr {value += x;}
| MINUS x=mexpr {value -= x;}
)*
;
mexpr returns [int value=0]
{int x;}
: value=atom ( STAR x=atom {value *= x;} )*
;
atom returns [int value=0]
: i:INT {value=Integer.parseInt(i.getText());}
| LPAREN value=expr RPAREN
;
class ExprLexer extends Lexer;
options {
k=2; // needed for newline junk
charVocabulary=’\u0000′..’\u007F’; // allow ascii
}
LPAREN: ‘(‘ ;
RPAREN: ‘)’ ;
PLUS : ‘+’ ;
MINUS : ‘-‘ ;
STAR : ‘*’ ;
INT : (‘0’..’9′)+ ;
WS : ( ‘ ‘
| ‘\r’ ‘\n’
| ‘\n’
| ‘\t’
)
{$setType(Token.SKIP);}
;

第一步你需要做的,就是在這份例子的最上頭加上

options {
language = “CSharp”;
namespace = “SmallCalc”; // encapsulate code in this namespace
//classHeaderPrefix = “protected”; // use to specify access level for generated class
}

表明我們要使用 c#, 並且 namespace 要命名為 SmallCalc.
接著使用下載到的 antlr, 來進行轉換
>antlr expr.g.txt
他會產出下列檔案:

• ExprLexer.cs
• ExprParser.cs
• ExprParserTokenTypes.cs
• ExprParserTokenTypes.txt

ok, 該有的都有啦,我們接下來需要的是主程式與必要的 antlr assembly(組件).
要取得 antlr assembly, 你必須先取得 antlr 的原始碼 (找 source distribution).
解開原始碼以後,在 lib/csharp/ 下,會有個 visual studio project 檔與 NAnt build 檔.
看你熟悉哪一個,就用哪一個.
總之你會得到 antlr.runtime.dll, 將他複製到剛剛程式所在的位置.
主程式的話,很簡單,就是使用剛剛產生出來的程式來進行剖析:

using System;
using System.IO;
using antlr;
namespace SmallCalc
{
public class Smallcalc {
public static void Main(String[] args)
{
ExprLexer lexer = new ExprLexer( Console.OpenStandardInput() );
ExprParser parser = new ExprParser(lexer);
int x = parser.expr();
Console.WriteLine(x);
}
}
}

然後編譯
>C:\WINDOWS\Microsoft.NET\Framework\v1.1.4322\csc /target:exe /out:smallcalc.exe /r:system.dll /r:antlr.runtime.dll *.cs
你會發現有點小錯誤:

ExprParser.cs(156,11): error CS0246: 找不到型別或命名空間名稱 ‘Integer’ (您是否遺漏 using 指示詞或組件參考?)

稍微調整一下,從原來的

value=Integer.parseInt(i.getText());

修正為

value=Convert.ToInt32( i.getText() );

再重新編譯一次,就大功告成了.
試試看結果囉…

>smallcalc
1+3+5+7*100
709

🙂
參考資料:

• ANTLR Parser Generator
• An Introduction To ANTLR,這是以簡單的運算式為例.
• Notes for using the ANTLR C# Code Generator,如何產生 c# code, 並且編譯.以及一些選項說明.

今天繼續往下面想以後,發現我以前的想法錯誤了.
本想說,根據歷史資料去統計,以出現次數較少的數字取亂數,又,理論上每個數字出現的次數會趨近一致,所以應該會有較高的機率得到下期中獎的號碼.
回頭想想每期中獎號碼組合機率,應該是以 1 去除以 42 取 6 的所有組合數.
我以排列組合去Google找了很多資料:

• 組合
• 排列與組合
• 排列组合
• 排列组合
• 組合數學

要怎麼求組合數呢??我們將樂透的規則套入組合公式:
從 42 個數字中,取 6 個號碼,不論順序,組成一組,不同的組合數為: 排列數/42!
排列組的計算: 42 * (42-1) * (42-2) * (42-3) * (42-4) * (42-5)
42!: 42*41*40*….*2*1
所以寫好以後的程式就是這樣:
using System;
using System.Collections;

public class MyClass
{
    public static double calcP( double totalNumbers, double pickNumbers )
    {
        double possible = 1.0;
        
        for( int i=0; i<pickNumbers; i++ )
            possible = possible * (totalNumbers-i);
            
        return possible;
    }

    public static double calcC( double totalNumbers, double pickNumbers )
    {
        double mShock = 1.0; // m!
        
        for( long i=0; i<pickNumbers; i++ )
            mShock = mShock * (i+1);
        
        double p = calcP( totalNumbers, pickNumbers );
        
        return( p/mShock );
    }

    public static void Main()
    {
        Console.WriteLine( "組合數是: {0}", calcC( 42.0, 6.0 ) );
        
        RL();
    }
    
    #region Helper methods

    private static void RL()
    {
        Console.ReadLine();    
    }
    

    #endregion
}
最後算出來的結果是: 5,245,786
也就是說,如果有 5,245,786 人去買的話,至少會有一人中獎.
不過,還是覺得怪怪的…這數字會不會太小了呢??

之前騎車的時候想到的一個 idea,想要來預測下期樂透的號碼.
以亂數取某數字,理論上,當次數越趨近於無限的時候,每個數字出現的機率會趨近於相等.
所以我們寫了這麼一個程式來驗證其正確性:
using System;
using System.Collections;

public class MyClass
{
    public static void Main()
    {
        Random r = new Random();
        int[] statistics = new int[43];
        int i=0;
        int sum=0;
        
        // initialize
        for( i=0; i<statistics.Length; i++ )
            statistics[i]=0;
            
        for( i=0; i<100000; i++ )
        {
            // int index = Convert.ToInt32( 41*r.NextDouble()+1 );
            int index = r.Next(42)+1;
            statistics[ index ] = statistics[ index ] + 1;
        }
        
        for( i=0; i<statistics.Length; i++ )
        {
            Console.WriteLine( "statistics[{0}] = {1}", i, statistics[i] );
            sum+=statistics[i];
        }
        Console.WriteLine( "sum={0}", sum );
            
        RL();
    }
    
    #region Helper methods
    private static void RL()
    {
        Console.ReadLine();    
    }
    #endregion
}
這邊遇到一件很有趣的事情,如果你用 41*r.NextDouble()+1 來取的話
結果會是最前面數字與最後面數字出現的機率會比其他數字要少了約一倍.
所以這樣取會比較好些: r.Next(42)+1
另外我們捨棄 [0] 不用,純使用 [1] ~ [42], 以方便我們的統計.
參考資料:

• A Lottery Program in C#
• Generating Random Number and String in C#
• Random Numbers in C#
• 亂猜是猜中了，還是沒猜中？

…待續…

CheckSum 是一個很簡單的檢查方法,把內容拆解成一堆 byte (或word,dword), 如果把這些 bytes 相加起來得到的值一致,表示內容”應該”是沒問題.

using System;
using System.IO;
using System.Collections;

public class CheckSum
{
    private long sum=0;
    
    public CheckSum()
    {
    }

    public void Add( int i )
    {
        sum += i;
    }
    
    public void Add( byte b )
    {
        sum += b;
    }
    
    public long GetCheckSum()
    {
        return sum;
    }
}

public class MyClass
{
    public static void Main()
    {
        string filename;
        FileStream fs=null;
        CheckSum sum = new CheckSum();
        
        //Open the stream and read it back.
        Console.Write( "Please input filename:" );
        filename = Console.ReadLine();
        Console.WriteLine( "Trying to read {0}", filename );
        
        if( File.Exists( filename ) )
            Console.WriteLine( "{0} is existed.", filename );

        try
        {
            fs = File.Open( filename, FileMode.Open, FileAccess.Read );
            
            if( fs.CanRead )
            {
                int value=0;
                
                while( (value = fs.ReadByte()) >= 0)
                {
                    sum.Add( value );
                }
                
                Console.WriteLine( "Checksum = {0,8:x}", sum.GetCheckSum() );
            }
            else
                Console.WriteLine( "Cannot be read" );
        }
        catch( Exception ex )
        {
            Console.WriteLine( ex.Message );
        }
        finally
        {
            fs.Close();
        }
        
        RL();
    }
    
    #region Helper methods
    private static void RL()
    {
        Console.ReadLine();    
    }
    #endregion
}