Groups | Search | Server Info | Login | Register

Groups > comp.compilers > #266

Re: coupling LALR with a scanner?

Show key headers only | View raw

/* Test1 grammar (like the one above). */

   G -> A <eof>
   A -> a B c
      -> a B d
   B -> b

Test1 grammar is LR(0) and requires NO lookahead symbols.
By default, b always reduces to B.

/* Test2 grammar. */

   G -> A <eof>
   A -> a B1 c
      -> a B2 d
   B1 -> b
   B2 -> b

Test2 grammar is LALR(1) and probably SLR(1) also.  The parser
requires one symbol of lookahead to know which reduction to make (B1
or B2).

/* Test3 grammar. */

   G -> A <eof>
   A -> a B1 c
      -> a B2 d
      -> a B1 d
      -> a B2 c
   B1 -> b
   B2 -> b

Test3 grammar is NOT LALR(1), but it is LR(1).  The parser requires
one symbol of lookahead to know which reduction to make (B1 or B2).

Test3 is a highly contrived situation, not usually seen in real-world
computer languages (as far as I know).  Test3 could be written as
Test2.

It seems that LALR(1) parsers are more powerful than some people
realize.  LR(1) parser tables can be huge.  A COBOL-85 grammar created
an LR(1) parser with over 2,000,000 states, whereas a IELR(1) parser
for that grammar created about 1668 states.  Bison can create IELR(1)
parsers. HYACC can also create IELR(1) parsers.

I don't understand why you want to have a different scanner for each
state.  The parser can easily make the decision, whether a token is
valid.  In fact, an LALR parser already has this information in the
parser tables, so why make a simple situation complicated?

Also in case of a syntax error, the parser can tell the user what
tokens were expected at the error point.  So there is no need for
different lexers, unless the syntax of the tokens changes from one
state to the next and this could be confusing to the the user of your
language.

Paul B Mann

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

Thread

coupling LALR with a scanner? "Armel" <armelasselin@hotmail.com> - 2011-07-05 01:02 +0200
  Re: coupling LALR with a scanner? "Armel" <armelasselin@hotmail.com> - 2011-07-07 10:28 +0200
    coupling LALR with a scanner? "Karsten Nyblad" <uu3kw29sb7@snkmail.com> - 2011-07-07 10:46 +0200
    Re: coupling LALR with a scanner? "Karsten Nyblad" <uu3kw29sb7@snkmail.com> - 2011-07-08 14:39 +0200
      Re: coupling LALR with a scanner? "Armel" <armelasselin@hotmail.com> - 2011-08-04 11:17 +0200
        Re: coupling LALR with a scanner? Paul B Mann <paul@paulbmann.com> - 2011-09-13 13:38 -0700
          Re: coupling LALR with a scanner? "Armel" <armelasselin@hotmail.com> - 2011-09-16 10:47 +0200
            Re: coupling LALR with a scanner? "Armel" <armelasselin@hotmail.com> - 2011-09-19 13:52 +0200
            Re: coupling LALR with a scanner? Paul B Mann <paul@paulbmann.com> - 2011-09-19 12:12 -0700
              Re: coupling LALR with a scanner? "Armel" <armelasselin@hotmail.com> - 2011-09-20 09:40 +0200
                Re: coupling LALR with a scanner? Chris Dodd <cdodd@acm.org> - 2011-09-23 23:59 +0100
                Re: coupling LALR with a scanner? Chris F Clark <cfc@shell01.TheWorld.com> - 2011-09-29 00:00 -0400
                Re: coupling LALR with a scanner? "Armel" <armelasselin@hotmail.com> - 2011-10-02 16:41 +0200
                Re: coupling LALR with a scanner? Chris F Clark <cfc@shell01.TheWorld.com> - 2011-10-03 11:59 -0400
                Re: coupling LALR with a scanner? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2011-10-03 21:08 +0000
          Re: coupling LALR with a scanner? Paul B Mann <paul@paulbmann.com> - 2011-09-17 10:38 -0700

csiph-web