{"id":2703,"date":"2020-07-08T17:14:40","date_gmt":"2020-07-08T21:14:40","guid":{"rendered":"http:\/\/codinggorilla.com\/?p=2703"},"modified":"2020-10-08T11:58:16","modified_gmt":"2020-10-08T15:58:16","slug":"converting-bison-precedence-and-associativity-rules-to-antlr","status":"publish","type":"post","link":"http:\/\/165.227.223.229\/index.php\/2020\/07\/08\/converting-bison-precedence-and-associativity-rules-to-antlr\/","title":{"rendered":"Converting Bison precedence and associativity rules to Antlr"},"content":{"rendered":"\n<p>As noted in the <a href=\"https:\/\/www.gnu.org\/software\/bison\/manual\/html_node\/Precedence-Decl.html\" class=\"ek-link\">Bison guide<\/a>:<\/p>\n\n\n\n<ul><li>The associativity of an operator&nbsp;<var>op<\/var>&nbsp;determines how repeated uses of the operator nest: whether \u00e2\u20ac\u0098<samp><var>x<\/var>&nbsp;<var>op<\/var>&nbsp;<var>y<\/var>&nbsp;<var>op<\/var>&nbsp;<var>z<\/var><\/samp>\u00e2\u20ac\u2122 is parsed by grouping&nbsp;<var>x<\/var>&nbsp;with&nbsp;<var>y<\/var>&nbsp;first or by grouping&nbsp;<var>y<\/var>&nbsp;with&nbsp;<var>z<\/var>&nbsp;first.&nbsp;<code>%left<\/code>&nbsp;specifies left-associativity (grouping&nbsp;<var>x<\/var>&nbsp;with&nbsp;<var>y<\/var>&nbsp;first) and&nbsp;<code>%right<\/code>&nbsp;specifies right-associativity (grouping&nbsp;<var>y<\/var>&nbsp;with&nbsp;<var>z<\/var>&nbsp;first).&nbsp;<code>%nonassoc<\/code>&nbsp;specifies no associativity, which means that \u00e2\u20ac\u0098<samp><var>x<\/var>&nbsp;<var>op<\/var>&nbsp;<var>y<\/var>&nbsp;<var>op<\/var>&nbsp;<var>z<\/var><\/samp>\u00e2\u20ac\u2122 is considered a syntax error.<code>%precedence<\/code>&nbsp;gives only precedence to the&nbsp;<var>symbols<\/var>, and defines no associativity at all. Use this to define precedence only, and leave any potential conflict due to associativity enabled.<\/li><li>The precedence of an operator determines how it nests with other operators. All the tokens declared in a single precedence declaration have equal precedence and nest together according to their associativity. When two tokens declared in different precedence declarations associate, the one declared later has the higher precedence and is grouped first.<\/li><\/ul>\n\n\n<h2>Associativity<\/h2>\n\n\n<p>By default, operators in Antlr are left-associative. So, %left associative operators do not require any additional declarations in Antlr.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>%left op<\/code><\/pre>\n\n\n\n<p>=&gt;<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>e : e op e<\/code><\/pre>\n\n\n\n<p>An operator declared as %right associative will need to be tagged in Antlr with <em>&lt;assoc=right&gt;<\/em>.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>%right op<\/code><\/pre>\n\n\n\n<p>=&gt;<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>e : &lt;assoc=right> e op e<\/code><\/pre>\n\n\n\n<p>Antlr does not have a %nonassoc declaration. To disallow a non-associative operator in Antlr, a semantic predicate must be used. <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>%nonassoc op<\/code><\/pre>\n\n\n\n<p>=&gt;<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>e : e op e { Input.LA(1) != op }?<\/code><\/pre>\n\n\n\n<h2>Precedence<\/h2>\n\n\n\n<p>In Antlr, to make op1 higher precedence than op2, one will need to define the alternative containing op1 before the alternative for op2. In other words, the order of the alternatives of the operators in Antlr is the same as the order of appearance in the Bison grammar.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>%left op1\n%left op2<\/code><\/pre>\n\n\n\n<p>=&gt;<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>e : e op1 e | e op2 e<\/code><\/pre>\n\n\n\n<h2>What are precedence and associativity bound to?<\/h2>\n\n\n\n<p>As noted <a href=\"https:\/\/docs.oracle.com\/cd\/E19504-01\/802-5880\/6i9k05dh3\/index.html#:~:text=A%20precedence%20and%20associativity%20is%20associated%20with%20each%20grammar%20rule.&amp;text=Left%20associative%20implies%20reduce%3B%20right,reduce%20conflicts%20reported%20by%20yacc%20.\" class=\"ek-link\">here<\/a>: &#8220;A precedence and associativity is associated with each grammar rule. It is the precedence and associativity of the final token or literal in the body of the rule. If the&nbsp;%prec&nbsp;construction is used, it overrides this default value. Some grammar rules may have no precedence and associativity associated with them.&#8221;<\/p>\n\n\n\n<p>Even though precedence and associativity are specified with an operator, the precedence and associativity are associated with a rule as well. Note, this makes sense from an implementation reference: when you see a shift\/shift or shift\/reduce conflict, you are deciding what to place in the parsing table for the action based on the rule and the lookahead that you see. Crucially, the %prec, %right, %left, %nonassoc clauses can appear within a rule, which overrides any clauses specified elsewhere.<\/p>\n\n\n\n<p>&#8211;Ken<\/p>\n","protected":false},"excerpt":{"rendered":"<p>As noted in the Bison guide: The associativity of an operator&nbsp;op&nbsp;determines how repeated uses of the operator nest: whether \u00e2\u20ac\u0098x&nbsp;op&nbsp;y&nbsp;op&nbsp;z\u00e2\u20ac\u2122 is parsed by grouping&nbsp;x&nbsp;with&nbsp;y&nbsp;first or by grouping&nbsp;y&nbsp;with&nbsp;z&nbsp;first.&nbsp;%left&nbsp;specifies left-associativity (grouping&nbsp;x&nbsp;with&nbsp;y&nbsp;first) and&nbsp;%right&nbsp;specifies right-associativity (grouping&nbsp;y&nbsp;with&nbsp;z&nbsp;first).&nbsp;%nonassoc&nbsp;specifies no associativity, which means that \u00e2\u20ac\u0098x&nbsp;op&nbsp;y&nbsp;op&nbsp;z\u00e2\u20ac\u2122 is considered a syntax error.%precedence&nbsp;gives only precedence to the&nbsp;symbols, and defines no associativity at all. Use this &hellip; <\/p>\n<p class=\"link-more\"><a href=\"http:\/\/165.227.223.229\/index.php\/2020\/07\/08\/converting-bison-precedence-and-associativity-rules-to-antlr\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Converting Bison precedence and associativity rules to Antlr&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/posts\/2703"}],"collection":[{"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/comments?post=2703"}],"version-history":[{"count":0,"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/posts\/2703\/revisions"}],"wp:attachment":[{"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/media?parent=2703"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/categories?post=2703"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/165.227.223.229\/index.php\/wp-json\/wp\/v2\/tags?post=2703"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}