Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I think you're semi-right here, but the term precedence is ambiguous.

Left recursion causes rules to be ambiguous. In `<S> | a`, it's always ambiguous if the input has ended. Thus the data structure that would be traversed can be a circular graph. In `<S> := a | <S>, S := ε', the rules are unambiguous and the data structure that is traversed has the shape of a tree.

You get precedence rules by defining the shape of this tree, thus which rules will be visited before which.

However it doesn't have to be strict precedence. Some rules can have an ambiguous order as long as the execution still follows the shape of a tree.

For example, in my simple rule above, it doesn't matter if you visit the ε rule or the other rule first in your implementation (although it's less efficient to visit ε first).

So, I think precedence is a side-effect of doing this transformation.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: