Precedences in specifications and implementations of programming languages

AbstractAlthough precedences are often used to resolve ambiguities in programming language descriptions, there has been no parser-independent definition of languages which are generated by grammars with precedence rules. This paper gives such a definition for a subclass of context-free grammars. The definition is shown to be equivalent to the implicit definition an operator precedence parser gives.A problem with a language containing infix, prefix and postfix operators of different precedences is that the well-known algorithm, which transforms a grammar with infix operator precedences to an ordinary unambiguous context-free grammar, does not work. This paper gives an algorithm that works also for prefix and postfix operators, and the correctness of it is proved. An application of the algorithm is also presented