• 日期: 2028-11-07
  • 标签: 常规

{ 'title': 'LR(0) 文法判别器 - C# 实现', 'description': '使用 C# 代码实现 LR(0) 文法判别器，并提供可视化界面，方便用户输入文法，判别文法是否为 LR(0) 文法。', 'keywords': 'LR(0), 文法判别器, C#, 程序实现, 可视化界面', 'content': 'private void button2_Click(object sender, EventArgs e)//判别LR0文法 { Dictionary<string, List> production = new Dictionary<string, List>(); // 获取用户输入的文法规则 //...

Dictionary<string, List<string>> first = new Dictionary<string, List<string>>();
Dictionary<string, List<string>> follow = new Dictionary<string, List<string>>();

// 计算 FIRST 集和 FOLLOW 集
GetFirst(production.Keys.First(), production, first);
foreach (var symbol in production.Keys)
{
    GetFollow(symbol, production, first, follow);
}

// 判断文法是否为 LR(0) 文法
if (JudgeLR0(production, first, follow))
{
    MessageBox.Show('该文法是 LR(0) 文法！');
}
else
{
    MessageBox.Show('该文法不是 LR(0) 文法！');
}

}

private void button4_Click(object sender, EventArgs e)//生成项目族信息 { // 获取用户输入的文法规则 //...

// 创建 LR0 分析器
LR0 lr0 = new LR0(production);

// 获取项目族信息
Dictionary<int, ItemSet> states = lr0.states;

// 将项目族信息显示在 dataGridView1 中
dataGridView1.DataSource = states.Select((state, index) => new { State = index, Items = string.Join('\n', state.Value.items.Select(item => item.ToString())) }).ToList();

}

private void button5_Click(object sender, EventArgs e)//构造LR分析表 { // 获取用户输入的文法规则 //...

// 创建 LR0 分析器
LR0 lr0 = new LR0(production);

// 获取分析表
Dictionary<int, List<string>> table = lr0.table;

// 将分析表显示在 dataGridView2 中
dataGridView2.DataSource = table.Select((row, index) => new { State = index }.Concat(row.Value.Select((cell, column) => new { Column = lr0.terminals.Union(lr0.nonterminal).ToList()[column], Value = cell }))).ToList();

}

private void button7_Click(object sender, EventArgs e)//单步显示输入的待分析句子 { // 获取待分析句子 string input = textBox1.Text;

// 获取用户输入的文法规则
//...

// 创建 LR0 分析器
LR0 lr0 = new LR0(production);

// 创建分析栈
Stack<int> stack = new Stack<int>();
stack.Push(0);

// 创建输入符号序列
List<string> inputSymbols = input.Split(' ').ToList();
inputSymbols.Add('#');

// 初始化状态
int state = 0;

// 初始化当前输入符号
string currentSymbol = inputSymbols[0];

// 单步执行分析过程
while (true)
{
    // 获取当前状态和当前输入符号对应的动作
    string action = lr0.table[state][lr0.terminals.IndexOf(currentSymbol)];

    // 执行动作
    switch (action[0])
    {
        case 'S':
            // 移进
            int newState = int.Parse(action.Substring(1));
            stack.Push(newState);
            state = newState;
            currentSymbol = inputSymbols[1];
            inputSymbols.RemoveAt(0);
            break;
        case 'r':
            // 归约
            int productionIndex = int.Parse(action.Substring(1));
            // 根据产生式规则进行归约
            //...
            break;
        case 'a':
            // 接受
            MessageBox.Show('接受！');
            return;
        default:
            MessageBox.Show('错误！');
            return;
    }
}

}

private void button8_Click(object sender, EventArgs e)//一键显示输入的待分析句子 { // 获取待分析句子 string input = textBox1.Text;

// 获取用户输入的文法规则
//...

// 创建 LR0 分析器
LR0 lr0 = new LR0(production);

// 创建分析栈
Stack<int> stack = new Stack<int>();
stack.Push(0);

// 创建输入符号序列
List<string> inputSymbols = input.Split(' ').ToList();
inputSymbols.Add('#');

// 初始化状态
int state = 0;

// 初始化当前输入符号
string currentSymbol = inputSymbols[0];

