SLR(1) and LALR(1) parsing for unrestricted grammars
type: Item
instance of: scholarly article
title: SLR(1) and LALR(1) parsing for unrestricted grammars
zbMATH Open document ID: 0634.68080
DOI: 10.1007/BF00264364
author: Lawrence A. Harris
published in: Acta Informatica
publication date: 1987-01-01T00:00:00Z
review text: The paper extends the SLR(1) and LALR(1) methods of deterministic parsing to unrestricted grammars (Chomsky type 0 grammars). In this aim, SLR(1) and LALR(1) phrase structure grammars are defined and corresponding deterministic two-pushdown automata are introduced in a similar manner with the context-free grammars case. Unfortunately, there is no algorithm which produces the SLR(1) or LALR(1) parse table for a given unrestricted grammar. However, the author presents a technique for parse table constructing. It can be applied in many cases as the chosen examples for several well-known non context-free languages show. The method could be also useful for converting LALR(k) grammars to equivalent unrestricted SLR(1) or LALR(1) grammars which could then be parsed efficiently.
reviewed by: L.-D.Şerbănaţi
Mathematics Subject Classification ID: 68N20
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 4033119
zbMATH Keywords: SLR(1) parsing
zbMATH Keywords: LALR(1) automaton
zbMATH Keywords: SLR(1) automaton
zbMATH Keywords: LALR(1) parsing
zbMATH Keywords: unrestricted grammars
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/bf00264364
OpenAlex ID: W1993575201
description: scientific article; zbMATH DE number 4033119