LL(1) 语法分析器实现 - C# 代码示例

// 定义一个用于存储产生式的类
public class Production
{
    public string Left { get; set; }
    public string Right { get; set; }
}

// 定义一个用于存储分析表的类
public class ParseTable
{
    private Dictionary<string, Dictionary<string, string>> table = new Dictionary<string, Dictionary<string, string>>();

    // 添加产生式到分析表中
    public void AddProduction(Production production)
    {  // 如果分析表中没有这个非终结符，则添加一个新的字典
        if (!table.ContainsKey(production.Left))
        {
            table.Add(production.Left, new Dictionary<string, string>());
        }
        // 将产生式添加到分析表中
        table[production.Left].Add(production.Right, production.Right);
    }

    // 获取分析表中对应非终结符和终结符的产生式
    public string GetProduction(string nonterminal, string terminal)
    {
        if (table.ContainsKey(nonterminal) && table[nonterminal].ContainsKey(terminal))
        {
            return table[nonterminal][terminal];
        }
        return null;
    }
}

// 定义一个用于存储输入符号栈的类
public class InputStack
{
    private Stack<char> stack = new Stack<char>();

    // 将符号压入栈中
    public void Push(char symbol)
    {
        stack.Push(symbol);
    }

    // 从栈中弹出符号
    public char Pop()
    {
        return stack.Pop();
    }

    // 获取栈顶元素
    public char Peek()
    {
        return stack.Peek();
    }

    // 获取栈的字符串表示
    public override string ToString()
    {
        return string.Join("", stack.Reverse());
    }

    // 判断栈是否为空
    public bool IsEmpty()
    {
        return stack.Count == 0;
    }
}

// 定义一个用于存储分析符号栈的类
public class AnalyseStack
{
    private Stack<char> stack = new Stack<char>();

    // 将符号压入栈中
    public void Push(char symbol)
    {
        stack.Push(symbol);
    }

    // 从栈中弹出符号
    public char Pop()
    {
        return stack.Pop();
    }

    // 获取栈顶元素
    public char Peek()
    {
        return stack.Peek();
    }

    // 获取栈的字符串表示
    public override string ToString()
    {
        return string.Join("", stack.Reverse());
    }

    // 判断栈是否为空
    public bool IsEmpty()
    {
        return stack.Count == 0;
    }
}

// 定义一个用于存储分析结果的类
public class AnalyseResult
{
    public List<string> AnalyseStack { get; set; } = new List<string>();
    public List<string> InputStack { get; set; } = new List<string>();
    public List<string> ParseResult { get; set; } = new List<string>();
}

// 语法分析器类
public class Parser
{
    private ParseTable table = new ParseTable();
    private InputStack inputStack = new InputStack();
    private AnalyseStack analyseStack = new AnalyseStack();
    private AnalyseResult result = new AnalyseResult();

    // 初始化语法分析器
    public void Initialize(List<Production> productions)
    {
        // 将产生式添加到分析表中
        foreach (Production production in productions)
        {
            table.AddProduction(production);
        }
    }

    // 执行语法分析
    public AnalyseResult Analyse(string input)
    {
        // 将输入字符串逆序压入输入栈中
        for (int i = input.Length - 1; i >= 0; i--)
        {
            inputStack.Push(input[i]);
        }
        // 将开始符号压入分析栈中
        analyseStack.Push('S');
        // 执行分析过程
        while (!inputStack.IsEmpty() || !analyseStack.IsEmpty())
        {
            // 获取分析栈的栈顶元素和输入栈的栈顶元素
            char topAnalyse = analyseStack.Peek();
            char topInput = inputStack.Peek();
            // 如果分析栈的栈顶元素为非终结符
            if (char.IsUpper(topAnalyse))
            {
                // 获取分析表中对应非终结符和终结符的产生式
                string production = table.GetProduction(topAnalyse.ToString(), topInput.ToString());
                // 如果分析表中没有产生式，则出错
                if (production == null)
                {
                    result.ParseResult.Add('出错');
                    break;
                }
                // 将产生式从分析栈中弹出
                analyseStack.Pop();
                // 如果产生式不是空串，则将产生式中的符号逆序压入分析栈中
                if (production != '#')
                {
                    for (int i = production.Length - 1; i >= 0; i--)
                    {
                        analyseStack.Push(production[i]);
                    }
                }
                // 记录分析结果
                result.AnalyseStack.Add(analyseStack.ToString());
                result.InputStack.Add(inputStack.ToString());
                result.ParseResult.Add(topAnalyse + " -> " + production);
            }
            // 如果分析栈的栈顶元素为终结符
            else
            {
                // 如果分析栈的栈顶元素和输入栈的栈顶元素相同，则进行匹配
                if (topAnalyse == topInput)
                {
                    // 将匹配的元素从分析栈和输入栈中弹出
                    analyseStack.Pop();
                    inputStack.Pop();
                    // 记录分析结果
                    result.AnalyseStack.Add(analyseStack.ToString());
                    result.InputStack.Add(inputStack.ToString());
                    result.ParseResult.Add('"' + topAnalyse + '"' + " 匹配");
                }
                // 如果分析栈的栈顶元素和输入栈的栈顶元素不相同，则出错
                else
                {
                    result.ParseResult.Add('出错');
                    break;
                }
            }
        }
        // 如果分析栈和输入栈都为空，则分析成功
        if (analyseStack.IsEmpty() && inputStack.IsEmpty())
        {
            result.ParseResult.Add('成功');
        }
        // 返回分析结果
        return result;
    }
}

// 测试用例
public class Program
{
    public static void Main(string[] args)
    {
        // 定义产生式
        List<Production> productions = new List<Production>
        {
            new Production { Left = 'S', Right = 'A' },
            new Production { Left = 'A', Right = 'B' },
            new Production { Left = 'B', Right = 'C' },
            new Production { Left = 'C', Right = 'a' },
            new Production { Left = 'C', Right = 'b' }
        };
        // 初始化语法分析器
        Parser parser = new Parser();
        parser.Initialize(productions);
        // 执行语法分析
        AnalyseResult result = parser.Analyse("aba");
        // 打印分析结果
        Console.WriteLine("分析栈：");
        foreach (string stack in result.AnalyseStack)
        {
            Console.WriteLine(stack);
        }
        Console.WriteLine("输入栈：");
        foreach (string stack in result.InputStack)
        {
            Console.WriteLine(stack);
        }
        Console.WriteLine("分析结果：");
        foreach (string resultItem in result.ParseResult)
        {
            Console.WriteLine(resultItem);
        }
        Console.ReadLine();
    }
}