【目的】 設計一個算符優先分析器，理解優先分析方法的原理。

【要求】 使用算符優先分析算法分析下面的文法：

E’ → #E#

E → E+T | T

T → T*F | F

F → P^F | P

P → (E) | i

其中i可以看作是一個終結符，無需作詞法分析。具體要求如下：

1. 如果輸入符號串為正確句子，顯示分析步驟，包括分析棧中的內容、優先關系、輸入符號串的變化情況；

2. 如果輸入符號串不是正確句子，則指示出錯位置。

【方法】 首先構造算符優先關系表，然后根據算符優先分析算法編寫程序。

【實驗環境和工具】 本實驗使用的是C#。

說明：本程序輸入的目標字符串要以#開頭和結尾。

本程序的運行環境是visual studio 2005.net,選擇的是控制臺應用程序。


源程序代碼：

/////文件【program.cs】


using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            //顯示產生式的內容
            Console.WriteLine("產生式為：=====================================================");
            Class1 cs1 = new Class1();
            cs1.generate = new Generate[9];
            cs1.InitGenerate(cs1.generate);
            cs1.Display(cs1.generate);
            Console.WriteLine("");
            Console.WriteLine();
            cs1.DispTable();

            //開始分析句子
            Console.WriteLine();
            Console.WriteLine("===============================================================");
            Console.WriteLine("請輸入目標句子(以＃開頭和結尾)：");
            Class1.strWhole = Console.ReadLine();
          
             cs1.process();
         
            Console.ReadLine();
        }
    }
}

