C# 语法分析器：使用 LL(1) 预测分析表进行语法分析

{"title":"C# 语法分析器：使用 LL(1) 预测分析表进行语法分析","description":"本文介绍了使用 C# 语言实现一个基于 LL(1) 预测分析表的语法分析器，并提供了详细的代码示例和功能解释，包括 FIRST 集、FOLLOW 集的计算、LL(1) 文法的判断、预测分析表的构建以及语法分析过程的实现。","keywords":"语法分析器, LL(1), 预测分析表, FIRST 集, FOLLOW 集, C#","content":"private\u0020void\u0020analyze\u0020()\n{\n\u0020\u0020//\u0020构建 LL(1)\u0020预测分析表\n\u0020\u0020Dictionary\u003Cstring,\u0020Dictionary\u003Cstring,\u0020string\u003E\u003E\u0020table\u0020=\u0020new\u0020Dictionary\u003Cstring,\u0020Dictionary\u003Cstring,\u0020string\u003E\u003E();\n\u0020\u0020GetSelect(production,\u0020firsts,\u0020follows);\n\n\u0020\u0020//\u0020初始化分析栈和输入栈\n\u0020\u0020Stack\u003Cchar\u003E\u0020analyseStack\u0020=\u0020new\u0020Stack\u003Cchar\u003E();\n\u0020\u0020Stack\u003Cchar\u003E\u0020inputStack\u0020=\u0020new\u0020Stack\u003Cchar\u003E();\n\u0020\u0020analyseStack.Push('#');\n\u0020\u0020analyseStack.Push(startSymbol[0]);\n\u0020\u0020inputStack.Push('#');\n\u0020\u0020for\u0020(int\u0020i\u0020=\u0020text.Length\u0020-\u00201; i\u0020>=\u00200; i--)\n\u0020\u0020\u0020\u0020inputStack.Push(text[i]);\n\n\u0020\u0020//\u0020初始化步骤、分析串、剩余输入串、推导所用产生式或匹配的列表\n\u0020\u0020List\u003Cstring\u003E\u0020steps\u0020=\u0020new\u0020List\u003Cstring\u003E();\n\u0020\u0020List\u003Cstring\u003E\u0020analyseStrings\u0020=\u0020new\u0020List\u003Cstring\u003E();\n\u0020\u0020List\u003Cstring\u003E\u0020inputStrings\u0020=\u0020new\u0020List\u003Cstring\u003E();\n\u0020\u0020List\u003Cstring\u003E\u0020productions\u0020=\u0020new\u0020List\u003Cstring\u003E();\n\n\u0020\u0020steps.Add("1");\n\u0020\u0020analyseStrings.Add(new\u0020string(analyseStack.ToArray()));\n\u0020\u0020inputStrings.Add(new\u0020string(inputStack.ToArray()));\n\u0020\u0020productions.Add("");\n\n\u0020\u0020//\u0020进行 LL(1)\u0020分析\n\u0020\u0020int\u0020step\u0020=\u00202;\n\u0020\u0020while\u0020(true)\n\u0020\u0020{\n\u0020\u0020\u0020\u0020//\u0020如果分析栈栈顶元素为终结符\n\u0020\u0020\u0020\u0020if\u0020(IsTerminal(analyseStack.Peek()))\n\u0020\u0020\u0020\u0020{\n\u0020\u0020\u0020\u0020\u0020\u0020//\u0020当两个栈都只剩下#时，说明匹配成功\n\u0020\u0020\u0020\u0020\u0020\u0020if\u0020(analyseStack.Peek()\u0020==\u0020inputStack.Peek()\u0020&&\u0020analyseStack.Count()\u0020==\u00201\u0020&&\u0020inputStack.Count()\u0020==\u00201)\n\u0020\u0020\u0020\u0020\u0020\u0020{\n\u0020\u0020\u0020\u0020\u0020\u0020\u0020\u0020steps.Add(step.ToString());\n\u0020\u0020\u0020\u0020\u0020\u0020\u0020\u0020analyseStrings.Add(new\u0020string(analyseStack.ToArray()));\n\u0020\u0020\u0020\u0020\u0020\u0020\u0020\u0020inputStrings.Add(new\u0020string(inputStack.ToArray()));\n\u0020\u0020\u0020\u0020\u0020\u0020\u0020\u0020productions.Add("成功");\n\u0020\u0020\u0020\u0020\u0020\u0020\u0020\u0020break;\n\u0020\u0020\u0020\u0020\u0020\u0020}\n\u0020\u0020\u0020\u0020\u0020\u0020if\u0020(analyseStack.Peek()\u0020==\u0020inputStack.Peek())\n\u0020\u0020\u0020\u0020\u0020\u0020{\n\u0020\u0020\u0020\u0020\u0020\u0020\u0020\u0020steps.Add(step.ToString());\n\u0020\u0020\u0020\u0020\u0020\u0020\u0020\u0020analyseStrings.Add(new\u0020string(analyseStack.ToArray()));\n\u0020\u0020\u0020\u0020\u0020\u0020\u0020\u0020inputStrings.Add(new\u0020string(inputStack.ToArray()));\n\u0020\u0020\u0020\u0020\u0020\u0020\u0020\u0020productions.Add("" + analyseStack.Peek() + ""匹配");\n\u0020\u0020\u0020\u0020\u0020\u0020\u0020\u0020analyseStack.Pop();\n\u0020\u0020\u0020\u0020\u0020\u0020\u0020\u0020inputStack.Pop();\n\u0020\u0020\u0020\u0020\u0020\u0020\u0020\u0020step++;\n\u0020\u0020\u0020\u0020\u0020\u0020\u0020\u0020continue;\n\u0020\u0020\u0020\u0020\u0020\u0020}\n\u0020\u0020\u0020\u0020\u0020\u0020else\n\u0020\u0020\u0020\u0020\u0020\u0020{\n\u0020\u0020\u0020\u0020\u0020\u0020\u0020\u0020steps.Add(step.ToString());\n\u0020\u0020\u0020\u0020\u0020\u0020\u0020\u0020analyseStrings.Add(new\u0020string(analyseStack.ToArray()));\n\u0020\u0020\u0020\u0020\u0020\u0020\u0020\u0020inputStrings.Add(new\u0020string(inputStack.ToArray()));\n\u0020\u0020\u0020\u0020\u0020\u0020\u0020\u0020productions.Add("失败");\n\u0020\u0020\u0020\u0020\u0020\u0020\u0020\u0020break;\n\u0020\u0020\u0020\u0020\u0020\u0020}\n\u0020\u0020\u0020\u0020}\n\n\u0020\u0020\u0020\u0020string\u0020noTerminal\u0020=\u0020analyseStack.Peek().ToString();\n\u0020\u0020\u0020\u0020string\u0020terminal\u0020=\u0020inputStack.Peek().ToString();\n\n\u0020\u0020\u0020\u0020//\u0020如果分析表中没有该产生式，则匹配失败\n\u0020\u0020\u0020\u0020if\u0020(!table.ContainsKey(noTerminal)\u0020||\u0020!table[noTerminal].ContainsKey(terminal))\n\u0020\u0020\u0020\u0020{\n\u0020\u0020\u0020\u0020\u0020\u0020steps.Add(step.ToString());\n\u0020\u0020\u0020\u0020\u0020\u0020analyseStrings.Add(new\u0020string(analyseStack.ToArray()));\n\u0020\u0020\u0020\u0020\u0020\u0020inputStrings.Add(new\u0020string(inputStack.ToArray()));\n\u0020\u0020\u0020\u0020\u0020\u0020productions.Add("失败");\n\u0020\u0020\u0020\u0020\u0020\u0020break;\n\u0020\u0020\u0020\u0020}\n\n\u0020\u0020\u0020\u0020//\u0020获取推导产生式\n\u0020\u0020\u0020\u0020string\u0020production\u0020=\u0020table[noTerminal][terminal];\n\u0020\u0020\u0020\u0020productions.Add(noTerminal\u0020+\u0020"->"\u0020+\u0020production);\n\n\u0020\u0020\u0020\u0020//\u0020将推导产生式中的符号压入分析栈\n\u0020\u0020\u0020\u0020analyseStack.Pop();\n\u0020\u0020\u0020\u0020if\u0020(!production.Equals("#"))\n\u0020\u0020\u0020\u0020{\n\u0020\u0020\u0020\u0020\u0020\u0020for\u0020(int\u0020i\u0020=\u0020production.Length\u0020-\u00201; i\u0020>=\u00200; i--)\n\u0020\u0020\u0020\u0020\u0020\u0020\u0020\u0020analyseStack.Push(production[i]);\n\u0020\u0020\u0020\u0020}\n\n\u0020\u0020\u0020\u0020//\u0020更新分析栈和输入栈的变化\n\u0020\u0020\u0020\u0020analyseStrings.Add(new\u0020string(analyseStack.ToArray()));\n\u0020\u0020\u0020\u0020inputStrings.Add(new\u0020string(inputStack.ToArray()));\n\u0020\u0020\u0020\u0020step++;\n\u0020\u0020}\n\n\u0020\u0020//\u0020在界面第二行之后展示步骤、分析串、剩余输入串、推导所用产生式或匹配\n\u0020\u0020listView4.Columns.Clear();\n\u0020\u0020listView4.Items.Clear();\n\u0020\u0020listView4.View\u0020=\u0020View.Details;\n\n\n\u0020\u0020listView4.Columns.Add("步骤",\u002060,\u0020HorizontalAlignment.Center);\n\u0020\u0020listView4.Columns.Add("分析串",\u002060,\u0020HorizontalAlignment.Center);\n\u0020\u0020listView4.Columns.Add("剩余输入串",\u002080,\u0020HorizontalAlignment.Center);\n\u0020\u0020listView4.Columns.Add("推导所用产生式或匹配",\u0020150,\u0020HorizontalAlignment.Center);\n\n\u0020\u0020for\u0020(int\u0020i\u0020=\u00200; i\u0020<\u0020steps.Count(); i++)\n\u0020\u0020{\n\u0020\u0020\u0020\u0020ListViewItem\u0020item\u0020=\u0020new\u0020ListViewItem(steps[i]);\n\u0020\u0020\u0020\u0020item.SubItems.Add(analyseStrings[i]);\n\u0020\u0020\u0020\u0020item.SubItems.Add(inputStrings[i]);\n\u0020\u0020\u0020\u0020item.SubItems.Add(productions[i]);\n\u0020\u0020\u0020\u0020listView4.Items.Add(item);\n\u0020\u0020}\n\u0020\u0020button8.Enabled\u0020=\u0020true;\n\u0020\u0020button9.Enabled\u0020=\u0020true;\n}\n private\u0020void\u0020button7_Click(object\u0020sender,\u0020EventArgs\u0020e)\n{\n\u0020\u0020string\u0020text\u0020=\u0020textBox1.Text;\n\u0020\u0020analyze();\n\n\u0020\u0020//\u0020在界面第二行之后展示步骤、分析串、剩余输入串、推导所用产生式或匹配\n\u0020\u0020listView4.Columns.Clear();\n\u0020\u0020listView4.Items.Clear();\n\u0020\u0020listView4.View\u0020=\u0020View.Details;\n\n\n\u0020\u0020listView4.Columns.Add("步骤",\u002060,\u0020HorizontalAlignment.Center);\n\u0020\u0020listView4.Columns.Add("分析串",\u002060,\u0020HorizontalAlignment.Center);\n\u0020\u0020listView4.Columns.Add("剩余输入串",\u002080,\u0020HorizontalAlignment.Center);\n\u0020\u0020listView4.Columns.Add("推导所用产生式或匹配",\u0020150,\u0020HorizontalAlignment.Center);\n\n\u0020\u0020button8.Enabled\u0020=\u0020true;\n\u0020\u0020button9.Enabled\u0020=\u0020true;\n }