// 一键执行分析过程
while (true)
{
    // 获取当前状态和当前输入符号对应的动作
    string action = lr0.table[state][lr0.terminals.IndexOf(currentSymbol)];

    // 执行动作
    switch (action[0])
    {
        case 'S':
            // 移进
            int newState = int.Parse(action.Substring(1));
            stack.Push(newState);
            state = newState;
            currentSymbol = inputSymbols[1];
            inputSymbols.RemoveAt(0);
            break;
        case 'r':
            // 归约
            int productionIndex = int.Parse(action.Substring(1));
            // 根据产生式规则进行归约
            //...
            break;
        case 'a':
            // 接受
            MessageBox.Show('接受！');
            return;
        default:
            MessageBox.Show('错误！');
            return;
    }
}

}

// 计算 FIRST 集 private void GetFirst(string symbol, Dictionary<string, List> production1, Dictionary<string, List> firsts1) { // 如果该非终结符的 FIRST 集已经被计算出，则直接返回 if (firsts1.ContainsKey(symbol)) { return; } firsts1.Add(symbol, new List()); // 遍历产生式，计算 FIRST 集 foreach (var prod in production1[symbol]) { // 如果产生式首字符为终结符，则直接将其加入 FIRST 集中 if (prod.Length > 0 && IsTerminal(prod[0])) { if (!firsts1[symbol].Contains(prod[0].ToString())) firsts1[symbol].Add(prod[0].ToString()); continue; } // 如果产生式首字符为非终结符，则计算该非终结符的 FIRST 集，并将结果加入首字符的 FIRST 集中 else if (prod.Length > 0 && !IsTerminal(prod[0])) { GetFirst(prod[0].ToString(), production1, firsts1); foreach (var f in firsts1[prod[0].ToString()]) { if (!firsts1[symbol].Contains(f) && !f.Equals('#')) firsts1[symbol].Add(f); } } //如果第一个非终结符能推出#
if (IsReachEmpty(prod[0].ToString(), production1)) { // 递归计算第二个和后面的字符的 FIRST 集，并将结果加入该非终结符的 FIRST 集中 for (int j = 1; j < prod.Length; j++) { if (IsTerminal(prod[j])) { if (!firsts1[symbol].Contains(prod[j].ToString())) firsts1[symbol].Add(prod[j].ToString()); break; } GetFirst(prod[j].ToString(), production1, firsts1); foreach (var f in firsts1[prod[j].ToString()]) { if (!firsts1[symbol].Contains(f) && !f.Equals('#')) firsts1[symbol].Add(f); } // 如果该非终结符的 FIRST 集没有包含空串，则可以结束循环 if (!IsReachEmpty(prod[j].ToString(), production1)) { break; } // 如果是最后一个字符且所有非终结符的 FIRST 集都含有空串，则将空串加入该非终结符的 FIRST 集中 if (j == prod.Length - 1) { if (!firsts1[symbol].Contains('#')) firsts1[symbol].Add('#'); } } } } }

// 判断一个字符是否为终结符 private bool IsTerminal(char c) { if (char.IsUpper(c)) return false; return true; }

// 判断一个非终结符是否能推出空串 private bool IsReachEmpty(string symbol, Dictionary<string, List> production1) { if (!production1.ContainsKey(symbol)) return false; foreach (var prod in production1[symbol]) { if (prod.Equals('#')) return true; bool flag = true; for (int i = 0; i < prod.Length; i++) { if (!IsReachEmpty(prod[i].ToString(), production1)) { flag = false; break; } } if (flag) return true; } return false; }

// 计算 FOLLOW 集 private void GetFollow(string symbol, Dictionary<string, List> production1, Dictionary<string, List> firsts1, Dictionary<string, List> follows1) { // 如果该非终结符的 FOLLOW 集已经被计算出，则直接返回 if (follows1.ContainsKey(symbol)) { return; } follows1.Add(symbol, new List()); // 如果是起始符号，则将 # 加入 FOLLOW 集中 if (symbol.Equals(production1.Keys.First())) { if (!follows1[symbol].Contains('#')) follows1[symbol].Add('#'); } // 遍历产生式，计算 FOLLOW 集 foreach (var item in production1) { foreach (var prod in item.Value) { int index = prod.IndexOf(symbol); if (index == -1) continue; // 如果该非终结符位于产生式末尾，则将产生式左部的 FOLLOW 集加入该非终结符的 FOLLOW 集中 if (index == prod.Length - 1) { GetFollow(item.Key, production1, firsts1, follows1); foreach (var f in follows1[item.Key]) { if (!follows1[symbol].Contains(f)) follows1[symbol].Add(f); } } else { // 如果该非终结符后面是终结符，则将该终结符加入该非终结符的 FOLLOW 集中 if (IsTerminal(prod[index + 1])) { if (!follows1[symbol].Contains(prod[index + 1].ToString())) follows1[symbol].Add(prod[index + 1].ToString()); } // 如果该非终结符后面是非终结符，则将该非终结符的 FIRST 集加入该非终结符的 FOLLOW 集中 else { GetFirst(prod[index + 1].ToString(), production1, firsts1); foreach (var f in firsts1[prod[index + 1].ToString()]) { if (!f.Equals('#') && !follows1[symbol].Contains(f)) follows1[symbol].Add(f); } // 如果该非终结符后面的所有符号都能推出空串，则将产生式左部的 FOLLOW 集加入该非终结符的 FOLLOW 集中 if (IsReachEmpty(prod[index + 1].ToString(), production1)) { GetFollow(item.Key, production1, firsts1, follows1); foreach (var f in follows1[item.Key]) { if (!follows1[symbol].Contains(f)) follows1[symbol].Add(f); } } } } } } } public bool JudgeLR0(Dictionary<string, List> production, Dictionary<string, List> first, Dictionary<string, List> follow) { // 遍历每个产生式 foreach (var item in production) { // 遍历该产生式的所有右部 foreach (var prod in item.Value) { // 遍历该产生式右部的每个符号 for (int i = 0; i < prod.Length; i++) { // 如果该符号是非终结符 if (!IsTerminal(prod[i])) { // 计算该非终结符的 FIRST 集 GetFirst(prod[i].ToString(), production, first); // 遍历该非终结符的 FIRST 集 foreach (var f in first[prod[i].ToString()]) { // 如果该非终结符的 FIRST 集中包含当前符号 if (f.Equals(prod[i].ToString())) { // 检查该非终结符的 FOLLOW 集是否包含当前符号 if (follow[item.Key].Contains(prod[i].ToString())) { // 如果 FOLLOW 集中包含当前符号，则该文法不是 LR(0) 文法 return false; } } } } } } } // 如果遍历完所有产生式都没有发现冲突，则该文法是 LR(0) 文法 return true; }

// 类 LR0 class LR0 { public List terminals; // 终结符集合 public List nonterminal;// 非终结符集合 public Dictionary<string, List> production;//继承LL1中的原始产生式 public Dictionary<string, List<List>> productions; // 产生式规则（包含全部规则）

public Dictionary<int, HashSet<string>> transitions; // 状态转移函数
public Dictionary<ItemSet, int> stateNumbers; // 状态编号
public Dictionary<int, ItemSet> states; // 状态集合
public Dictionary<int, List<string>> table;

public LR0(Dictionary<string, List<string>> production)
{
    // 初始化终结符集合和非终结符集合
    terminals = new List<string>();
    nonterminal = new List<string>();
    foreach (var item in production)
    {
        if (!nonterminal.Contains(item.Key))
            nonterminal.Add(item.Key);
        foreach (var item2 in item.Value)
        {
            foreach (var symbol in item2)
            {
                if (IsTerminal(symbol) && !terminals.Contains(symbol))
                    terminals.Add(symbol.ToString());
            }
        }
    }
    terminals.Add('#');
    // 初始化产生式规则
    productions = new Dictionary<string, List<List<string>>>();
    foreach (var item in production)
    {
        productions.Add(item.Key, new List<List<string>>());
        foreach (var item2 in item.Value)
        {
            List<string> proitem = new List<string>();
            for (int i = 0; i < item2.Length; i++)
                proitem.Add(item2[i].ToString());
            productions[item.Key].Add(proitem);
        }
    }
    // 初始化状态转移函数
    transitions = new Dictionary<int, HashSet<string>>();
    // 构建 DFA
    buildDFA();
    // 构建分析表
    buildtable();
}

private ItemSet CLOSURE(ItemSet I)
{
    ItemSet J = new ItemSet();
    foreach (var item in I.items)
        J.items.Add(item);
    Stack<Item> stack = new Stack<Item>();

    foreach (Item i in I.items)
    {
        stack.Push(i);
    }

    while (stack.Count > 0)
    {
        Item i = stack.Pop();
        if (i.dotIndex < i.RHS.Count && nonterminal.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)
{
    ItemSet J = new ItemSet();
    foreach (Item i in I.items)
    {
        if (i.dotIndex < i.RHS.Count && i.RHS[i.dotIndex] == X)
        {
            Item newI = new Item(i.LHS, i.RHS, i.dotIndex + 1);
            J.items.Add(newI);
        }
    }

    return CLOSURE(J);
}

private int iscommon(Dictionary<ItemSet, int> states, ItemSet itemSet)
{
    int flag;
    int index=-1;
    foreach(var item in states.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=states[item];
        }
    }
    return index;
}

private void buildDFA()
{
    //构造初始项目集
    string s = productions.Keys.First() + ''';
    Item startItem = new Item(s, new List<string>() { productions.Keys.First() }, 0);
    ItemSet startSet = new ItemSet();
    startSet.items.Add(startItem);
    startSet = CLOSURE(startSet);

    // 初始化状态编号
    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);
            int index;

            if (J.items.Count > 0) 
            {
                index = iscommon(stateNumbers, 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 int getproconut(ItemSet itemSet)
{
    int index = 1;
    if (itemSet.items.Count == 1)
    {
        foreach (var item in itemSet.items)
            if(item.dotIndex == item.RHS.Count)
            {
                foreach(var key in productions.Keys)
                {
                    if (key.Equals(item.LHS))
                    {
                        foreach( var item2 in productions[key])
                        {
                            if (item.RHS.Equals(item2)) return index;
                            else index++;
                        }
                    }
                    index += productions[key].Count;
                }
                return index;
            }
    }
    return -1;
}
private void buildtable()
{
    int flag = 0;
    table = new Dictionary<int, List<string>>();
    for(int i=0;i<states.Count; i++)
    {
        //对每个状态经过终结符的情况进行判断
        List<string> strings = new List<string>();
        foreach(var symbol in terminals)
        {
            flag = 0;
            if (transitions.ContainsKey(i))
            {
                foreach (var item in transitions[i])
                {
                    if (item[0].ToString().Equals(symbol))
                    {
                        strings.Add('S'+item.Substring(1));
                        flag = 1;
                        break;
                    }
                }
                if (flag==0)strings.Add('');
            }
            else
            {
                if (states[i].items.First().LHS.Equals(production.Keys.First() + '''))
                {
                    if(symbol.Equals('#')) strings.Add('acc');
                    else strings.Add('');
                }
                else
                {
                    int index = getproconut(states[i]);
                    strings.Add('r' + index);
                }
            }
        }
        //对每个状态经过非终结符的情况进行判断
        foreach(var t in nonterminal)
        {
            flag = 0;
            if (transitions.ContainsKey(i))
            {
                foreach (var item in transitions[i])
                {
                    if (item[0].ToString().Equals(t))
                    {
                        strings.Add(item.Substring(1));
                        flag = 1;
                        break;
                    }
                }
                if (flag == 0) strings.Add('');
            }
            else strings.Add('');
        }
        table.Add(i,strings);
    }
}

} // 类 Item class Item { public string LHS; // 产生式左部 public List RHS; // 产生式右部 public int dotIndex; // 点的位置

