Consider such a rule in grammar for an LR-family parsing generator (e.g YACC, BISON, etc.):

Nonterminal : [ lookahead not in {Terminal1, ..., TerminalN} ] Rule ;

It's an ordinary rule, except that it has a restriction: a phrase produced with this rule cannot begin with Terminal1, ..., TerminalN. (Surely, this rule can be replaced with a set of usual rules, but it will result in a bigger grammar). This can be useful for resolving conflicts.

The question is, is there a modification of LR table construction algorithm that accepts such restrictions? It seems to me that such a modification is possible (like precedence relations).

Surely, it can be checked in runtime, but I mean compile-time check (a check which is performed while building parsing table, like %prec, %left, %right and %nonassoc directives in yacc-compartible generators.)

  • $\begingroup$ I'm not clear whether this a question about the tools in practice, or the LR parsing strategy in the abstract world. Also, the title mislead me: I thought you wanted like $-5$ symbols lookahead. $\endgroup$
    – Raphael
    Apr 21 '13 at 14:29
  • $\begingroup$ Seems that the phrase "negative lookahead" is common use in regard to regular expressions. The question is about abstract theory, but it would be very useful in real world parsing (e.g., consider ECMA-262 grammar, ecma-international.org/ecma-262/5.1, section 12.4). I would very much appreciate any formal or informal proof or practical experience whether it is possible to implement such restrictions and how to do that. $\endgroup$
    – skvadrik
    Apr 21 '13 at 15:24
  • 1
    $\begingroup$ Okay. You say yourself, "this rule can be replaced with a set of usual rules". What remains to say? $\endgroup$
    – Raphael
    Apr 21 '13 at 15:26
  • $\begingroup$ This fact neither means that negative lookahead in LR parsing is useless, nor that it is possible, so I don't see what you mean. :) $\endgroup$
    – skvadrik
    Apr 21 '13 at 15:49
  • $\begingroup$ You claim yourself that there is a (straight-forward) construction to unfold the "negative lookahead" into regular rules, so a parser-generator can just do that, can't it $\endgroup$
    – Raphael
    Apr 21 '13 at 15:51

Yes, there is such a modification. A negative lookahead assertion at the END of a production means taking special care in computing FOLLOW sets. Before a terminal makes no sense. Before a nonterminal is a bit more complicated: the optimal strategy depends on the context. Special care while generating the shift relationship is part of the answer. On balance, this is an algorithm design problem more than a theoretical computer science problem.


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.