 	}
 }
 
+/// A parser that can parse ambiguous grammars and retrieve every possible syntax tree
+public protocol AmbiguousGrammarParser: Parser {
+	func allSyntaxTrees(for string: String) throws -> [SyntaxTree<NonTerminal, Range<String.Index>>]
+}
 
 /// A parser based on the CYK algorithm.
 ///
 /// The parser can parse non-deterministic and deterministic grammars.
 /// It requires O(n^3) runtime.
-public struct CYKParser: Parser {
+public struct CYKParser: AmbiguousGrammarParser {
 	
 	/// The grammar which the parser recognizes
 	public let grammar: Grammar

			let upperBound = cykTable.count - row
			
			cykTable[row] = (0..<upperBound).map { column -> [SyntaxTree<Production, Range<String.Index>>] in
				(1...row).flatMap { offset -> [SyntaxTree<Production, Range<String.Index>>] in
					let ref1Row = row - offset
					let ref2Col = column + row - offset + 1
					let ref2Row = offset - 1

							return SyntaxTree(key: pattern, children: [leftTree, rightTree])
						}
					}
				}
				if ignoreAmbiguousItems {
					return cell.unique(by: {$0.root!.pattern}).collect(Array.init)
				} else {
					return cell
				}
			}
		}
		
		// If a given word is not a member of the language generated by this grammar
		// an error will be computed that returns the first and largest structure
		// in the syntax tree that the parser was unable to process.
		let syntaxTrees = cykTable[cykTable.count-1][0].filter { tree -> Bool in
			tree.root?.pattern == normalizedGrammar.start
		}
		if syntaxTrees.isEmpty {
			throw generateError(cykTable, string: string)
		}
		return syntaxTrees.map{unfoldChainProductions($0).explode(normalizedGrammar.normalizationNonTerminals.contains)[0]}
	}
	
	public func syntaxTree(for string: String) throws -> SyntaxTree<NonTerminal, Range<String.Index>> {
		return try self.syntaxTree(for: string, ignoreAmbiguousItems: true)[0]
	}
	
	public func allSyntaxTrees(for string: String) throws -> [SyntaxTree<NonTerminal, Range<String.Index>>] {
		return try self.syntaxTree(for: string, ignoreAmbiguousItems: false)
	}
}
