Ambiguous non-terminal in GLR

Path	csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!us.feeder.erje.net!news.linkpendium.com!news.linkpendium.com!news.iecc.com!.POSTED!nerds-end
From	Maxim Reznik <reznikmm@front.ru>
Newsgroups	comp.compilers
Subject	Ambiguous non-terminal in GLR
Date	Mon, 01 Apr 2013 11:16:51 +0300
Organization	Aioe.org NNTP Server
Lines	25
Sender	johnl@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<13-04-002@comp.compilers> (permalink)
NNTP-Posting-Host	news.iecc.com
Mime-Version	1.0
Content-Type	text/plain; charset=UTF-8
Content-Transfer-Encoding	7bit
X-Trace	leila.iecc.com 1364922149 95558 64.57.183.58 (2 Apr 2013 17:02:29 GMT)
X-Complaints-To	abuse@iecc.com
NNTP-Posting-Date	Tue, 2 Apr 2013 17:02:29 +0000 (UTC)
Keywords	parse, question
Posted-Date	02 Apr 2013 13:02:28 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:879

Show key headers only | View raw

Hi, all

I'm playing with GLR and have a question.

When GLR parser reduces some text to the same non-terminal in two or
more ways it merges parse subtrees. Rekers uses 'symbol nodes' for this.

I this not each non-terminal could cause a merge. Knowing in advance
what non-terminals never merge will greatly simplify parse tree
construction.

For instance in Elkhound Technical Report the author implemented C++
grammar for GLR parser. He describes it:

    The grammar currently has 37 shift/reduce conflicts, 47
reduce/reduce conflicts and 8 ambiguous nonterminal.

How can I separate ambiguous and unambiguous nonterminal for a given
CFG? Where can I read about this?


Thank you
--
Maxim Reznik

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

Thread

Ambiguous non-terminal in GLR Maxim Reznik <reznikmm@front.ru> - 2013-04-01 11:16 +0300

csiph-web