按年被提到
20012016 · 2 次2026
算法与数据结构›经典算法与数据结构·arXiv:cs/0112018 · cs.CL

Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication

Lillian Lee · 2001
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2016-06-25 · 最近 2016-09-15
2不同的人
2活跃月份
2讨论串
123被引(OpenAlex)
arXiv 摘要(候选层不写导读)

In 1975, Valiant showed that Boolean matrix multiplication can be used for parsing context-free grammars (CFGs), yielding the asympotically fastest (although not practical) CFG parsing algorithm known. We prove a dual result: any CFG parser with time complexity $O(g n^{3 - \epsilson})$, where $g$ is the size of the grammar and $n$ is the length of the input string, can be efficiently converted into an algorithm to multiply $m \times m$ Boolean matrices in time $O(m^{3 - ε/3})$. Given that practical, substantially sub-cubic Boolean matrix multiplication algorithms have been quite difficult to find, we thus explain why there has been little progress in developing practical, substantially sub-cubic general CFG parsers. In proving this result, we also develop a formalization of the notion of parsing.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论DannyBee · 2016-06

“It is known that any fast CFG parsing algorithm can be turned into a fast boolean matrix multiplication algorithm. So if CFG parsing was n^2, so is boolean matrix multiplication:) See http://arxiv.org/abs/cs/0112018”

On the Complexity and Performance of Parsing with Derivatives原评论 ↗
评论ulrikrasmussen · 2016-09

“Minor technical nitpick for the README: You're not moving up the Chomsky hierarchy but rather moving sideways;). PEGs are non-Chomskyan parsing formalisms, in the sense that the family of languages describable by PEGs are not to be found in the Chomsky hierarchy. For example, they are not regular, as they can match patterns such as a^n b^n. On the other…”

Show HN: Using Parsing Expression Grammars to rewrite source code原评论 ↗