LL vs LR parsing

Path	csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!news.misty.com!news.iecc.com!.POSTED!nerds-end
From	"SLK Mail" <slkpg4@gmail.com>
Newsgroups	comp.compilers
Subject	LL vs LR parsing
Date	Sat, 26 Jul 2014 16:23:03 -0700
Organization	SLK Systems
Lines	13
Sender	news@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<14-07-061@comp.compilers> (permalink)
NNTP-Posting-Host	news.iecc.com
Mime-Version	1.0
Content-Type	text/plain; charset=iso-8859-15; format=flowed; delsp=yes
Content-Transfer-Encoding	8bit
X-Trace	miucha.iecc.com 1406409133 89409 2001:470:1f07:1126:0:676f:7373:6970 (26 Jul 2014 21:12:13 GMT)
X-Complaints-To	abuse@iecc.com
NNTP-Posting-Date	Sat, 26 Jul 2014 21:12:13 +0000 (UTC)
Keywords	parse, tools
Posted-Date	26 Jul 2014 17:12:13 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:1351

Show key headers only | View raw

It does seem odd that all LR grammars can be made LR(1), but not the case
with LL. Intuitively, it may be that the constructive vs predictive nature
of the two is the cause. In LR, you only know what you have after you have
found it. In LL, you must predict what you think you have based on the
lookahead. So more lookahead equals more predictive power.

SLK now can generate LR(k) parsers in addition to LL(k). Parsing geeks may
be interested to know that the lookahead algorithm is the same for both.
This is because at any point in a parse, the lookahead is independent of
the direction of parse tree construction, i.e. up or down.

http://slkpg.1eko.com

Back to comp.compilers | Previous | Next | Find similar | Unroll thread

Thread

LL vs LR parsing "SLK Mail" <slkpg4@gmail.com> - 2014-07-26 16:23 -0700

csiph-web