SLR(1) and LALR(1) parsing for unrestricted grammars

Lawrence A. Harris

Research output: Contribution to journalArticlepeer-review


Simple LR(1) and lookahead LR(1) phrase structure grammars are defined and corresponding deterministic two-pushdown automata which parse all sentences are given. These grammars include a wide variety of grammars for non context-free languages. A given phrase structure grammar is one of these types if the parse table for the associated automaton has no multiple entries. A technique for construction of this parse table is given which in the lookahead case involves elimination of inverses in a grammar for lookahead strings for LR(0) items and computation of first sets for strings of symbols in the given grammar.

Original languageEnglish
Pages (from-to)191-209
Number of pages19
JournalActa Informatica
Issue number2
StatePublished - Apr 1987

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'SLR(1) and LALR(1) parsing for unrestricted grammars'. Together they form a unique fingerprint.

Cite this