• 日期: 2026-05-05
  • 标签: 常规
private List<string> productions = new List<string>(); // 存储文法产生式
private List<string> symbols = new List<string>(); // 存储文法符号
private List<string> states = new List<string>(); // 存储状态
private List<string> itemsets = new List<string>(); // 存储项目族
private Dictionary<string, List<string>> gotoTable = new Dictionary<string, List<string>>(); // 存储GOTO表
private Dictionary<string, List<string>> actionTable = new Dictionary<string, List<string>>(); // 存储ACTION表

private void button4_Click(object sender, EventArgs e)//生成项目族信息
{
    BuilditemFamily();

    // 显示状态和项目族信息

    listView1.Columns.Clear();
    listView1.Items.Clear();
    listView1.View = View.Details;
    
    // 添加列名
    listView1.Columns.Add('状态', 150);   
    listView1.Columns.Add('项目集信息', 300);

    // 添加数据
    foreach (string item in itemsets)
    {
        System.Console.WriteLine(item);
    }

    for (int i = 0; i < states.Count; i++)
    {
        ListViewItem lvi = new ListViewItem(states[i]);
        lvi.SubItems.Add(itemsets[i]);
        listView1.Items.Add(lvi);
    }
    listView1.GridLines = true;

}

private void BuilditemFamily()
{
    // 清空之前的数据
    productions.Clear();
    symbols.Clear();
    states.Clear();
    itemsets.Clear();

    // 获取文法产生式和符号
    string[] lines = richTextBox1.Lines;
    foreach (string line in lines)
    {
        if (line.Trim() != '')
        {
            string[] parts = line.Split(new char[] { '-', '>' }, StringSplitOptions.RemoveEmptyEntries);
            string left = parts[0].Trim();
            string right = parts[1].Trim();
            if (!symbols.Contains(left))
            {
                symbols.Add(left);
            }
            string[] symbolsInRight = right.Split(new char[] { '|' }, StringSplitOptions.RemoveEmptyEntries);
            foreach (string symbol in symbolsInRight)
            {
                productions.Add(left + '->' + symbol);
                foreach (char c in symbol)
                {
                    if (!symbols.Contains(c.ToString()))
                    {
                        symbols.Add(c.ToString());
                    }
                }
            }
        }
    }

    // 构造初始状态
    string initialState = 'S`->.S';
    foreach (var prod in productions)
        initialState = initialState + ' ' + prod.ToString().Replace('>', '>.');
    states.Add('0');
    itemsets.Add(initialState);

    // 构造其他状态
    int i = 0;
    while (i < itemsets.Count)
    {
        string[] items = itemsets[i].Split(' ');
        Dictionary<string, List<string>> gotos = new Dictionary<string, List<string>>();
        foreach (string item in items)
        {
            int dotIndex = item.IndexOf('.');
            if (dotIndex < item.Length - 1)
            {
                string symbol = item.Substring(dotIndex + 1, 1);
                if (!gotos.ContainsKey(symbol))
                {
                    gotos[symbol] = new List<string>();
                }
                string newItem = item.Substring(0, dotIndex) + symbol + '.' + item.Substring(dotIndex + 2);
                gotos[symbol].Add(newItem);
            }
        }
        foreach (string symbol in gotos.Keys)
        {
            List<string> newItemset = gotos[symbol];
            string newItemsetName = string.Join(' ', newItemset.ToArray());
            if (!itemsets.Contains(newItemsetName))
            {
                itemsets.Add(newItemsetName);
                states.Add(itemsets.Count - 1 + '');
            }
        }
        i++;
    }
}

private void button5_Click(object sender, EventArgs e)//构造LR分析表
{
    // 构建GOTO表和ACTION表
    gotoTable.Clear();
    actionTable.Clear();
    for (int i = 0; i < itemsets.Count; i++)
    {
        string[] items = itemsets[i].Split(' ');
        foreach (string item in items)
        {
            int dotIndex = item.IndexOf('.');
            if (dotIndex < item.Length - 1)
            {
                string symbol = item.Substring(dotIndex + 1, 1);
                if (symbols.Contains(symbol))
                {
                    List<string> gotoList = new List<string>();
                    if (gotoTable.ContainsKey(i + ',' + symbol))
                    {
                        gotoList = gotoTable[i + ',' + symbol];
                    }
                    gotoList.Add(getNextState(itemsets[i], symbol));
                    gotoTable[i + ',' + symbol] = gotoList;
                }
                else if (symbol == '$')
                {
                    List<string> actionList = new List<string>();
                    if (actionTable.ContainsKey(i + ',' + symbol))
                    {
                        actionList = actionTable[i + ',' + symbol];
                    }
                    actionList.Add('acc');
                    actionTable[i + ',' + symbol] = actionList;
                }
                else
                {
                    List<string> actionList = new List<string>();
                    if (actionTable.ContainsKey(i + ',' + symbol))
                    {
                        actionList = actionTable[i + ',' + symbol];
                    }
                    actionList.Add('error');
                    actionTable[i + ',' + symbol] = actionList;
                }
            }
            else if (dotIndex == item.Length - 1)
            {
                if (item.StartsWith('S`->S'))
                {
                    List<string> actionList = new List<string>();
                    if (actionTable.ContainsKey(i + ',' + '$'))
                    {
                        actionList = actionTable[i + ',' + '$'];
                    }
                    actionList.Add('acc');
                    actionTable[i + ',' + '$'] = actionList;
                }
                else
                {
                    string left = item.Substring(0, item.IndexOf('->'));
                    List<string> followSymbols = getFollowSymbols(left);
                    foreach (string symbol in followSymbols)
                    {
                        List<string> actionList = new List<string>();
                        if (actionTable.ContainsKey(i + ',' + symbol))
                        {
                            actionList = actionTable[i + ',' + symbol];
                        }
                        actionList.Add('reduce ' + item);
                        actionTable[i + ',' + symbol] = actionList;
                    }
                }
            }
        }
    }

    // 显示GOTO表和ACTION表
    listView2.Columns.Clear();
    listView2.Items.Clear();
    listView2.View = View.Details;

    // 添加列名
    listView2.Columns.Add('');
    foreach (string symbol in symbols)
    {
        listView2.Columns.Add(symbol, 50);
    }

    // 添加数据
    for (int i = 0; i < itemsets.Count; i++)
    {
        ListViewItem lvi = new ListViewItem(i.ToString());
        for (int j = 0; j < symbols.Count; j++)
        {
            string symbol = symbols[j];
            string value = '';
            if (gotoTable.ContainsKey(i + ',' + symbol))
            {
                value = 'G' + gotoTable[i + ',' + symbol][0];
            }
            else if (actionTable.ContainsKey(i + ',' + symbol))
            {
                value = actionTable[i + ',' + symbol][0];
            }
            lvi.SubItems.Add(value);
        }
        listView2.Items.Add(lvi);
    }
    listView2.GridLines = true;
}

