Thumbnail
Access Restriction
Subscribed

Author Gilbert, Philip
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1966
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract The analytic grammar (a model which provides a rigorous description of syntactic analysis) is presented, and some of its fundamental properties are shown. Various submodels are discussed and equivalences among these are noted.An analytic grammar incorporates a set $\textit{P}$ of syntactic productions, and also a $\textit{scan}$ @@@@. At each successive “rewriting” in the analysis of a string $\textit{x},$ @@@@ computes a subset of productions applicable to $\textit{x}$ (i.e., which may be used to “rewrite” $\textit{x})$ from the set of productions which are potentially applicable to $\textit{x}.$ Thus each scan determines a class of grammars.It is shown that all analytic languages are recursive, and conversely, all recursive sets are analytic languages. All phrase structure grammars are analytic grammars. A simple sufficient condition is shown under which an analytic grammar provides unique analyses for all strings.Particularly relevant to syntactic analysis of algorithmic languages (i.e., languages which are used to specify computing algorithms) are the “leftmost” scans, each of which chooses a certain “leftmost” production. Conditions which provide equivalences among these scans are noted.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1966-01-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 13
Issue Number 1
Page Count 18
Starting Page 90
Ending Page 107


Open content in new tab

   Open content in new tab
Source: ACM Digital Library