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

Lawrence A. Harris

doi:10.1007/BF00264364

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

Lawrence A. Harris

Mathematics

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

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 language	English
Pages (from-to)	191-209
Number of pages	19
Journal	Acta Informatica
Volume	24
Issue number	2
DOIs	https://doi.org/10.1007/BF00264364
State	Published - Apr 1987

ASJC Scopus subject areas

Software
Information Systems
Computer Networks and Communications

Access to Document

10.1007/BF00264364

Cite this

@article{808aaa0be93c4a4e9c9bc611d8ea30cc,

title = "SLR(1) and LALR(1) parsing for unrestricted grammars",

abstract = "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.",

author = "Harris, {Lawrence A.}",

year = "1987",

month = apr,

doi = "10.1007/BF00264364",

language = "English",

volume = "24",

pages = "191--209",

number = "2",

}

TY - JOUR

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

AU - Harris, Lawrence A.

PY - 1987/4

Y1 - 1987/4

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0023328503&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023328503&partnerID=8YFLogxK

U2 - 10.1007/BF00264364

DO - 10.1007/BF00264364

M3 - Article

AN - SCOPUS:0023328503

SN - 0001-5903

VL - 24

SP - 191

EP - 209

JO - Acta Informatica

JF - Acta Informatica

IS - 2

ER -

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

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this