LR(0) 文法分析器 - 完善冲突检测
private void button2_Click(object sender, EventArgs e)
{
string str = richTextBox1.Text;
if (str.Length == 0)
{
MessageBox.Show("输入为空");
return;
}
string temp = "";
int i = 0;
while (i < str.Length)
{
temp = "";
while (i < str.Length && str[i] != '\r' && str[i] != '\n')
{
if (str[i] != ' ')
temp += str[i];
i++;
}
i++;
if (temp.Length > 0 && temp[temp.Length - 1] == '|')
{
MessageBox.Show("不得包含空串！");
return;
}
if (temp.Length > 3)
{
if (temp[0] < 'A' || temp[0] > 'Z')
{
MessageBox.Show("含有非法左部！");
return;
}
if (temp[1] != '-' || temp[2] != '>')
{
MessageBox.Show("产生式输入不规范！");
return;
}
for (int j = 3; j < temp.Length; j++)
{
if (!char.IsUpper(temp[j]) && !char.IsLower(temp[j]) && temp[j] != '|' && temp[j] != '*' && temp[j] != '+' && temp[j] != '(' && temp[j] != ')' && temp[j] != '[' && temp[j] != ']' && temp[j] != '{' && temp[j] != '}' && temp[j] != '.' && temp[j] != ',' && temp[j] != ';' && temp[j] != ':' && temp[j] != '=' && temp[j] != '<' && temp[j] != '>')
{
MessageBox.Show("含有非法字符！");
return;
}
}
}
if (temp.Length <= 3 && temp.Length > 0)
{
MessageBox.Show("产生式输入不规范！");
return;
}
}
if (LR0Judge(str))
{
MessageBox.Show("正确的LR(0)文法");
button4.Enabled = true;
button5.Enabled = true;
button6.Enabled = true;
}
else
{
MessageBox.Show("不是LR(0)文法！");
}
}
// 判断是否为LR(0)文法
private bool LR0Judge(string str)
{
// 构造产生式
List<Production> productions = new List<Production>();
string[] lines = str.Split(new char[] { '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries);
foreach (string line in lines)
{
string[] sides = line.Split(new char[] { '-', '>' }, StringSplitOptions.RemoveEmptyEntries);
Production production = new Production(sides[0][0], sides[1]);
productions.Add(production);
}
// 构造项集族
ItemSetCollection itemSetCollection = new ItemSetCollection(productions);
// 判断是否存在移进规约冲突
if (itemSetCollection.HasShiftReduceConflict())
{
return false;
}
// 判断是否存在规约规约冲突
if (itemSetCollection.HasReduceReduceConflict())
{
return false;
}
return true;
}
完善后的构造LR分析表函数button5_Click代码：
private void button5_Click(object sender, EventArgs e)
{
listView2.Clear();
LR.Table[][] table;
table = lr.GET_ANA();
int xlen = table.GetLength(0);
int ylen = table[1].Length;
listView2.Columns.Clear();
listView2.Items.Clear();
listView2.View = View.Details;
listView2.Columns.Add(" ");
for (int i = 0; i < lr.Echar.Count; i++)//添加表头
{
string text = lr.Echar[i].ToString();
listView2.Columns.Add(text, 58);
}
for (int i = 0; i < lr.Nchar.Count; i++)//添加表头
{
string text = lr.Nchar[i].ToString();
listView2.Columns.Add(text, 58);
}
for (int i = 0; i < xlen; i++)
{
ListViewItem li = new ListViewItem(i.ToString());
for (int j = 0; j < ylen; j++)
{
string st = "";
if (table[i][j].error)
st = "-";
else if (table[i][j].type == 'A')
st = "AC";
else if (table[i][j].type == 'S' || table[i][j].type == 'R')
{
if (table[i][j].shiftReduceConflict || table[i][j].reduceReduceConflict)
{
st = "Conflict";
}
else
{
st = table[i][j].type.ToString() + table[i][j].id.ToString();
}
}
li.SubItems.Add(st);
}
listView2.Items.Add(li);
}
listView2.GridLines = true;
}
相关调用函数：
public class ItemSetCollection
{
// 项集族
public List<ItemSet> ItemSets { get; private set; }
// 活前缀和非终结符
private List<char> _livePrefixes;
private List<char> _nonTerminals;
// 产生式
private List<Production> _productions;
// FIRST集
private Dictionary<char, HashSet<char>> _firstSets;
// FOLLOW集
private Dictionary<char, HashSet<char>> _followSets;
// LR(0)自动机
private LR0Automaton _automaton;
// 移进规约冲突
public bool HasShiftReduceConflict()
{
foreach (ItemSet itemSet in ItemSets)
{
foreach (Item item in itemSet.Items)
{
if (item.IsReduceItem)
{
if (itemSet.Actions.ContainsKey(item.FollowSymbol))
{
// 存在移进规约冲突
return true;
}
}
}
}
return false;
}
// 规约规约冲突
public bool HasReduceReduceConflict()
{
foreach (ItemSet itemSet in ItemSets)
{
List<Item> reduceItems = itemSet.Items.FindAll(p => p.IsReduceItem);
if (reduceItems.Count > 1)
{
HashSet<char> reduceSymbols = new HashSet<char>();
foreach (Item reduceItem in reduceItems)
{
reduceSymbols.Add(reduceItem.Production.Left);
}
if (reduceSymbols.Count > 1)
{
// 存在规约规约冲突
return true;
}
}
}
return false;
}
// 构造函数
public ItemSetCollection(List<Production> productions)
{
_productions = productions;
_livePrefixes = new List<char>();
_nonTerminals = new List<char>();
foreach (Production production in productions)
{
if (!_nonTerminals.Contains(production.Left))
{
_nonTerminals.Add(production.Left);
}
}
// 计算FIRST集和FOLLOW集
_firstSets = new Dictionary<char, HashSet<char>>();
_followSets = new Dictionary<char, HashSet<char>>();
foreach (char nonTerminal in _nonTerminals)
{
_firstSets.Add(nonTerminal, new HashSet<char>());
_followSets.Add(nonTerminal, new HashSet<char>());
}
foreach (char nonTerminal in _nonTerminals)
{
CalculateFirst(nonTerminal);
}
CalculateFollow();
// 构造项集族
_automaton = new LR0Automaton(productions, _firstSets, _followSets);
ItemSets = _automaton.BuildDFA();
}
// 计算非终结符的FIRST集
private void CalculateFirst(char nonTerminal)
{
foreach (Production production in _productions.FindAll(p => p.Left == nonTerminal))
{
if (production.Right.Length == 0)
{
_firstSets[nonTerminal].Add('#');
}
else
{
foreach (char symbol in production.Right)
{
if (char.IsUpper(symbol))
{
_firstSets[nonTerminal].UnionWith(_firstSets[symbol]);
if (!_livePrefixes.Contains(symbol))
{
break;
}
}
else
{
_firstSets[nonTerminal].Add(symbol);
break;
}
}
}
}
}
// 计算非终结符的FOLLOW集
private void CalculateFollow()
{
_followSets[_productions[0].Left].Add('#');
while (true)
{
bool changed = false;
foreach (Production production in _productions)
{
for (int i = 0; i < production.Right.Length; i++)
{
if (char.IsUpper(production.Right[i]))
{
bool hasEpsilon = false;
for (int j = i + 1; j < production.Right.Length; j++)
{
if (char.IsUpper(production.Right[j]))
{
_followSets[production.Right[i]].UnionWith(_firstSets[production.Right[j]]);
if (!_firstSets[production.Right[j]].Contains('#'))
{
hasEpsilon = false;
break;
}
}
else
{
_followSets[production.Right[i]].Add(production.Right[j]);
hasEpsilon = false;
break;
}
}
if (hasEpsilon || i == production.Right.Length - 1)
{
_followSets[production.Right[i]].UnionWith(_followSets[production.Left]);
}
}
}
}
if (!changed)
{
break;
}
}
}
}
public class LR0Automaton
{
// 项集族
private ItemSetCollection _itemSetCollection;
// 产生式
private List<Production> _productions;
// FIRST集
private Dictionary<char, HashSet<char>> _firstSets;
// FOLLOW集
private Dictionary<char, HashSet<char>> _followSets;
// 自动机的状态
private List<ItemSet> _states;
// 构造函数
public LR0Automaton(List<Production> productions, Dictionary<char, HashSet<char>> firstSets, Dictionary<char, HashSet<char>> followSets)
{
_productions = productions;
_firstSets = firstSets;
_followSets = followSets;
}
// 构造DFA
public List<ItemSet> BuildDFA()
{
_states = new List<ItemSet>();
// 初始项集
ItemSet initialItemSet = new ItemSet();
initialItemSet.AddItem(new Item(_productions[0], 0));
Closure(initialItemSet);
_states.Add(initialItemSet);
// 遍历项集族
for (int i = 0; i < _states.Count; i++)
{
ItemSet currentState = _states[i];
Dictionary<char, ItemSet> transitions = new Dictionary<char, ItemSet>();
// 计算当前项集的转移项集
foreach (Item item in currentState.Items)
{
if (!item.IsReduceItem)
{
char symbol = item.NextSymbol;
Item newItem = new Item(item.Production, item.DotPosition + 1);
if (!transitions.ContainsKey(symbol))
{
ItemSet newItemSet = new ItemSet();
newItemSet.AddItem(newItem);
Closure(newItemSet);
transitions.Add(symbol, newItemSet);
}
else
{
transitions[symbol].AddItem(newItem);
}
}
}
// 遍历转移项集
foreach (KeyValuePair<char, ItemSet> kvp in transitions)
{
ItemSet newItemSet = kvp.Value;
// 如果转移项集已存在，则添加转移边
ItemSet existingItemSet = _states.Find(p => p.Equals(newItemSet));
if (existingItemSet != null)
{
currentState.AddTransition(newItemSet, kvp.Key);
}
// 否则添加新的状态
else
{
currentState.AddTransition(newItemSet, kvp.Key);
_states.Add(newItemSet);
}
}
}
return _states;
}
// 计算闭包
private void Closure(ItemSet itemSet)
{
bool changed = true;
while (changed)
{
changed = false;
List<Item> closureItems = itemSet.Items.FindAll(p => !p.IsReduceItem && char.IsUpper(p.NextSymbol));
foreach (Item closureItem in closureItems)
{
foreach (Production production in _productions.FindAll(p => p.Left == closureItem.NextSymbol))
{
Item newItem = new Item(production, 0);
if (!itemSet.Items.Contains(newItem))
{
itemSet.AddItem(newItem);
changed = true;
}
}
}
}
}
}
public class Production
{
// 产生式左侧
public char Left { get; private set; }
// 产生式右侧
public string Right { get; private set; }
// 构造函数
public Production(char left, string right)
{
Left = left;
Right = right;
}
}
public class Item
{
// 产生式
public Production Production { get; private set; }
// 点的位置
public int DotPosition { get; private set; }
// 是否为规约项
public bool IsReduceItem { get { return DotPosition == Production.Right.Length; } }
// 下一个符号
public char NextSymbol { get { return IsReduceItem ? '#' : Production.Right[DotPosition]; } }
// 规约符号
public char FollowSymbol { get { return Production.Left; } }
// 构造函数
public Item(Production production, int dotPosition)
{
Production = production;
DotPosition = dotPosition;
}
}
public class ItemSet
{
// 项集中的项
public List<Item> Items { get; private set; }
// 状态之间的转移
public Dictionary<ItemSet, char> Transitions { get; private set; }
// 动作表
public Dictionary<char, LR.Table> Actions { get; private set; }
// 构造函数
public ItemSet()
{
Items = new List<Item>();
Transitions = new Dictionary<ItemSet, char>();
Actions = new Dictionary<char, LR.Table>();
}
// 添加项
public void AddItem(Item item)
{
if (!Items.Contains(item))
{
Items.Add(item);
}
}
// 添加转移边
public void AddTransition(ItemSet target, char symbol)
{
if (!Transitions.ContainsKey(target))
{
Transitions.Add(target, symbol);
}
}
// 判断两个项集是否相等
public override bool Equals(object obj)
{
if (obj == null || !(obj is ItemSet))
{
return false;
}
ItemSet other = (ItemSet)obj;
if (Items.Count != other.Items.Count)
{
return false;
}
foreach (Item item in Items)
{
if (!other.Items.Contains(item))
{
return false;
}
}
return true;
}
// 重写GetHashCode方法
public override int GetHashCode()
{
int hashCode = 0;
foreach (Item item in Items)
{
hashCode ^= item.GetHashCode();
}
return hashCode;
}
}
说明：
LR0Judge函数用于判断输入的文法是否为 LR(0) 文法。它通过构造产生式和项集族，并检查是否存在移进规约冲突和规约规约冲突来进行判断。HasShiftReduceConflict和HasReduceReduceConflict函数分别用于检测移进规约冲突和规约规约冲突。button5_Click函数用于构造 LR 分析表，并在表中显示冲突信息。ItemSetCollection类用于表示项集族，包括项集、FIRST 集、FOLLOW 集和 LR(0) 自动机。LR0Automaton类用于构造 LR(0) 自动机。Production类用于表示产生式。Item类用于表示项。ItemSet类用于表示项集。
使用方法：
- 将代码复制到 C# 项目中。
- 在项目中添加一个
richTextBox1用于输入文法，一个button2用于判断文法是否为 LR(0) 文法，一个button5用于构造 LR 分析表，以及其他必要控件。 - 将
button2_Click和button5_Click事件绑定到相应的代码。 - 运行程序，输入文法，并点击按钮进行判断和构造分析表。
示例：
E->E+T
E->T
T->T*F
T->F
F->(E)
F->id
上述文法为一个 LR(0) 文法，程序会输出正确的 LR(0) 分析表。
注意：
本代码仅实现了基本的 LR(0) 文法分析功能，并未包含其他功能，例如语义分析、代码生成等。
原文地址: https://www.cveoy.top/t/topic/oIdJ 著作权归作者所有。请勿转载和采集!