yyl-20020115/CYKAlgorithm

CYKAlgorithm in C#

CYKAlgorithm in C#

by Yilin Yang

public static partial class CYK
{
	public static List<CYKNode> Parse(string[] Input, List<CNFProduction> Productions)
	{
		List<CYKNode> Finals = new List<CYKNode>();
		if ((Input != null && Input.Length > 0) && Productions != null && Productions.Count > 0)
		{
			int InputLength = Input.Length;

			List<CYKNode>[,] Matrix = new List<CYKNode>[InputLength, InputLength];

			for (int row = 0; row < InputLength; row++)
			{
				for (int column = 0; column < InputLength; column++)
				{
					Matrix[row, column] = new List<CYKNode>();

					if (row == 0)
					{
						Matrix[row, column].AddRange(
							CYKNode.ToNodes(
							from p in Productions
							where p.Type == ProductionType.OneTerminal
							&& p.Terminal == Input[column]
							select p)
						);
						if (Matrix[row, column].Count == 0)
						{
							return Finals;
						}
					}
				}
			}

			for (int row = 1; row < InputLength; row++)
			{
				for (int column = 0; column < InputLength - row; column++)
				{
					// {Xi1,Xj1} U {Xi2,Xj2} == Xi1Xi2 Xi1Xj2 Xj1Xi2 Xj1Xj2
					int i1 = row - 1;
					int j1 = column;

					int i2 = 0;
					int j2 = row + column;

					for (int cx = 0; cx < row; cx++)
					{
						List<CYKNode> B = Matrix[i1, j1];
						List<CYKNode> C = Matrix[i2, j2];
						List<CYKNode> M = Matrix[row, column];

						M.AddRange(
							from b in B
							from c in C
							from p in Productions
							where
							p.Type == ProductionType.TwoNonterminals
							&& p.Head == b.Target
							&& p.Tail == c.Target
							select new CYKNode(p, b, c)
							);

						i1--;
						i2++;
						j2--;
					}
				}
			}

			Finals = Matrix[InputLength - 1, 0];
			if (!Finals
				.Any(node => node.Production == Productions[0]))
			{
				Finals.Clear();
			}
		}
		return Finals;
	}


}