private void BuilditemFamily()
{
    // 初始化
    productions = richTextBox1.Lines.ToList();
    productions.RemoveAll(x => x == ''); // 去除空行
    symbols = GetSymbols(productions);
    states.Clear();
    itemsets.Clear();

    // 生成初始项目集
    List<string> initialItemset = new List<string>();
    initialItemset.Add($'{productions[0].Split(' ')[0]}->{productions[0].Split(' ')[1]}.'); // 第一个产生式的初始项目
    HashSet<string> closure = GetClosure(initialItemset);
    states.Add('I0');
    itemsets.Add(string.Join('\n', closure));

    // 构建项目集族
    int curStateIndex = 0;
    while (curStateIndex < states.Count)
    {
        string curState = states[curStateIndex];
        HashSet<Item> curItemSet = GetItemSet(itemsets[curStateIndex]);
        Dictionary<string, HashSet<Item>> goToDict = GetGoToDict(curItemSet);
        foreach (string symbol in symbols)
        {
            if (goToDict.ContainsKey(symbol))
            {
                HashSet<Item> goToItemSet = goToDict[symbol];
                string goToItemSetStr = string.Join('\n', goToItemSet);
                if (!states.Contains(goToItemSetStr))
                {
                    states.Add(goToItemSetStr);
                    itemsets.Add(goToItemSetStr);
                }
            }
        }
        curStateIndex++;
    }
}

// 获取文法符号集合
private List<string> GetSymbols(List<string> productions)
{
    List<string> symbols = new List<string>();
    foreach (string production in productions)
    {
        string[] productionArr = production.Split(' ');
        foreach (string symbol in productionArr)
        {
            if (!symbols.Contains(symbol))
            {
                symbols.Add(symbol);
            }
        }
    }
    symbols.Remove('->'); // 去除产生式符号
    return symbols;
}

// 获取项目集的闭包
private HashSet<string> GetClosure(List<string> itemset)
{
    HashSet<Item> closureItemSet = new HashSet<Item>();
    foreach (string item in itemset)
    {
        string[] itemArr = item.Split('.');
        string lhs = itemArr[0];
        string[] rhsArr = itemArr[1].Split(' ');
        int dotIndex = itemArr[1].IndexOf('.') + 1;
        HashSet<string> lookahead = new HashSet<string>();
        if (dotIndex < itemArr[1].Length)
        {
            lookahead = GetFirst(itemArr[1].Substring(dotIndex));
        }
        Item closureItem = new Item(lhs, rhsArr.ToList(), dotIndex);
        closureItemSet.Add(closureItem);
        foreach (string production in productions)
        {
            if (production.StartsWith(lhs))
            {
                string[] productionArr = production.Split(' ');
                Item newItem = new Item(lhs, productionArr.ToList().GetRange(1, productionArr.Length - 1), 0);
                if (!closureItemSet.Contains(newItem))
                {
                    foreach (string lookaheadSymbol in lookahead)
                    {
                        newItem.RHS.Add(lookaheadSymbol);
                        closureItemSet.Add(newItem);
                        newItem.RHS.RemoveAt(newItem.RHS.Count - 1);
                    }
                }
            }
        }
    }
    HashSet<string> closureStrSet = new HashSet<string>();
    foreach (Item closureItem in closureItemSet)
    {
        closureStrSet.Add(closureItem.ToString());
    }
    return closureStrSet;
}

// 获取项目集
private HashSet<Item> GetItemSet(string itemsetStr)
{
    HashSet<Item> itemSet = new HashSet<Item>();
    string[] itemArr = itemsetStr.Split('\n');
    foreach (string item in itemArr)
    {
        string[] itemParts = item.Split('.');
        string lhs = itemParts[0];
        string[] rhsArr = itemParts[1].Split(' ');
        int dotIndex = itemParts[1].IndexOf('.') + 1;
        itemSet.Add(new Item(lhs, rhsArr.ToList(), dotIndex));
    }
    return itemSet;
}

