CFG Parsing: Difference between revisions

Revision as of 13:04, 15 February 2023

Given a grammar $G$ and a string $s$, find the parse structure, or analysis, assigned to the string $s$ by the grammar $G$.

n: length of the given string

Name	Year	Time	Space	Approximation Factor	Model	Reference
Earley parser	1968	$O(n^{3})$	$O(n^{2})$	Exact	Deterministic	Time & Space
GLR parser	1974	$O(n^{3})$	$O(n^{3})$	Exact	Deterministic	Time & Space

Error creating thumbnail: Unable to save thumbnail to destination

Error creating thumbnail: Unable to save thumbnail to destination

Error creating thumbnail: Unable to save thumbnail to destination

Problem	Implication	Year	Citation	Reduction
BMM	if: to-time: $O(n^{3-\epsilon})$ for some $\epsilon > {0}$ where $n \times n$ matrix then: from-time: $O(gn^{3-\epsilon})$ where $g$ is the size of the CFG	1975	https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/pii/S0022000075800468	link

Problem	Implication	Year	Citation	Reduction
BMM	if: to-time: $O(gn^{3-\epsilon})$ for some $\epsilon > {0}$ where $g$ is the size of the CFG and $n$ is the size of the string then: from-time: $O(n^{3-\epsilon/3})$ where $n \times n$ matrix	2002	https://arxiv.org/abs/cs/0112018	link

@@ Line 26: / Line 26: @@
 |}
-== Time Complexity graph ==
+== Time Complexity Graph ==
 [[File:CFG Problems - CFG Parsing - Time.png|1000px]]
-== Space Complexity graph ==
+== Space Complexity Graph ==
 [[File:CFG Problems - CFG Parsing - Space.png|1000px]]
-== Pareto Decades graph ==
+== Pareto Frontier Improvements Graph ==
 [[File:CFG Problems - CFG Parsing - Pareto Frontier.png|1000px]]