LR(0) 文法分析器：项目族构建与分析

private List productions = new List(); // 存储文法产生式 private List symbols = new List(); // 存储文法符号 private List states = new List(); // 存储状态 private List itemsets = new List(); // 存储项目族 private Dictionary<string, List> gotoTable = new Dictionary<string, List>(); // 存储GOTO表 private Dictionary<string, List> actionTable = new Dictionary<string, List>(); // 存储ACTION表 private void button2_Click(object sender, EventArgs e)//判别LR0文法 { // 读取文法产生式 string[] productionsArr = richTextBox1.Text.Split(new string[] { "\r\n" }, StringSplitOptions.RemoveEmptyEntries); productions.AddRange(productionsArr);

// 获取文法符号
foreach (string production in productions)
{
    string[] parts = production.Split(' ');
    foreach (string part in parts)
    {
        if (!symbols.Contains(part))
        {
            symbols.Add(part);
        }
    }
}

// 初始化状态0
string item = "S' -> .S";
itemsets.Add(item);
states.Add(GetClosure(item));


BuilditemFamily();

}

private void button4_Click(object sender, EventArgs e)//生成项目族信息 { BuilditemFamily(); // 显示状态和项目族信息 dataGridView1.Columns.Clear(); dataGridView1.Columns.Add("State", "状态"); dataGridView1.Columns.Add("ItemSet", "项目族信息"); dataGridView1.DataSource = itemsets.Select((x, i) => new { State = i, ItemSet = x }).ToList(); dataGridView1.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.AllCells; } private void BuilditemFamily() { int i = 0; while (i < itemsets.Count) { string itemset = itemsets[i]; i++;

    // 获取该项目集的所有可移进符号
    List<string> shiftSymbols = GetShiftSymbols(itemset);
    foreach (string symbol in shiftSymbols)
    {
        // 计算移进后的项目集
        string newItemset = GetShiftItemset(itemset, symbol);
        if (!itemsets.Contains(newItemset))
        {
            itemsets.Add(newItemset);
            System.Diagnostics.Debug.WriteLine(newItemset);
            states.Add(GetClosure(newItemset));
        }

        // 添加GOTO表项
        int fromState = itemsets.IndexOf(itemset);
        int toState = itemsets.IndexOf(newItemset);
        string key = fromState + "," + symbol;
        string value = "S" + toState;
        if (!gotoTable.ContainsKey(key))
        {
            gotoTable[key] = new List<string>();
        }
        gotoTable[key].Add(value);
    }

    // 获取该项目集的所有规约符号
    List<string> reduceSymbols = GetReduceSymbols(itemset);
    foreach (string symbol in reduceSymbols)
    {
        // 添加ACTION表项
        int state = itemsets.IndexOf(itemset);
        string key = state + "," + symbol;
        string value = "r" + GetReduceProductionIndex(itemset, symbol);
        if (!actionTable.ContainsKey(key))
        {
            actionTable[key] = new List<string>();
        }
        actionTable[key].Add(value);
    }
}

}

// 获取闭包 private string GetClosure(string item) { List closure = new List(); closure.Add(item);

int i = 0;
while (i < closure.Count)
{
    string item1 = closure[i];
    i++;

    string[] parts = item1.Split(' ');
    int dotIndex = parts.ToList().IndexOf(".");
    if (dotIndex != parts.Length - 1) // 不是最后一个符号
    {
        string nextSymbol = parts[dotIndex + 1];
        List<string> productionsWithNextSymbol = productions.Where(p => p.StartsWith(nextSymbol + " ")).ToList();
        foreach (string production in productionsWithNextSymbol)
        {
            string newItem = nextSymbol + " -> ." + production.Split(new string[] { nextSymbol + " " }, StringSplitOptions.None)[1];
            if (!closure.Contains(newItem))
            {
                closure.Add(newItem);
            }
        }
    }
}

return string.Join("\r\n", closure);

}

// 获取该项目集的所有可移进符号 private List GetShiftSymbols(string itemset) { List shiftSymbols = new List();

string[] items = itemset.Split(new string[] { "\r\n" }, StringSplitOptions.RemoveEmptyEntries);
foreach (string item in items)
{
    string[] parts = item.Split(' ');
    int dotIndex = parts.ToList().IndexOf(".");
    if (dotIndex != parts.Length - 1) // 不是最后一个符号
    {
        string nextSymbol = parts[dotIndex + 1];
        if (!shiftSymbols.Contains(nextSymbol))
        {
            shiftSymbols.Add(nextSymbol);
        }
    }
}

return shiftSymbols;

}

// 计算移进后的项目集 private string GetShiftItemset(string itemset, string symbol) { List newItems = new List();

string[] items = itemset.Split(new string[] { "\r\n" }, StringSplitOptions.RemoveEmptyEntries);
foreach (string item in items)
{
    string[] parts = item.Split(' ');
    int dotIndex = parts.ToList().IndexOf(".");
    if (dotIndex != parts.Length - 1) // 不是最后一个符号
    {
        string nextSymbol = parts[dotIndex + 1];
        if (nextSymbol == symbol)
        {
            string newItem = string.Join(" ", parts.Take(dotIndex)) + " " + nextSymbol + " ." + string.Join(" ", parts.Skip(dotIndex + 2));
            newItems.Add(newItem);
        }
    }
}

return string.Join("\r\n", newItems);

}

// 获取该项目集的所有规约符号 private List GetReduceSymbols(string itemset) { List reduceSymbols = new List();

string[] items = itemset.Split(new string[] { "\r\n" }, StringSplitOptions.RemoveEmptyEntries);
foreach (string item in items)
{
    string[] parts = item.Split(' ');
    int dotIndex = parts.ToList().IndexOf(".");
    if (dotIndex == parts.Length - 1) // 是最后一个符号
    {
        string reduceSymbol = parts[0];
        if (!reduceSymbols.Contains(reduceSymbol))
        {
            reduceSymbols.Add(reduceSymbol);
        }
    }
}

return reduceSymbols;

}

// 获取规约产生式在文法产生式列表中的索引 private int GetReduceProductionIndex(string itemset, string symbol) { string[] items = itemset.Split(new string[] { "\r\n" }, StringSplitOptions.RemoveEmptyEntries); foreach (string item in items) { string[] parts = item.Split(' '); int dotIndex = parts.ToList().IndexOf("."); if (dotIndex == parts.Length - 1) // 是最后一个符号 { string reduceSymbol = parts[0]; if (reduceSymbol == symbol) { return productions.IndexOf(string.Join(" ", parts.Take(dotIndex))); } } }

return -1;