Syntaxis.jar; a new LALR(1) Builder.

Path	csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!news.misty.com!news.iecc.com!.POSTED!nerds-end
From	Evangelos Drikos <drikosev@otenet.gr>
Newsgroups	comp.compilers
Subject	Syntaxis.jar; a new LALR(1) Builder.
Date	Mon, 10 Sep 2012 01:27:33 +0300
Organization	An OTEnet S.A. customer
Lines	57
Sender	johnl@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<12-09-010@comp.compilers> (permalink)
NNTP-Posting-Host	news.iecc.com
Mime-Version	1.0
Content-Type	text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding	7bit
X-Trace	leila.iecc.com 1347285559 43010 64.57.183.58 (10 Sep 2012 13:59:19 GMT)
X-Complaints-To	abuse@iecc.com
NNTP-Posting-Date	Mon, 10 Sep 2012 13:59:19 +0000 (UTC)
Keywords	tools, LALR, available
Posted-Date	10 Sep 2012 09:59:18 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:746

Show key headers only | View raw

Hello,

This message describes a new LALR(1) Builder, identified as LALR' in
the application menu of the parser/scanner generator "Syntaxis.jar".

The new builder implements partially the first phase of Pager's
lane-tracing algorithm [2]; It stores only the kernel items (nucleus)
for each state generated but it doesn't utilize yet internal
connecting lanes to propagate context [1]. It supports the following
options:

a) Reduce & Move Simultaneously Conflicting Productions.
b) Shift Simultaneously Conflicting Tokens.
c) Eliminate Reductions by Single Productions.
d) ...

This first option activates a method that resolves a reduce/reduce
conflict if the productions involved in the conflict have equal number
of symbols and do not have different semantic actions; even if the
grammar is non LR(k).

The implementation of the method described above is experimental. I've
tested it with a subset of the FORTRAN grammar, restricted to free
source form (N1830.pdf). It resolved many conflicts; too many remain.
Nevertheless, the generated parser can parse the following fragment:

>program test
>!...
>if ( f(a,b,c=0))="assignment-stmt"
>if ( f(a,b,c)) e="if-stmt"
>!...
>end program test

The second option activates a method that prevents parse table
explosion if the grammar has a large number of unreserved keywords. It
can be used only in conjunction with a scanner generated by this tool.
The grammar must have clear token boundaries [3].

The third option activates a method that eliminates unit reductions in
order to improve the performance of the generated parser. Sometimes it
increases the parsing table; it depends on the grammar. In such a case,
one can always rephrase some grammar rules (e.g. an expr).

Constructive feedback is welcome. The program "SyntaxisDemo.jar" is
available for evaluation on request.

Regards,
Ev. Drikos

REFERENCES
[1] David Pager. A practical general method for constructing LR(k)
parsers. Acta Informatica, 7:249 - 268, 1977.
[2] David Pager, Xin Chen. "The Lane Table Method Of Constructing LR(1)
Parsers". The First Asia-Pacific Programming Languages and Compilers
Workshop (APPLC) Beijing, China, June 14, 2012
[3] Schrodinger's Token. John Aycock and R. Nigel Horspool. Softw.
Pract. Exper. 2001; 31:803-804 (DOI 10:2002/spe. 390)

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

Thread

Syntaxis.jar; a new LALR(1) Builder. Evangelos Drikos <drikosev@otenet.gr> - 2012-09-10 01:27 +0300

csiph-web