Re: How change grammar to equivalent LL(1) ?

Path	csiph.com!3.us.feeder.erje.net!feeder.erje.net!news.snarked.org!border2.nntp.dca1.giganews.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From	Hans-Peter Diettrich <DrDiettrich1@netscape.net>
Newsgroups	comp.compilers
Subject	Re: How change grammar to equivalent LL(1) ?
Date	Mon, 23 Dec 2019 10:01:06 +0100
Organization	Compilers Central
Lines	26
Sender	news@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<19-12-025@comp.compilers> (permalink)
References	<19-12-019@comp.compilers>
Mime-Version	1.0
Content-Type	text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding	8bit
Injection-Info	gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="59733"; mail-complaints-to="abuse@iecc.com"
Keywords	parse, LL(1)
Posted-Date	23 Dec 2019 21:53:54 EST
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:2406

Show key headers only | View raw

Am 23.12.2019 um 00:55 schrieb Andy:
> Obviously if is possible.
> In Polish Wikipedia can we read, that even very simple grammar:
> expr->number '+' expr
> expr->number
> is not LL(1) bacause we must see '+' to distinguish
>
> But
> is posssible equivalent grammar:
> expr -> number optPlusExpr
> optPlusExpr -> epsilon
> optPlusExpr ->'+' expr
>
> What are general rules to change grammar to equivalent LL(1) grammar if possible?

Use EBNF:
   expr -> number { '+' expr }
or
   expr -> number { '+' number }

EBNF or "railroad diagrams" typically translate directly into LL
top-down parsers. Many problems vanish when the grammar does not allow
for too much freedom causing inobvious problems. E.g. in EBNF only a
single derivation of a (left hand) nonterminal is allowed.

DoDi

Back to comp.compilers | Previous | Next — Previous in thread | Find similar

Thread

How change grammar to equivalent LL(1) ? Andy <borucki.andrzej@gmail.com> - 2019-12-22 15:55 -0800
  Re: How change grammar to equivalent LL(1) ? Lasse Hillerøe Petersen <lhp+news@toft-hp.dk> - 2019-12-23 03:17 +0000
  Re: How change grammar to equivalent LL(1) ? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-12-23 10:01 +0100

csiph-web