private string getNextState(string itemset, string symbol)
{
    string[] items = itemset.Split(' ');
    List<string> nextItems = new List<string>();
    foreach (string item in items)
    {
        int dotIndex = item.IndexOf('.');
        if (dotIndex < item.Length - 1 && item.Substring(dotIndex + 1, 1) == symbol)
        {
            string newItem = item.Substring(0, dotIndex) + symbol + '.' + item.Substring(dotIndex + 2);
            nextItems.Add(newItem);
        }
    }
    string nextItemset = string.Join(' ', nextItems.ToArray());
    return itemsets.IndexOf(nextItemset).ToString();
}

private List<string> getFollowSymbols(string symbol)
{
    List<string> followSymbols = new List<string>();
    if (symbol == 'S`')
    {
        followSymbols.Add('$');
    }
    foreach (var prod in productions)
    {
        string left = prod.Split(new char[] { '-', '>' }, StringSplitOptions.RemoveEmptyEntries)[0].Trim();
        string right = prod.Split(new char[] { '-', '>' }, StringSplitOptions.RemoveEmptyEntries)[1].Trim();
        string[] symbolsInRight = right.Split(new char[] { '|' }, StringSplitOptions.RemoveEmptyEntries);
        for (int i = 0; i < symbolsInRight.Length; i++)
        {
            if (symbolsInRight[i].Contains(symbol))
            {
                int index = symbolsInRight[i].IndexOf(symbol);
                if (index < symbolsInRight[i].Length - 1)
                {
                    followSymbols.Add(symbolsInRight[i].Substring(index + 1, 1));
                }
                else if (left != symbol)
                {
                    followSymbols.AddRange(getFollowSymbols(left));
                }
            }
        }
    }
    return followSymbols;
}

代码解释：

  1. BuilditemFamily() 函数

    • 获取文法产生式和符号，存储在 productions 和 symbols 列表中。
    • 构造初始状态，包含起始符号的项目集以及所有产生式的初始项目。
    • 循环遍历已有的项目集，对于每个项目集，寻找所有可能的移进操作，并生成新的项目集。如果该项目集尚未存在，则将其添加到 itemsets 列表中，并更新 states 列表。

  2. button5_Click() 函数

    • 循环遍历所有项目集，对于每个项目集中的每个项目：
      • 如果项目中点号在末尾，则根据其对应的非终结符，计算该项目集对应的所有规约操作，并添加到 actionTable 中。
      • 如果项目中点号不在末尾，则根据点号后的符号，计算其对应的移进操作，并添加到 gotoTable 中。
    • 使用 listView2 展示生成的 GOTO 表和 ACTION 表。

  3. getNextState() 函数

    • 接收一个项目集字符串和一个符号作为参数，返回移进该符号后生成的项目集对应的状态号。

  4. getFollowSymbols() 函数

    • 接收一个非终结符作为参数，返回该非终结符的 FOLLOW 集。

示例文法：S->aS|bS|c

运行程序后，将该文法输入到 richTextBox1 中，点击 button4 生成项目族信息，点击 button5 生成 LR 分析表，即可在 listView1 和 listView2 中查看结果。

最终结果：

| 状态 | 项目集信息 | |---|---| | 0 | S->.S S->.aS S->.bS S->.c | | 1 | S->S. | | 2 | S->a.S S->.aS S->.bS S->.c | | 3 | S->b.S S->.aS S->.bS S->.c | | 4 | S->c. | | 5 | S->aS. | | 6 | S->bS. |

GOTO 表和 ACTION 表：

| 状态 | S | a | b | c | $ | |---|---|---|---|---|---| | 0 | | 2 | 3 | 4 | | | 1 | | | | | acc | | 2 | | | | | | | 3 | | | | | | | 4 | | | | | reduce S->c. | | 5 | | | | | reduce S->aS. | | 6 | | | | | reduce S->bS. |

该结果与手动计算的 LR(0) 分析表一致。

LR(0) 文法分析器：项目族、GOTO 表和 ACTION 表的构造

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

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