Re: coupling LALR with a scanner?

Paul B Mann <paul@paulbmann.com>
Mon, 19 Sep 2011 12:12:40 -0700 (PDT)

          From comp.compilers

Related articles
[3 earlier articles]
Re: coupling LALR with a scanner? uu3kw29sb7@snkmail.com (Karsten Nyblad) (2011-07-08)
Re: coupling LALR with a scanner? armelasselin@hotmail.com (Armel) (2011-08-04)
Re: coupling LALR with a scanner? paul@paulbmann.com (Paul B Mann) (2011-09-13)
Re: coupling LALR with a scanner? armelasselin@hotmail.com (Armel) (2011-09-16)
Re: coupling LALR with a scanner? paul@paulbmann.com (Paul B Mann) (2011-09-17)
Re: coupling LALR with a scanner? armelasselin@hotmail.com (Armel) (2011-09-19)
Re: coupling LALR with a scanner? paul@paulbmann.com (Paul B Mann) (2011-09-19)
Re: coupling LALR with a scanner? armelasselin@hotmail.com (Armel) (2011-09-20)
Re: coupling LALR with a scanner? cdodd@acm.org (Chris Dodd) (2011-09-23)
Re: coupling LALR with a scanner? cfc@shell01.TheWorld.com (Chris F Clark) (2011-09-29)
Re: coupling LALR with a scanner? armelasselin@hotmail.com (Armel) (2011-10-02)
Re: coupling LALR with a scanner? cfc@shell01.TheWorld.com (Chris F Clark) (2011-10-03)
Re: coupling LALR with a scanner? gah@ugcs.caltech.edu (glen herrmannsfeldt) (2011-10-03)
| List of all articles for this month |

From: Paul B Mann <paul@paulbmann.com>
Newsgroups: comp.compilers
Date: Mon, 19 Sep 2011 12:12:40 -0700 (PDT)
Organization: Compilers Central
References: 11-07-013 11-07-015 11-07-018 11-08-004 11-09-016 11-09-017
Keywords: parse
Posted-Date: 19 Sep 2011 15:29:17 EDT

> IELR was exactly made for that reason, as a first step to PSLR: some
> grammars have no 'tokens' and 'grammar rules', they just have a
> 'grammar' where mutually exclusive tokens are present, e.g. you
> cannot make a Javascript single lexer as there are state where /
> (slash) means 'start of regular expression' (of course the content
> of the regular expression follows totally different lexing rules
> than the rest of the text) whereas in other states it means
> 'division' operator. If your parser cannot tell which of the two
> lexers to use, you are off.


IELR(1) does not solve this problem. It solves the problem of reduce-
reduce conflicts in an LR(0) state machine where a state has multiple
"lookback nonterminal transitions" which cause conflicts. IELR(1)
does state splitting (or duplicating) in order to remove the conflicts
(if possible). It has nothing to do with how many scanners you may
need. It only pertains to the language defined by the grammar. It
looks like you have two languages or two lexical languages (and need
two scanners).


To show that IELR(1) solves this problem you would have to have an
LALR(1) grammar that has reduce-reduce conflicts caused by the need of
two different lexers (scanners) and show that IELR(1) removes the
conflicts.


What you described with Javascript is a little language inside of
another language. Why not switch parsers when a slash ('/') is
encountered if necessary?


Parsing expression grammars are more appropriate for this Javascript
problem, if you don't want to hand-code a "fix" within an LALR parser.


A similar situation occurs when parsing C. You encounter a "#if ..."
while parsing C. At the '#' you must leave the C parser and enter the
C- preprocessor parser. After the conditional statement has been
parsed, you must switch back to the C parser.


/ Paul Mann



Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.