Robert W. Floyd
Abstract
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.
- 1 ARDEN AND GRAHAM, On GAT and the construction of translators. Comm. ACM 2 (1959), 24-26. Google Scholar
Digital Library
- 2 BAR-HILLEL, Y., PERLES, M., AND SHAMIR, E. On formal properties of simple phrase structure grammars. Z. Phonetik, Sprachwise, und Kommunikationsforach. 14, 2(1961), 143-172.Google Scholar
- 3 CHOMSKY, N. On certain formal properties of grammars. Inf. Contr. 2 (1959), 137-167.Google ScholarCross Ref
- 4 EICKEL, J., PAUL, M., BAUER, F. L,, AND SAMELSON, K. A syntax-controlled generator of formal languages processors. Institut f~r Angew. Math., Johannes Gutenberg Univ. in Mainz (Sept. 1962).Google Scholar
- 5 FLOYD, R. W. A descriptive language for symbol manipulation. J. ACM 8, 4 (1961), 579-584. Google ScholarDigital Library
- 6 ----. Syntactic analysis and operator precedence. J. ACM 10 (1963), 3. Google ScholarDigital Library
- 7 GORN, S. Detection of generative ambiguities in context-free mechanical languages. J. ACM 10, 2 (1963), 196-208. Google ScholarDigital Library
- 8 PAUL, M. A general processor for certain formal languages. Symbolic Languages in Data Processing, Proc. 1962 Rome Symposium, Gordon and Breach, New York, 1962.Google Scholar
- 9 SAMELSON, K., AND BAUER, F. L. Sequential formula translation. Comm. ACM 8, 2 (1960), 76-83. Google ScholarDigital Library
- 10 SCHUTZENBERGER, M. P., AND CHOMSKY, N. The algebraic theory of context-free languages. Computer Programming and Formal Systems, North-Holland, 1963.Google Scholar
Index Terms
- Bounded context syntactic analysis
Recommendations
Bounded context translation
AFIPS '64 (Spring): Proceedings of the April 21-23, 1964, spring joint computer conferenceAll translators are syntax-directed in the sense that the translator must obviously recognize the various syntactic structures and the output of the translator is a function of the syntax of the language. The term syntax-directed is usually applied to a ...
A parsing method on l-1 bounded context parsing
ACM-SE 18: Proceedings of the 18th annual Southeast regional conferenceBounded context parsing was first introduced by Floyd and Graham in which they used a precedence parsing method. However, precedence parsing has some drawbacks such as the parser is often very large and not all languages are precedence parsable.Another ...
Grammatical analysis of languages with lexical and syntactic ambiguities
The problem of parsing languages with lexical ambiguities is considered. An algorithm for lexical analysis is proposed that allows the correct processing of various ambiguities. For this algorithm, we propose an algorithm for parsing to make it possible ...
Comments