C# LR(0) 文法分析器实现 - 完整实验代码
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace LR0Parser
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
//--------------------预处理
Dictionary<string, List<string>> production;//产生式
Dictionary<string, List<string>> firsts;// first集
Dictionary<string, List<string>> follows;//follow集
Dictionary<string, List<string>> selects;//select集
Dictionary<string, Dictionary<string, string>> table;//预测分析表
List<string> terminals;//终结符
List<string> nonterminals;//非终结符
Stack<char> analyseStack;// 分析栈
Stack<char> inputStack;// 输入栈
List<string> resultAnalyse;// 分析栈的每一步变化
List<string> resultInput;// 输入栈的每一步变化
List<string> resultParse;// 每一步分析的结果，包括推导所用产生式或匹配成功/失败的信息
private int step = 0; // 记录当前分析到第几步
private void Form1_Load(object sender, EventArgs e)
{
// 初始化
production = new Dictionary<string, List<string>>();
firsts = new Dictionary<string, List<string>>();
follows = new Dictionary<string, List<string>>();
selects = new Dictionary<string, List<string>>();
table = new Dictionary<string, Dictionary<string, string>>();
terminals = new List<string>();
nonterminals = new List<string>();
analyseStack = new Stack<char>();
inputStack = new Stack<char>();
resultAnalyse = new List<string>();
resultInput = new List<string>();
resultParse = new List<string>();
// 读入文法
string[] lines = System.IO.File.ReadAllLines(@"grammar.txt");
foreach (string line in lines)
{
string[] parts = line.Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
string left = parts[0];
List<string> right = new List<string>();
for (int i = 2; i < parts.Length; i++)
{
right.Add(parts[i]);
if (!terminals.Contains(parts[i]) && !nonterminals.Contains(parts[i]))
{
if (i == 2)
{
nonterminals.Add(parts[i]);
}
else
{
terminals.Add(parts[i]);
}
}
}
production.Add(left, right);
}
// 计算first集
foreach (string symbol in terminals)
{
firsts.Add(symbol, new List<string> { symbol });
}
foreach (string symbol in nonterminals)
{
firsts.Add(symbol, new List<string>());
}
bool updated = true;
while (updated)
{
updated = false;
foreach (KeyValuePair<string, List<string>> entry in production)
{
string left = entry.Key;
List<string> right = entry.Value;
foreach (string symbol in right)
{
bool flag = true;
foreach (string s in firsts[symbol])
{
if (!firsts[left].Contains(s))
{
firsts[left].Add(s);
updated = true;
}
}
if (!right.Last().Equals(symbol))
{
flag = false;
}
foreach (string s in firsts[symbol])
{
if (!s.Equals("ε") && !firsts[left].Contains(s))
{
firsts[left].Add(s);
updated = true;
}
}
if (flag && !firsts[left].Contains("ε"))
{
firsts[left].Add("ε");
updated = true;
}
}
}
}
// 计算follow集
foreach (string symbol in nonterminals)
{
follows.Add(symbol, new List<string>());
}
follows["S"].Add("$");
updated = true;
while (updated)
{
updated = false;
foreach (KeyValuePair<string, List<string>> entry in production)
{
string left = entry.Key;
List<string> right = entry.Value;
for (int i = 0; i < right.Count; i++)
{
if (nonterminals.Contains(right[i]))
{
bool flag = true;
for (int j = i + 1; j < right.Count; j++)
{
foreach (string s in firsts[right[j]])
{
if (!s.Equals("ε") && !follows[right[i]].Contains(s))
{
follows[right[i]].Add(s);
updated = true;
}
}
if (!firsts[right[j]].Contains("ε"))
{
flag = false;
break;
}
}
if (flag)
{
foreach (string s in follows[left])
{
if (!follows[right[i]].Contains(s))
{
follows[right[i]].Add(s);
updated = true;
}
}
}
}
}
}
}
// 计算select集
foreach (KeyValuePair<string, List<string>> entry in production)
{
string left = entry.Key;
List<string> right = entry.Value;
selects.Add(left, new List<string>());
bool flag = true;
foreach (string symbol in right)
{
foreach (string s in firsts[symbol])
{
if (!s.Equals("ε") && !selects[left].Contains(s))
{
selects[left].Add(s);
}
}
if (!firsts[symbol].Contains("ε"))
{
flag = false;
break;
}
}
if (flag)
{
foreach (string s in follows[left])
{
if (!selects[left].Contains(s))
{
selects[left].Add(s);
}
}
}
}
// 构造预测分析表
foreach (string symbol in nonterminals)
{
table.Add(symbol, new Dictionary<string, string>());
foreach (string s in terminals)
{
table[symbol].Add(s, "");
}
}
foreach (KeyValuePair<string, List<string>> entry in production)
{
string left = entry.Key;
List<string> right = entry.Value;
foreach (string s in selects[left])
{
table[left][s] = entry.Key + " → " + String.Join(" ", right);
}
}
// 初始化分析栈和输入栈
analyseStack.Push('$');
analyseStack.Push('S');
inputStack.Push('$');
}
private void button1_Click(object sender, EventArgs e)
{
// 读入输入串
string input = textBox1.Text;
inputStack.Clear();
foreach (char c in input)
{
inputStack.Push(c);
}
inputStack.Push('$');
// 初始化分析栈和输出
analyseStack.Clear();
analyseStack.Push('$');
analyseStack.Push('S');
resultAnalyse.Clear();
resultInput.Clear();
resultParse.Clear();
step = 0;
// 开始分析
while (analyseStack.Count > 0)
{
char top = analyseStack.Pop();
char next = inputStack.Pop();
resultAnalyse.Add(new string(analyseStack.Reverse().ToArray()));
resultInput.Add(new string(inputStack.Reverse().ToArray()));
if (top == next)
{
resultParse.Add("匹配 " + top);
}
else if (nonterminals.Contains(top.ToString()) && terminals.Contains(next.ToString()) && !table[top.ToString()][next.ToString()].Equals(""))
{
string production = table[top.ToString()][next.ToString()];
resultParse.Add("使用产生式 " + production);
string[] parts = production.Split(new char[] { ' ', '→' }, StringSplitOptions.RemoveEmptyEntries);
for (int i = parts.Length - 1; i > 0; i--)
{
analyseStack.Push(parts[i][0]);
}
}
else
{
resultParse.Add("错误");
break;
}
step++;
}
// 输出分析结果
button7.Enabled = true;
button8.Enabled = true;
}
private void button7_Click(object sender, EventArgs e)
{
if (step < resultAnalyse.Count)
{
ListViewItem item = new ListViewItem((step + 1).ToString());
item.SubItems.Add(resultAnalyse[step]);
item.SubItems.Add(resultInput[step]);
item.SubItems.Add(resultParse[step]);
listView1.Items.Add(item);
step++;
}
else
{
MessageBox.Show("输出完毕");
button7.Enabled = false;
button8.Enabled = false;
}
}
private void button8_Click(object sender, EventArgs e)
{
listView1.Items.Clear();
for (int i = 0; i < resultAnalyse.Count; i++)
{
ListViewItem item = new ListViewItem((i + 1).ToString());
item.SubItems.Add(resultAnalyse[i]);
item.SubItems.Add(resultInput[i]);
item.SubItems.Add(resultParse[step]);
listView1.Items.Add(item);
}
MessageBox.Show("输出完毕");
button7.Enabled = false;
button8.Enabled = false;
}
}
}
使用方法：
- 在 VS 中创建一个新的 Windows Forms 应用程序项目。
- 将以上代码复制到
Form1.cs文件中。 - 创建一个名为
grammar.txt的文本文件，并将其放在与Form1.cs相同的目录中。 - 在
grammar.txt文件中输入文法规则，每个规则占一行，格式为：左部符号 → 右部符号1 右部符号2 ...，例如：
S → E
E → E + T
E → T
T → T * F
T → F
F → ( E )
F → id
- 运行程序，在文本框中输入要分析的字符串，然后点击“分析”按钮。
- 分析结果将显示在
ListView控件中。
代码说明：
production：存储文法规则的字典，键为左部符号，值为右部符号列表。firsts：存储每个符号的 First 集的字典。follows：存储每个符号的 Follow 集的字典。selects：存储每个产生式的 Select 集的字典。table：存储预测分析表的字典。terminals：存储终结符列表。nonterminals：存储非终结符列表。analyseStack：分析栈。inputStack：输入栈。resultAnalyse：存储分析栈每一步变化的列表。resultInput：存储输入栈每一步变化的列表。resultParse：存储每一步分析结果的列表。
注意：
- 本代码只实现了 LR(0) 分析器，无法处理所有文法。
- 文法规则中的符号必须与代码中的符号一致。
- 输入字符串中的符号必须与终结符一致。
- 确保
grammar.txt文件存在且格式正确。
更多信息：
- LR(0) 分析器：https://zh.wikipedia.org/wiki/LR%E5%88%86%E6%9E%90
- C# 语言：https://docs.microsoft.com/zh-cn/dotnet/csharp/
原文地址: https://www.cveoy.top/t/topic/fZvP 著作权归作者所有。请勿转载和采集!