Distinguishing redundant parentheses by syntax

Abstract

We give a generalized formal schema for designing a context free expression grammar that distinguishes required parentheses from redundant parentheses by means of formal syntax alone. The method applies to expression grammars having binary operators at any number of precedence levels, each level having any number of operators and being either left-associative, right-associative, or (syntactically) non-associative. We give proofs of correct parsing, unambiguity, LR(1)-ness, and the distinction of redundant parentheses. The resulting grammars appear to be LALR(1).

Keywords:

• Compilers
• Programming languages
• Redundant parentheses
• Context-free grammars