程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 仿查詢分析器的C#計算器——4.語法分析(6)

仿查詢分析器的C#計算器——4.語法分析(6)

編輯:關於C語言

12.堆棧分析:此時列表分析結束,堆棧不為空,需要對堆棧進行處理。經過上面的堆棧分析,遵循高出低入原則,堆棧中的TokenRecord肯 定是棧底優先級最低,棧頂優先級最高。只需要將堆棧中的TokenRecord依次彈棧,然後加入到新棧頂的ChildList中即可。最後彈棧的一個 TokenRecord就是整個樹視圖的根節點,也就是返回值。到此,堆棧為空,也得到了預期的樹視圖,返回根節點TokenRecord即可。

上面是對語法分析整個流程的分析,下面給出具體的代碼。程序中的語法分析放在一個單獨的文件中,SyntaxTreeAnalyse.cs,文件中也只 有一個SyntaxTreeAnalyse類,專門用於語法樹的分析。這個類只有一個入口即一個公開方法SyntaxTreeGetTopTokenAnalyse,傳入 TokenRecord列表,經過分析後返回一個頂級TokenRecord對象,即樹形結構的根節點。具體代碼如下:

    /// <summary>
    /// 語法樹分析
    /// </summary>
    /// <remarks>Author:Alex Leo</remarks>
    internal class SyntaxTreeAnalyse
    {
        /// <summary>
        /// 記號段提取,提取頂級操作記號
        /// </summary>
        /// <param name="IndexStart">起始序號</param>
        /// <param name="IndexEnd">結束序號</param>
        /// <returns>傳入記號段的頂級操作記號記錄對象</returns>
        /// <remarks>Author:Alex Leo</remarks>
        internal static TokenRecord SyntaxTreeGetTopTokenAnalyse(List<TokenRecord> TokenList, int IndexStart, int IndexEnd)
        {
            int intIndexCurrent = IndexStart;//當前處理序號
            int intIndexSubStart = IndexStart;//子記號段的起始序號
            TokenRecord Token;//獲取當前Token
            Stack<TokenRecord> StackCompart = new Stack<TokenRecord>();//括號堆棧
            Stack<TokenRecord> StackOperate = new Stack<TokenRecord>();//操作記號堆棧

            for (int intIndex = IndexStart; intIndex <= IndexEnd; intIndex++)
            {
                Token = TokenList[intIndex];
                intIndexCurrent = intIndex;
                if (Token is TokenLeftBracket)
                {
                    StackCompart.Push(TokenList[intIndexCurrent]);//把左括號壓棧
                    //獲取該括號對中包含的記號段
                    intIndexSubStart = intIndexCurrent + 1;//設置子記號段的起始序號
                    //提取記號段
                    //如果語法錯誤,比如在記號段的末尾沒有配對的右括號記號,則會出錯,這裡假設為語法正確
                    while (StackCompart.Count > 0)
                    {
                        intIndexCurrent += 1;
                        if (intIndexCurrent >= TokenList.Count)
                        {
                            //Error or auto add lossed bracket
                            throw new SyntaxException(Token.Index, Token.Length, "缺少配對的 括號");
                        }

                        if (TokenList[intIndexCurrent] is TokenLeftBracket)
                        {
                            StackCompart.Push(TokenList[intIndexCurrent]);
                        }
                        else if (TokenList[intIndexCurrent] is TokenRightBracket)
                        {
                            StackCompart.Pop();
                        }
                    }

                    TokenRecord TokenInnerTop = SyntaxTreeGetTopTokenAnalyse(TokenList, intIndexSubStart, intIndexCurrent - 1);
                    if (TokenInnerTop != null)//只有在取得括號中的頂級節點才添加
                    {
                        Token.ChildList.Add(TokenInnerTop);
                    }
                    else
                    {
                        //無法獲取括號內的頂級節點
                        throw new SyntaxException(Token.Index, Token.Length, "括號內不包含計算表 達式");
                    }

                    intIndex = intIndexCurrent;//移動序號到當前序號
                    SyntaxTreeStackAnalyse(StackOperate, Token);
                }//if token is TokenLeftBracket
                else if (Token is TokenMethod)//方法處理
                {
                    //檢查方法後是否接著左括號
                    if (intIndexCurrent >= IndexEnd || !(TokenList[intIndexCurrent + 1] is TokenLeftBracket))
                    {
                        throw new SyntaxException(Token.Index, Token.Length, "方法後缺少括號 ");
                    }

                    intIndexSubStart = intIndexCurrent;//設置子記號段的起始序號
                    intIndexCurrent += 1;//指針後移
                    StackCompart.Push(TokenList[intIndexCurrent]);//把左括號壓棧
                    //提取記號段
                    //如果語法錯誤,比如在記號段的末尾沒有配對的右括號記號,則會出錯,這裡假設為語法正確
                    while (StackCompart.Count > 0)
                    {
                        intIndexCurrent += 1;
                        if (intIndexCurrent >= TokenList.Count)
                        {
                            //Error or auto add lossed bracket
                            throw new SyntaxException(Token.Index, Token.Length, "缺少配對的 括號");
                        }
                        if (TokenList[intIndexCurrent] is TokenLeftBracket)
                        {
                            StackCompart.Push(TokenList[intIndexCurrent]);
                        }
                        else if (TokenList[intIndexCurrent] is TokenRightBracket)
                        {
                            StackCompart.Pop();
                        }
                    }

                    if ((intIndexCurrent - intIndexSubStart) == 2)//如果右括號的序號和方法的序號之差是2, 說明中間只有一個左括號
                    {
                        throw new SyntaxException(TokenList[intIndexCurrent - 1].Index, 1, "括號 內不包含計算表達式");
                    }

                    //分析方法記號段,因為方法括號段中可能有多個運算結果,比如if,max等,不能用獲取頂級節 點的方法SyntaxTreeGetTopTokenAnalyse
                    SyntaxTreeMethodAnalyse(TokenList, intIndexSubStart, intIndexCurrent);

                    intIndex = intIndexCurrent;//移動序號到當前序號
                    SyntaxTreeStackAnalyse(StackOperate, Token);
                }//if token is TokenKeyWord
                else if (Token is TokenSymbol || Token is TokenValue)
                {
                    SyntaxTreeStackAnalyse(StackOperate, Token);
                }
                else
                {
                    //不做處理
                    throw new SyntaxException(Token.Index, Token.Length, "運算符位置錯誤");
                }
            }
            return SyntaxTreeStackGetTopToken(StackOperate);//返回頂級記號
        }


        /// <summary>
        /// 方法記號段分析(處於括號中間的代碼段)
        /// </summary>
        /// <param name="ListToken">記號列表</param>
        /// <param name="IndexStart">括號開始的序號</param>
        /// <param name="IndexEnd">括號結束的序號</param>
        /// <remarks>只處理完整的方法段,比如if(), round()</remarks>
        /// <remarks>Author:Alex Leo</remarks>
        private static void SyntaxTreeMethodAnalyse(List<TokenRecord> ListToken, int IndexStart, int IndexEnd)
        {
            int intIndexSubStart = IndexStart;//子記號段的起始序號
            intIndexSubStart = IndexStart + 2;//移動子記號段的開始序號到括號後面
            int intIndexSubEnd = IndexEnd;//子記號段的結束序號
            TokenRecord TokenMethod = ListToken[IndexStart];//方法記號對象
            TokenRecord TokenCurrent;//獲取當前Token
            Stack<TokenRecord> StackCompart = new Stack<TokenRecord>();//分隔符堆棧

            for (int intIndex = IndexStart; intIndex <= IndexEnd; intIndex++)
            {
                TokenCurrent = ListToken[intIndex];
                if (TokenCurrent is TokenLeftBracket)
                {
                    StackCompart.Push(TokenCurrent);
                }
                else if (TokenCurrent is TokenRightBracket)
                {
                    StackCompart.Pop();
                    if (StackCompart.Count == 0)//如果是最後一個右括號
                    {
                        intIndexSubEnd = intIndex - 1;//設置段結束序號
                        TokenMethod.ChildList.Add(SyntaxTreeGetTopTokenAnalyse(ListToken, intIndexSubStart, intIndexSubEnd));//遞歸
                    }
                }
                else if (TokenCurrent is TokenComma)
                {
                    if (StackCompart.Count == 1)//如果是方法的子段
                    {
                        intIndexSubEnd = intIndex - 1;//設置段結束序號
                        TokenMethod.ChildList.Add(SyntaxTreeGetTopTokenAnalyse(ListToken, intIndexSubStart, intIndexSubEnd));//遞歸
                        intIndexSubStart = intIndex + 1;//把子記號段序號後移
                    }
                }
                else
                {
                    //不作處理
                }
            }

            //TokenMethod.GetType().GetMethod("CheckChildCount").Invoke(TokenMethod, new object[] { "運算元素數量不合法" });
        }


        /// <summary>
        /// 語法樹堆棧分析,基於記號的優先級
        /// </summary>
        /// <param name="SyntaxTreeStack">語法樹堆棧</param>
        /// <param name="NewToken">新記號</param>
        /// <remarks>Author:Alex Leo</remarks>
        private static void SyntaxTreeStackAnalyse(Stack<TokenRecord> SyntaxTreeStack, TokenRecord NewToken)
        {
            if (SyntaxTreeStack.Count == 0)//如果語法樹堆棧中不存在記號,則直接壓棧
            {
                SyntaxTreeStack.Push(NewToken);
            }
            else//否則,比較優先級進行棧操作
            {
                //比較優先級,如果新Token優先級高,則壓棧;
                //如果新Token優先級低,則彈棧,把彈出的Token設置為新Token的下級,並把新Token壓棧;
                //相同優先級也彈棧,並將新Token壓棧
                //if (this.m_DicTokenTypePriority[SyntaxTreeStack.Peek().TokenType] < this.m_DicTokenTypePriority[NewToken.TokenType])//低進
                if (SyntaxTreeStack.Peek().Priority < NewToken.Priority)//低進
                {
                    SyntaxTreeStack.Push(NewToken);//低進
                }
                else
                {
                    TokenRecord TempToken = null;
                    //如果堆棧中有記號,並且棧頂的記號優先級大於等於新記號的優先級,則繼續彈棧
                    while (SyntaxTreeStack.Count > 0 && (SyntaxTreeStack.Peek().Priority >= NewToken.Priority))
                    {
                        TempToken = SyntaxTreeStack.Pop();
                        if (SyntaxTreeStack.Count > 0)//檢測棧頂是否可能為空,如果為空則退出
                        {
                            if (SyntaxTreeStack.Peek().Priority >= NewToken.Priority)
                            {
                                SyntaxTreeStack.Peek().ChildList.Add(TempToken);
                            }
                            else
                            {
                                NewToken.ChildList.Add(TempToken);
                            }
                        }
                        else
                        {
                            NewToken.ChildList.Add(TempToken);
                        }
                    }
                    SyntaxTreeStack.Push(NewToken);//壓棧
                }
            }
        }


        /// <summary>
        /// 獲取語法樹堆棧的頂級記號
        /// </summary>
        /// <param name="SyntaxTreeStack">語法樹堆棧</param>
        /// <returns>頂級記號</returns>
        /// <remarks>Author:Alex Leo</remarks>
        private static TokenRecord SyntaxTreeStackGetTopToken(Stack<TokenRecord> SyntaxTreeStack)
        {
            TokenRecord TempToken = null;
            if (SyntaxTreeStack.Count > 0)
            {
                TempToken = SyntaxTreeStack.Pop();
                while (SyntaxTreeStack.Count > 0)
                {
                    SyntaxTreeStack.Peek().ChildList.Add(TempToken);
                    TempToken = SyntaxTreeStack.Pop();
                }
            }
            return TempToken;
        }
    }//class SyntaxTreeAnalyse

代碼中對括號進行了特殊處理,遇到左括號之後需要查找到配對的右括號,然後對這一段調用SyntaxTreeGetTopTokenAnalyse進行遞歸處理 ,找出括號中的頂級節點。而對於方法也需要特殊處理,方法必須帶括號,而且括號中不止一個根節點。處理過程是以逗號為分隔符,依次找 出括號中的幾個節點,然後添加到方法的ChildList中。實際的代碼在SyntaxTreeMethodAnalyse方法中實現。

這一篇寫的我自己都頭暈了,呵呵,堆棧一個個分析,截圖都挺煩。代碼裡方法互相遞歸調用,也是比較讓人容易頭暈的,希望有人能看懂 吧。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved