Access Restriction

Author LaLonde, Wilf R.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Parsing ♦ Regular expressions ♦ Language generation ♦ Scanners ♦ Formal definition ♦ Finite state machines (automata) ♦ Translators ♦ Parser construction ♦ Syntax diagrams ♦ Lr(k) grammars ♦ Programming languages ♦ Compilers
Abstract This paper introduces an alternative to context-free grammars called regular right part (RRP) grammars, which resemble PASCAL syntax diagrams. Formally, RRP grammars have production right parts, which are nondeterministic finite state machines (FSMs), and, as a special case, regular expression, since these can be converted to FSMs. RRP grammars describe the syntax of programming languages more concisely and more understandably than is possible with CF grammars. Also introduced is a class of parsers, RRP LR(m, k) parsers, which includes the CF LR(k) parsers and provides the same advantages. Informally, an RRP LR(m, k) parser can determine the right end of each handle by considering at most k symbols to the right of the handle and the left end, after the right end has been found, by considering at most m symbols to the left of the handle. A mechanism for determining the left end is required because there is no bound on the length of the handle.
Description Affiliation: Carleton Univ., Ottawa, Ont., Canada (LaLonde, Wilf R.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 20
Issue Number 10
Page Count 11
Starting Page 731
Ending Page 741

Open content in new tab

   Open content in new tab
Source: ACM Digital Library