When parsing, certainly precedence and associativity effect the AST. But, do precedence and associativity alter the set of accepted sentences? In other words, can precedence and associativity be "ignored" (defined in some random precedence all associating left, say) in the grammar, and then the AST fixed later based on (possibly dynamic) precedence and associativity conditions?

I am concerned only with LL grammars and their common variants.


Precedence and associativity declarations are common in parser generators, but they are not part of the theory of context-free grammars. And nor are they part of the working of the LL(k) parsing algorithms (or, for that matter, the LR(k) algorithms). So there is no real way to answer that question in terms of the theory of formal languages.

On a practical level, you could perhaps look at popular parser generators and ask if the precedence and associativity declarations can alter the language recognised by the generated parser. In most cases, the answer will be "yes", but it depends considerably on how the precedence declarations are used to modify the generated parser.

I don't know enough about LL parser generators to answer that question for any of them, but it's quite clear precedence declarations for Yacc-based parser generators which use the mechanism described in the Dragon book can affect the set of recognised sentences. First, most such precedence declarations include the "nonassoc" declaration, which specifies that a particular operator cannot be used in a way which might require associativity. For example, a language in which a < b < c is illegal might declare < to be nonassociative, thereby removing the illegal construct from the language.

But even without "nonassoc", there are certainly cases in which forcing a reduction in a particular context can eliminate valid sentences. If, for example, you invert the precedence order used to resolve the "dangling else" ambiguity, you will make it impossible for the parser to recognize conditionals with "else" clauses.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.