public Item(string lhs, List<string> rhs, int dotIndex)
{
    this.LHS = lhs;
    this.RHS = rhs;
    this.dotIndex = dotIndex;
}

// 判断两个项目是否相等
public bool Equals(Item other)
{
    return LHS == other.LHS && dotIndex == other.dotIndex && RHS.Count == other.RHS.Count
            && new HashSet<string>(RHS).SetEquals(other.RHS);
}

public override string ToString()
{
    List<string> tempRHS = new List<string>(RHS);
    tempRHS.Insert(dotIndex, '.');
    return $'{LHS}->{string.Join('',tempRHS)}';
}

public string ToString2()
{
    List<string> tempRHS = new List<string>(RHS);
    return $'{LHS}->{string.Join('', tempRHS)}';
}

} // 类 ItemSet class ItemSet { public HashSet items;

public ItemSet()
{
    items = new HashSet<Item>();
}

public override bool Equals(object other)
{
    if (other == null || GetType() != other.GetType())
    {
        return false;
    }

    ItemSet otherSet = (ItemSet)other;
    return items.SetEquals(otherSet.items);
}

//public override string ToString()
//{
//    return string.Join('\n', items);
//}

}

LR(0) 文法判别器 - C# 实现

原文地址: https://www.cveoy.top/t/topic/fZDH 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录