W3C home > Mailing lists > Public > public-ixml@w3.org > July 2021

Informative references to parsing algorithms

From: Steven Pemberton <steven.pemberton@cwi.nl>
Date: Wed, 07 Jul 2021 10:19:19 +0000
Message-Id: <1625650436913.3692347111.3870978229@cwi.nl>
To: ixml <public-ixml@w3.org>
The spec mentions several suitable parsing algorithms, which I think we should reference nonnormatively. Here are some suggestions. Improvements gratefully received.


Earley
Earley, Jay (1970), "An efficient context-free parsing algorithm", Communications of the ACM, 13 (2): 94–102, doi:10.1145/362007.362035


Unger
Unger, S. H. A global parser for context-free phrase structure grammars. Commun. ACM, 11(4):240–247, April 1968


CYK
Sakai, Itiroo. Syntax in universal translation. In 1961 International Conference on Machine Translation of Languages and Applied Language Analysis, pages 593–608


GLR
Masaru Tomita. Generalized LR Parsing. Springer Science & Business Media. ISBN 978-1-4615-4034-2.


GLL
GLL Parsing Elizabeth Scott and Adrian Johnstone Electronic Notes in Theoretical Computer Science, Volume 253, Issue 7, 17 September 2010, Pages 177-189




Or we could use just one reference to cover them all.
Grune, D. and Jacobs, C. (2008). Parsing techniques : a practical guide (2nd ed.). New York: Springer. p. 579. ISBN 978-0-387-20248-8.
https://dickgrune.com/Books/PTAPG_2nd_Edition/CompleteList.pdf


Steven
Received on Wednesday, 7 July 2021 10:23:49 UTC

This archive was generated by hypermail 2.4.0 : Wednesday, 7 July 2021 10:29:39 UTC