By Robert W. Floyd
Communications of the ACM,
February 1964,
Vol. 7 No. 2, Pages 62-67
10.1145/363921.363927
Comments
Certain phase structure grammars define languages in which the phrasehood and structure of a substring of a sentence may be determined by consideration of only a bounded context of the substring. It is possible to determine, for any specified bound on the number of contextual characters considered, whether a given grammar is such a bounded context grammar. Such grammars are free from syntactic ambiguity. Syntactic analysis of sentences in a bounded context language may be performed by a standard process and requires a number of operations proportional to the length of sentence analyzed.
Bounded context grammars form models for most languages used in computer programming, and many methods of syntactic analysis, including analysis by operator precedence, are special cases of bounded context analysis.
The full text of this article is premium content
No entries found
Log in to Read the Full Article
Need Access?
Please select one of the options below for access to premium content and features.
Create a Web Account
If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.
Join the ACM
Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.
Subscribe to Communications of the ACM Magazine
Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.
Purchase the Article
Non-members can purchase this article or a copy of the magazine in which it appears.
