14
$\begingroup$

I try to teach myself the usage of bison. The manpage bison(1) says about bison:

Generate a deterministic LR or generalized LR (GLR) parser employing LALR(1), IELR(1), or canonical LR(1) parser tables.

What is an IELR-parser? All relevant articles I found on the world wide web are paywalled.

$\endgroup$
  • 5
    $\begingroup$ Including cs.clemson.edu/~malloy/papers/sac08/paper.pdf ? $\endgroup$ – reinierpost Sep 7 '12 at 17:56
  • $\begingroup$ @reinierpost I feel so stupid right now. Why didn't I find this? $\endgroup$ – FUZxxl Sep 7 '12 at 18:59
  • $\begingroup$ I don't know - Google does personalize results ... $\endgroup$ – reinierpost Sep 10 '12 at 7:43
  • $\begingroup$ @reinierpost, would you like to answer this question by quoting your link, so as to clean this question up? $\endgroup$ – Merbs Nov 27 '12 at 7:26
  • $\begingroup$ Hmmm ... if that's all it takes, OK. $\endgroup$ – reinierpost Dec 5 '12 at 10:39
3
$\begingroup$

The IELR(1) Parsing Algorithm

The IELR(1) parsing algorithm was developed in 2008 by Joel E. Denny as part of his Ph.D. research under the supervision of Brian A. Malloy at Clemson University. The IELR(1) algorithm is a variation of the so-called "minimal" LR(1) algorithm developed by David Pager in 1977, which itself is a variation of the LR(k) parsing algorithm invented by Donald Knuth in 1965. The IE in IELR(1) stands for inadequacy elimination (see last section).

LR(1) Algorithms

The LR(1) part of IELR(1) stands for Left to right, Rightmost derivation with 1 lookahead token. LR(1) parsers are also called canonical parsers. This class of parsing algorithms employs a bottom-up, shift-reduce parsing strategy with a stack and state transition table determining the next action to take during parsing.

Historically, LR(1) algorithms have been disadvantaged by large memory requirements for their transition tables. Pager's improvement was to develop a method of combining the transition states when the transition table is generated, significantly reducing the size of the table. Thus Pager's algorithm makes LR(1) parsers competitive with other parsing strategies with respect to space and time efficiency. The phrase "minimal LR(1) parser" refers to the minimal size of the transition table introduced by Pager's algorithm.

Limitations of Pager's Algorithm

Minimal LR(1) algorithms produce the transition table based on a particular input grammar for the language to be parsed. Different grammars can produce the same language. Indeed, it is possible for a non-LR(1) grammar to produce an LR(1) parsable language. In practice, LR(1) parser generators accept non-LR(1) grammars with a specification for resolving conflicts between two possible state transitions ("shift-reduce conflicts") to accommodate this fact. Denny and Malloy found that Pager's algorithm fails to generate parsers powerful enough to parse LR(1) languages when provided certain non-LR(1) grammars even though the non-LR(1) grammar generates an LR(1) language.

Denny and Malloy show that this limitation is not merely academic by demonstrating that Gawk and Gpic, both widely used, mature software, perform incorrect parser actions.

IELR(1)'s Improvements

Denny and Malloy studied the source of the deficiencies of Pager's algorithm by comparing the transition table generated by Pager's algorithm to the transition table of an equivalent LR(1) grammar and identified two sources of what they term inadequacies that appear in the transition table from Pager's algorithm but not in the LR(1) transition table. Denny and Malloy's IELR(1) (Inadequacy Elimination LR(1)) algorithm is an algorithm designed to eliminate these inadequacies when generating the transition table that is virtually identical in size to that of Pager's algorithm.

$\endgroup$
6
$\begingroup$

An article that claims to introduce it: IELR(1): Practical LR(1) Parser Tables for Non-LR(1) Grammars with Conflict Resolution by Joel E. Denny and Brian A. Malloy, Clemson University, is freely available from Malloy's site.

What they are worth is something I can't answer. (Personally I don't understand the need for such crippled CFG parsing - why limit your expressive power when you can just use GLR? What does make sense to me is something like TAG or PEG (they seem natural and add expressive power) or tree grammars (for languages such as XML, in which recognizing parse trees is unproblematic by design.)

$\endgroup$
  • $\begingroup$ While I do agree on principle regarding technology, the problem is often that traditional deterministic parsing has better, more complete implementations. Another issue is that General CF parsing is more powerful, but GLR may not be the best version of it. $\endgroup$ – babou Dec 10 '14 at 12:27
  • 4
    $\begingroup$ The main reason for why people have developed hobbled CFG parsers is that a GLR parser does not necessarily run in linear time—this is a huge problem for many applications. An IELR parser can guarantee linear runtime and more. $\endgroup$ – FUZxxl Oct 1 '15 at 18:58
  • $\begingroup$ I don't understand why it would be a problem. $\endgroup$ – reinierpost Oct 1 '15 at 20:37
  • 2
    $\begingroup$ @reinierpost It's linear time vs. worst-case-$O(n^4)$ (GLR) or $O(n^3)$ (GLL). For e.g. compiling large source files, this can add up lots of time. Furthermore, the attitude of preferring expressiveness over constraint without support neglects the time sacrifice involved. Technically we could use the super-expressive sLMG and/or PMCFG formalisms but then we'd be dealing with up to $lim_{x\rightarrow\infty} O(n^x)$. That might be an absurd example, but the motivation is always time. Humans don't live forever and have a lot to do. Wasting their time is generally bad. $\endgroup$ – user Oct 10 '15 at 9:24
  • 3
    $\begingroup$ I would like to note that "Personally I don't understand the need for such crippled CFG parsing - why limit your expressive power when you can just use GLR?" is rather misguided in this context. IELR(1) is used to generate more efficient LR(1) parser tables, which allows for more efficient GLR parsers. $\endgroup$ – orlp Jan 1 '16 at 9:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.