Path: csiph.com!au2pb.net!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end From: Vladimir Makarov Newsgroups: comp.compilers Subject: Yet Another Earley's Parser (YAEP) Date: Tue, 13 Oct 2015 14:54:36 -0400 Organization: Aioe.org NNTP Server Lines: 30 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <15-10-010@comp.compilers> NNTP-Posting-Host: news.iecc.com Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-Trace: miucha.iecc.com 1444822579 87643 2001:470:1f07:1126:0:676f:7373:6970 (14 Oct 2015 11:36:19 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Wed, 14 Oct 2015 11:36:19 +0000 (UTC) Keywords: parse, tools Posted-Date: 14 Oct 2015 07:36:19 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:1637 A standalone C/C++ library implementing Earley's Parser called YAEP is available now on https://github.com/vnmakarov/yaep Major features of this implementation: o It makes a simple syntax directed translation. o It can make error recovery with minimal number of skipped tokens. o It can parse an input described by ambiguous grammar producing one or all abstract trees in a compact form (DAG). o It can produce minimal cost abstract trees of an input described by ambiguous grammar. o It has two interfaces to describe a grammar through function calls or through providing YACC-like description. o It is pretty fast. It can parse 300K lines of C code per second. Still it is 2.5-6 times slower than YACC (1.6 - 3 times with taking scanner into account). YAEP is actually a further development of Earley's parser in COCOM tool set originally written in 2002. The original version has been sped up to 2 times by implementing new optimizations. Some optimizations are described briefly on https://github.com/vnmakarov/yaep/blob/master/README.md