Access Restriction

Author Woods, William A.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Recognition algorithms ♦ Formal grammars ♦ Formal language theory ♦ Parsing ♦ Parsing algorithms ♦ Context-sensitive grammars ♦ Context-sensitive parsing
Abstract This paper presents a canonical form for context-sensitive derivations and a parsing algorithm which finds each context-sensitive analysis once and only once. The amount of memory required by the algorithm is essentially no more than that required to store a single complete derivation. In addition, a modified version of the basic algorithm is presented which blocks infinite analyses for grammars which contain loops. The algorithm is also compared with several previous parsers for context-sensitive grammars and general rewriting systems, and the difference between the two types of analyses is discussed. The algorithm appears to be complementary to an algorithm by S. Kuno in several respects, including the space-time trade-off and the degree of context dependence involved.
Description Affiliation: Harvard Univ., Cambridge, MA (Woods, William A.)
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 13
Issue Number 7
Page Count 9
Starting Page 437
Ending Page 445

Open content in new tab

   Open content in new tab
Source: ACM Digital Library