// 获取一个符号的FIRST集
private HashSet<string> GetFirst(string symbol)
{
    HashSet<string> firstSet = new HashSet<string>();
    if (symbol == '') // 空串
    {
        firstSet.Add('');
        return firstSet;
    }
    string firstSymbol = symbol.Split(' ')[0];
    if (IsTerminal(firstSymbol)) // 终结符
    {
        firstSet.Add(firstSymbol);
        return firstSet;
    }
    foreach (string production in productions) // 非终结符
    {
        if (production.StartsWith(firstSymbol))
        {
            string[] productionArr = production.Split(' ');
            if (productionArr.Length == 1) // 产生式为A->空
            {
                if (symbol.Length == firstSymbol.Length) // 第一个符号为A
                {
                    firstSet.Add('');
                }
                else // 第一个符号不为A
                {
                    HashSet<string> nextFirstSet = GetFirst(symbol.Substring(firstSymbol.Length + 1));
                    foreach (string nextFirstSymbol in nextFirstSet)
                    {
                        firstSet.Add(nextFirstSymbol);
                    }
                }
            }
            else // 产生式为A->BCD...
            {
                HashSet<string> nextFirstSet = GetFirst(symbol.Substring(firstSymbol.Length + 1));
                foreach (string nextFirstSymbol in nextFirstSet)
                {
                    firstSet.Add(nextFirstSymbol);
                }
                if (nextFirstSet.Contains('')) // B可以推出空
                {
                    HashSet<string> restFirstSet = GetFirst(symbol.Substring(firstSymbol.Length + 1 + ' '.Length));
                    foreach (string restFirstSymbol in restFirstSet)
                    {
                        firstSet.Add(restFirstSymbol);
                    }
                }
            }
        }
    }
    return firstSet;
}

// 判断一个符号是否为终结符
private bool IsTerminal(string symbol)
{
    foreach (string production in productions)
    {
        if (production.StartsWith(symbol))
        {
            string[] productionArr = production.Split(' ');
            if (productionArr.Length == 1) // 产生式为A->空
            {
                return false;
            }
            else // 产生式为A->BCD...
            {
                for (int i = 1; i < productionArr.Length; i++)
                {
                    if (productionArr[i] == symbol)
                    {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

// 获取所有项集的GOTO函数字典
private Dictionary<string, HashSet<Item>> GetGoToDict(HashSet<Item> itemSet)
{
    Dictionary<string, HashSet<Item>> goToDict = new Dictionary<string, HashSet<Item>>();
    foreach (Item item in itemSet)
    {
        if (item.dotIndex < item.RHS.Count)
        {
            string nextSymbol = item.RHS[item.dotIndex];
            List<string> newRHS = new List<string>(item.RHS);
            newRHS[item.dotIndex] = '.';
            newRHS.Insert(item.dotIndex + 1, nextSymbol);
            HashSet<string> lookahead = new HashSet<string>();
            if (item.dotIndex + 1 < item.RHS.Count)
            {
                lookahead = GetFirst(string.Join(' ', item.RHS.GetRange(item.dotIndex + 1, item.RHS.Count - item.dotIndex - 1)));
            }
            else
            {
                lookahead.Add('$');
            }
            Item newItem = new Item(item.LHS, newRHS, item.dotIndex + 1);
            foreach (string lookaheadSymbol in lookahead)
            {
                newItem.RHS.Add(lookaheadSymbol);
                if (!goToDict.ContainsKey(nextSymbol))
                {
                    goToDict[nextSymbol] = new HashSet<Item>();
                }
                goToDict[nextSymbol].Add(newItem);
                newItem.RHS.RemoveAt(newItem.RHS.Count - 1);
            }
        }
    }
    return goToDict;
}

// 项目类
private class Item
{
    public string LHS { get; set; }
    public List<string> RHS { get; set; }
    public int dotIndex { get; set; }

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

    public override string ToString()
    {
        List<string> tempRHS = new List<string>(RHS);
        tempRHS.Insert(dotIndex, '.');
        return $'{LHS}->{string.Join('', tempRHS)}';
    }
}
LR(0) 文法项目集族构建算法实现

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

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