Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Extending context-free grammars with permutation phrases

Extending context-free grammars with permutation phrases Extending Context-Free Grammars with Permutation Phrases ROBERT D. CAMERON Simon Fraser University A permutation phrase is a grammatical phrase that specifies a syntactic construct as any permutation of a set of constituent elements. Permutation phrases allow for the concise and natural expression of free-order constructs as found in programming languages and notations such as C, Cobol, BIBTEX, and Unix command lines. The conciseness and clarity of expression that permutation phrase grammars offer over context-free grammars areillustrated througha case study of the declarations in C. The parsing problem for permutation phrase grammars is considered, and it is shown how efficient linear-time parsing can be achieved for permutation phrase grammars satisfying an extended notion of the LL(l) property. Languages]: Formal Definitions and Subject Descriptors: D.3. 1 [Programming and Theo~ ”s@ax; D.3.4 [Programming Languages]: Processors ”parsing; F.4.2 [Mathematical Logic and Formal Languages]: Grammars and Other Rewriting Systems ”grammar Categories types General Additional phrase Terms: Documentation, Key Words Languages, Standardization grammar, free-order construct, permutation and Phrases: Context-free 1, INTRODUCTION Many ples programming in in 1986] Systems which attribute Cobol and include languages the order specifiers [ANSI 1986]. and in other C formal elements notations [ANSI in of BIBTEX various grammars This handle http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Letters on Programming Languages and Systems (LOPLAS) Association for Computing Machinery

Extending context-free grammars with permutation phrases

Download PDF
10 pages

Loading next page...
 
/lp/association-for-computing-machinery/extending-context-free-grammars-with-permutation-phrases-50SJQ7SWvu
Publisher
Association for Computing Machinery
Copyright
Copyright © 1993 by ACM Inc.
ISSN
1057-4514
DOI
10.1145/176454.176490
Publisher site
See Article on Publisher Site

Abstract

Extending Context-Free Grammars with Permutation Phrases ROBERT D. CAMERON Simon Fraser University A permutation phrase is a grammatical phrase that specifies a syntactic construct as any permutation of a set of constituent elements. Permutation phrases allow for the concise and natural expression of free-order constructs as found in programming languages and notations such as C, Cobol, BIBTEX, and Unix command lines. The conciseness and clarity of expression that permutation phrase grammars offer over context-free grammars areillustrated througha case study of the declarations in C. The parsing problem for permutation phrase grammars is considered, and it is shown how efficient linear-time parsing can be achieved for permutation phrase grammars satisfying an extended notion of the LL(l) property. Languages]: Formal Definitions and Subject Descriptors: D.3. 1 [Programming and Theo~ ”s@ax; D.3.4 [Programming Languages]: Processors ”parsing; F.4.2 [Mathematical Logic and Formal Languages]: Grammars and Other Rewriting Systems ”grammar Categories types General Additional phrase Terms: Documentation, Key Words Languages, Standardization grammar, free-order construct, permutation and Phrases: Context-free 1, INTRODUCTION Many ples programming in in 1986] Systems which attribute Cobol and include languages the order specifiers [ANSI 1986]. and in other C formal elements notations [ANSI in of BIBTEX various grammars This handle

Journal

ACM Letters on Programming Languages and Systems (LOPLAS) – Association for Computing Machinery

Published: Mar 1, 1993

There are no references for this article.