Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #746

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

Show all headers | 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