On Mon, 27 Aug 2001, Robin Lee Powell wrote:
On Mon, Aug 27, 2001 at 04:38:44PM -0400, Rob Speer wrote:
On Mon, Aug 27, 2001 at 11:17:55AM -0600, Jay Kominek wrote:
Hrm. A parser with back tracking or more look ahead (or basically any
parser which can parse a larger class of languages) could take the
same
YACC grammar and be able to parse "le broda joi le brode"
correctly... I
think...
So, what is the advantage to having Lojban interpreted by a parser
which can't
backtrack or look ahead more than one word?
All other parsers turn out to be _extremely_ inefficient, IIRC from my
course on such things.
So, basically, it's to make computers happy.
LALR(1) deals in a table on the order of O(n^2), where n is the number
of
productions in the language. (Maybe n is the size of the set of
terminals
_and_ non-terminals. Not really relevent.)
LALR(2) would need a table around O((2*n)^2), IIRC.
Backtracking is a pain, but doesn't make things too much more
inefficient.
The main advantage to using a non-backtracking parser with just one word
of lookahead is that parser generators for such grammars are commonly
available, and easy to implement.
In fact, I don't know that I've ever seen a reference to a C (or C++, or
Java, or Perl) parser generator which is anything _but_ LALR(1).
Most programming languages are LALR(1), so most programming language
courses, or compiler building courses wherein computer science students
are taught how to construct a parser tend to gloss over the details of
all
other classes of parsers.