/////[文件class1.cs]
using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1
{
    public struct Generate //用結構體存儲產生式
    {
        public char left;//左部
        public string right;//右部

    }
    class Class1
    {
       public  static string strWhole = "";//句子字符串
        static char tempChar = ' ';//當前字符
        static int p = 1;//剩余字符串的當前位置
        static int top = 1;//棧頂
        static int j = 1;
        static char[] stack = new char[30];
        public Generate[] generate;
        char[] VT;//存儲非終結符的數組
        static char[] VN = new char[] { 'S', 'E', 'E', 'T', 'T', 'F', 'F', 'P', 'P' };
        static char[,] priority = new char[7, 7];//存儲算符優先關系的數組
        public Class1()
        {
            stack[0] = ' ';
            stack[1] = '#';
            this.VT = new char[7] { '+', '*', '^', '(', ')', 'i', '#' };

        }
        //先初始化產生式并存入數組
        public void InitGenerate(Generate[] generate)
        {
            generate[0].left = 'S';
            generate[0].right = "#E#";
            generate[1].left = 'E';
            generate[1].right = "E+T";
            generate[2].left = 'E';
            generate[2].right = "T";
            generate[3].left = 'T';
            generate[3].right = "T*F";
            generate[4].left = 'T';
            generate[4].right = "F";
            generate[5].left = 'F';
            generate[5].right = "P^F";
            generate[6].left = 'F';
            generate[6].right = "P";
            generate[7].left = 'P';
            generate[7].right = "(E)";
            generate[8].left = 'P';
            generate[8].right = "i";
        }
        //將產生式進行顯示
        public void Display(Generate[] generate)
        {
            for (int i = 0; i < 9; i++)
            {
                Console.WriteLine("\t" + generate[i].left + "->" + generate[i].right);
            }
        }
        public void DispTable()
        {
            //先將優先關系初始化為N
            for (int i = 0; i < 7; i++)
                for (int j = 0; j < 7; j++)
                {
                    priority[i, j] = 'N';
                }
            //存儲FIRSTVT集合
            char[] FS = new char[] { '#' };
            char[] FE = new char[] { '+', '*', '^', '(', 'i' };
            char[] FT = new char[] { '*', '^', '(', 'i' };
            char[] FF = new char[] { '^', '(', 'i' };

            priority[6, 6] = '=';//# = ＃
            priority[3, 4] = '=';//( = )
            //#<FIRSTVT(E)
            for (int i = 0; i <= 6; i++)
            {
                for (int j = 0; j < 5; j++)
                {
                    if (VT[i] == FE[j])
                    {
                        priority[3, i] = '<'; //( <FIRST(E)
                        priority[6, i] = '<';
                    }
                }
            }
            //+<FIRSTVT(T)
            for (int i = 0; i < 7; i++)
            {
                for (int j = 0; j < 4; j++)
                {
                    if (VT[i] == FT[j])
                        priority[0, i] = '<';
                }
            }
            //*<FIRSTVT(F)
            for (int i = 0; i < 7; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    if (VT[i] == FF[j])
                    {
                        priority[1, i] = '<';
                        priority[2, i] = '<';
                    }
                }
            }
            //存儲LASTVT集合
            char[] LE = new char[] { '+', '*', '^', ')', 'i' };
            char[] LT = new char[] { '*', '^', ')', 'i' };
            char[] LP = new char[] { ')', 'i' };
            for (int i = 0; i < 7; i++)
            {
                for (int j = 0; j < 5; j++)
                {
                    if (VT[i] == LE[j])
                    {
                        priority[i, 6] = '>';//LASTVT(E)> #
                        priority[i, 0] = '>';//LASTVT(E)> +
                        priority[i, 4] = '>';//LASTVT(E)> ')'
                    }
                }
            }
            //LASTVT(T)> *

            for (int i = 0; i < 7; i++)
            {
                for (int j = 0; j < 4; j++)
                {
                    if (VT[i] == LT[j])
                        priority[i, 1] = '>';
                }
            }
            //LASTVT(P)> '^'
            for (int i = 0; i < 7; i++)
            {
                for (int j = 0; j < 2; j++)
                {
                    if (VT[i] == LP[j])
                        priority[i, 2] = '>';
                }
            }
            //顯示算府優先關系表
            Console.WriteLine("算符優先關系表為：");
            Console.WriteLine("\t+\t*\t^\t(\t)\ti\t#\t");
            Console.WriteLine("----------------------------------------------------------");
            for (int i = 0; i < 7; i++)
            {
                Console.Write(VT[i] + "\t");
                for (int j = 0; j < 7; j++)
                    Console.Write(priority[i, j].ToString() + "\t");

                Console.WriteLine();
            }
            


        }
        public void process()
        {
            char result = ' ';
            char Q = ' ';
            string str="";
           
            //確保以#開頭和結尾
            while (strWhole.Substring(0, 1) != "#" || strWhole.Substring(strWhole.Length - 1, 1) != "#")
            {
                Console.WriteLine("請重新輸入，以#開頭和結尾：");
                strWhole = Console.ReadLine();
            }
            Console.WriteLine("棧         當前符號       剩余字符串    操作");
            readNext();
                Display();
            while (true )
            {
              
               
                if (isMemVT(stack[top],this .VT ))
                    j = top;
                else
                    j = top - 1;
                result = CompareChar(stack[j], tempChar, this.VT);
               
                if (result == '>')
                { 
                    Q = stack[j];
                   while (CompareChar(stack[j], Q, this.VT) != '<')
                    {
                        Q = stack[j];
                        if (isMemVT(stack[j - 1], this.VT))
                            j = j - 1;
                        else j = j - 2;
                    }
                    for (int i = j + 1; i <= top; i++)
                    {
                        str += stack[i];
                    }
                     Console.Write(  "\t歸約"+"\n");
                    top = j + 1;
                    stack[top] = 'N';
                    Display();
                   
                    
                }
                else if (result == '<')
                { Console.Write(" \t" + "移進" + "\n");
                    top = top + 1;
                    stack[top] = tempChar;
                    readNext(); 
                    Display();
                   
                  
                }
                else if (result == '=')
                {
                    if (stack[j] == '#')
                    {
                        if (p == strWhole.Length - 1)
                        {
                            Console.WriteLine();
                            Console.WriteLine("分析成功!");
                            break;
                        }
                        else
                        {
                            Console.WriteLine("出錯！");
                            break;
                        }
                    }
                    else
                    {
                        Console.Write("\t移進\n");
                        top = top + 1;
                        stack[top] = tempChar;
                        readNext();
                        Display();
                    }
                }
                else
                { 
                Console .WriteLine ("出錯！");
                break;
                }
            }
         

        }
        static void Display()
        {
            for (int i = 1; i <= top; i++)
            {
                Console.Write(stack[i]);
            }
            Console.Write("\t\t" + tempChar.ToString()+"\t\t");
            if (tempChar == '#')   Console.Write("");
            else
            {
                for (int i = p; i <= strWhole.Length - 1; i++)
                {
                    Console.Write(strWhole[i]);
                }
            }
            
        }
        static bool isMemVT(char c, char[] VT)
        {
            bool r = false;
            for (int i = 0; i <=VT.Length - 1; i++)
            {
                if (c == VT[i])
                {
                    r = true;
                    break;
                }
                    
            }
            return r;
        }

        static void readNext()
        {
            tempChar = strWhole [p];
            if (p <= strWhole.Length - 2)
                p += 1;
            else p = strWhole.Length - 1;
        }
        static char CompareChar(char c1, char c2, char[] VT)
        {

            int a = 0, b = 0;
            for (int i = 0; i < 7; i++)
            {
                if (VT[i] == c1) a = i;
                if (VT[i] == c2) b = i;

            }
            return priority[a, b];
        }
       public  static void clear()
        {
            top = 1;
            p = 1;
            j = 1;
            strWhole = "";
            tempChar =' ';
            strWhole="";
            char []stack = new char[30];
        }
    }
}