LR(0) 文法分析器实现及判别
{
'title': 'LR(0) 文法分析器实现及判别',
'description': '该项目展示了如何使用 C# 语言实现 LR(0) 文法分析器，并提供判别 LR(0) 文法功能。代码包含 LR(0) 项目类、项集类、LR(0) 分析器类以及测试代码。',
'keywords': 'LR(0), 文法分析器, C#, 项目族, LR(0) 分析表, DFA, 判别 LR(0) 文法',
'content': 'private void button2_Click(object sender, EventArgs e)//判别LR0文法
{
Dictionary<string, List
private void button4_Click(object sender, EventArgs e)//生成项目族信息
{
Dictionary<string, List
// 显示项目族信息
dataGridView1.Columns.Clear();
dataGridView1.Columns.Add('状态', '状态');
dataGridView1.Columns.Add('项目族', '项目族');
int stateIndex = 0;
foreach (var state in states)
{
dataGridView1.Rows.Add();
dataGridView1.Rows[stateIndex].Cells[0].Value = state.Key;
string items = string.Join('\n', state.Value.items.Select(item => item.ToString()));
dataGridView1.Rows[stateIndex].Cells[1].Value = items;
stateIndex++;
}
}
private void button5_Click(object sender, EventArgs e)//构造LR分析表
{
Dictionary<string, List
// 显示分析表
dataGridView2.Columns.Clear();
dataGridView2.Columns.Add('状态', '状态');
foreach (var terminal in terminals)
{
dataGridView2.Columns.Add(terminal, terminal);
}
foreach (var nonterminal in nonterminals)
{
dataGridView2.Columns.Add(nonterminal, nonterminal);
}
int stateIndex = 0;
foreach (var state in table)
{
dataGridView2.Rows.Add();
dataGridView2.Rows[stateIndex].Cells[0].Value = state.Key;
int columnIndex = 1;
foreach (var action in state.Value)
{
dataGridView2.Rows[stateIndex].Cells[columnIndex].Value = action;
columnIndex++;
}
stateIndex++;
}
}
private void button7_Click(object sender, EventArgs e)//单步显示输入的待分析句子 { string input = textBox1.Text; if (input.Length > 0) { string symbol = input[0].ToString(); input = input.Substring(1); textBox1.Text = input; textBox2.Text += symbol + ' '; } }
private void button8_Click(object sender, EventArgs e)//一键显示输入的待分析句子 { textBox2.Text = textBox1.Text; }
private Dictionary<string, List
private void transformpro(Dictionary<string, List
private void getTerminals(Dictionary<string, List
private void getNonTerminals(Dictionary<string, List
private void buildDFA(Dictionary<string, List
// 初始化状态编号
stateNumbers = new Dictionary<ItemSet, int>();
states = new Dictionary<int, ItemSet>();
// 使用队列保存待处理的项集
Queue<ItemSet> queue = new Queue<ItemSet>();
stateNumbers[startSet] = 0;
states.Add(0, startSet);
queue.Enqueue(startSet);
while (queue.Count > 0)
{
ItemSet I = queue.Dequeue();
int stateNumber = stateNumbers[I];
// 计算 I 中每个符号的移进操作后得到的新项集，并添加到 DFA 中
foreach (string symbol in nonterminal.Union(terminals))
{
ItemSet J = GOTO(I, symbol, production, productions, nonterminals);
int index;
if (J.items.Count > 0)
{
index = iscommon(stateNumbers, states, J);
if (index == -1)// 如果该项集不为空且还没有被加入到状态集合中
{
stateNumbers[J] = states.Count;
states.Add(states.Count, J);
queue.Enqueue(J);
}
if (!transitions.ContainsKey(stateNumber))// 如果该项集不为空
{
transitions[stateNumber] = new HashSet<string>();
}
transitions[stateNumber].Add(symbol + (index != -1 ? index : stateNumbers[J]));
}
}
}
}
private Dictionary<int, List
private ItemSet CLOSURE(ItemSet I, Dictionary<string, List
foreach (Item i in I.items)
{
stack.Push(i);
}
while (stack.Count > 0)
{
Item i = stack.Pop();
if (i.dotIndex < i.RHS.Count && nonterminals.Contains(i.RHS[i.dotIndex])) // dot 后的符号为非终结符
{
string X = i.RHS[i.dotIndex];
foreach (List<string> prod in productions[X]) // 考虑 X -> Y1 Y2 ... Yk 的每个产生式
{
Item newI = new Item(X, prod, 0);
if (!J.items.Contains(newI))
{
J.items.Add(newI);
stack.Push(newI);
}
}
}
}
return J;
}
private ItemSet GOTO(ItemSet I, string X, Dictionary<string, List
return CLOSURE(J, production, productions, nonterminals);
}
private int iscommon(Dictionary<ItemSet, int> stateNumbers, Dictionary<int, ItemSet> states, ItemSet itemSet) { int flag; int index = -1; foreach (var item in stateNumbers.Keys) { flag = 0; if (item.items.Count == itemSet.items.Count) { foreach (var j in itemSet.items) { foreach (var i in item.items) { if (i.Equals(j)) { flag++; break; } } } if (flag == item.items.Count) index = stateNumbers[item]; } } return index; }
private int getproconut(ItemSet itemSet, Dictionary<string, List
private bool JudgeLR0(Dictionary<string, List
// Item 类
public class Item
{
public string LHS; // 产生式左部
public List
public Item(string lhs, List<string> rhs, int dotIndex)
{
this.LHS = lhs;
this.RHS = rhs;
this.dotIndex = dotIndex;
}
// 判断两个项目是否相等
public override bool Equals(object obj)
{
if (obj == null || GetType() != obj.GetType())
{
return false;
}
Item other = (Item)obj;
return LHS == other.LHS && dotIndex == other.dotIndex && RHS.Count == other.RHS.Count
&& new HashSet<string>(RHS).SetEquals(other.RHS);
}
public override int GetHashCode()
{
return LHS.GetHashCode() ^ dotIndex.GetHashCode() ^ RHS.GetHashCode();
}
public override string ToString()
{
List<string> tempRHS = new List<string>(RHS);
tempRHS.Insert(dotIndex, '.');
return $'{LHS}->{string.Join('', tempRHS)}';
}
}
// ItemSet 类
public class ItemSet
{
public HashSet
public ItemSet()
{
items = new HashSet<Item>();
}
public override bool Equals(object obj)
{
if (obj == null || GetType() != obj.GetType())
{
return false;
}
ItemSet otherSet = (ItemSet)obj;
return items.SetEquals(otherSet.items);
}
public override int GetHashCode()
{
return items.GetHashCode();
}
}
// 判断一个字符是否为终结符 private bool IsTerminal(char c) { if (char.IsUpper(c)) return false; return true; }
// 判断一个非终结符是否能推出空串
private bool IsReachEmpty(string symbol, Dictionary<string, List
// 计算 FIRST 集
private void GetFirst(string symbol, Dictionary<string, List
// 计算 FOLLOW 集
private void GetFollow(string symbol, Dictionary<string, List
原文地址: https://www.cveoy.top/t/topic/fZDG 著作权归作者所有。请勿转载和采集!