藍色情懷

《編譯原理》有限自動機的 C 程式語言範例

//程式功能：
//利用狀態表和有限自動機的運行原理，識別一個輸入串是否為一個有效的無符號定點實數。
//
//例：
//輸入：1#
//輸出：接受
//輸入：3.14#
//輸出：接受
//輸入：3ab#
//輸出：不接受
//輸入：1.2.3
//輸出：不接受
//
//輸入資料要求：不能有空格，以'#'結束（在本程式可以不用'#'結束）。
//輸出：如果是無符號定點實數，顯示「接受」；否則顯示「不接受」。
//
//註：通過改變狀態表和Run()函數，可以改變程式的功能。
// 如可將狀態表改變成識別「偶數」的有限自動機的狀態表
// 將狀態表改變成識別「無符號實數」的有限自動機的狀態表
/////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <string.h>

//狀態表相關存儲資訊：
#define STATE_NUMBER 4 //狀態數目
#define CHAR_NUMBER 2 //輸入字元的種類: d 和 .
#define DIGIT 0 //輸入數位在狀態表中位於第0列
#define DOT 1 //小數點位於狀態表的第1列
//State[][]為狀態表，以整數組形式存放，0,1,2,3表示狀態，-1表示沒有此狀態
int State[STATE_NUMBER][CHAR_NUMBER]
    = {{1,-1},
    {1,2},
    {3,-1},
    {3,-1}};
int Q[STATE_NUMBER] = {0,1,0,1}; //終態標誌：0非終態，1終態。

//緩衝區：
//輸入緩衝區：由專門函數操作（ReadALine(),GetChar()）
#define BUFFER_SIZE 1000 //運算式緩衝區大小
char Buffer[BUFFER_SIZE]; //運算式緩衝區，以''表示結束
int ipBuffer = 0; //運算式緩衝區當前位置序號
char ch; //存放取得的一個字元

//函數宣告：
bool Run(); //對存儲在緩衝區的一行字串（以'#'結束）進行運行
void Init(); //全局初始化
bool ReadALine(); //從鍵盤讀一行（沒有空格），存於運算式緩衝區Buffer[]中
char GetChar(); //從緩衝區取一個字元，返回該字元的同時將它存於總體變數ch中


//主程序：
void main()
{
    Init();
    while(ReadALine()) //讀一行成功，對它進行判斷
    {
        if(Run()) //對該行進行運行，看是否能被接受？
            printf("接受nn");
        else
            printf("不接受nn");
        }
    }

//對存儲在緩衝區的一行字串（以'#'結束）進行運行
//返回：如果是無符號定點實數，返回true；否則返回：false
bool Run()
{
    int S=0; //S存放運行時的當前狀態，目前為初態
    while(GetChar()!='#')
    {
        if(ch >= '0' && ch <= '9') //數字
            S = State[S][DIGIT]; //將狀態轉換成輸入數位後的狀態
        else if(ch == '.') //小數點
            S = State[S][DOT]; //將狀態轉換成輸入小數點後的狀態
        else //其他都為非法字元
            return false;
        if(S == -1) //處於非法狀態
            return false;
    }
    //運行結束，判斷S是否為終態
    if(Q[S] == 1) //終態
        return true;
    else //非終態
        return false;
}

//全局初始化
void Init()
{
    //好像無需初始化
    printf("程式功能：輸入一個字串，判斷它是否是無符號定點實數。n");
    printf("======================================================nn");
}

//從鍵盤讀一行（沒有空格），存於運算式緩衝區Buffer[]中，以'#'結束，並置ipBuffer=0；
//讀到非空字串：返回 true；讀到單獨的「#」：返回 false
bool ReadALine()
{
    int l;
    printf("請輸入以"#"號結束的無空格字串：");
    scanf("%s",Buffer);
    l = strlen(Buffer); //讀入的字串的長度
    if(l == 0) return ReadALine(); //輸入了空字串，重新輸入
    if(Buffer[0] == '#') return false; //輸入單獨的'#'表示不再輸入
    Buffer[l] = '#'; //最後一個字元用結束標記'#'代替（本來是''）
    ipBuffer = 0; //初始化緩衝區指標
    return true;
}

//從緩衝區取一個字元，返回該字元的同時將它存於總體變數ch中
//成功：返回字元；不成功：返回'#'
char GetChar()
{
    if((ch = Buffer[ipBuffer]) != '#')
        ipBuffer ++;
    return ch;
}