Resolving shift/reduce conflict for default label in switch block
<p>I'm writing a parser for Unrealscript using PLY, and I've run into (hopefully) one of the last ambiguities in the parsing rules that I've set up.</p>

<p>Unrealscript has a keyword, <code>default</code>, which is used differently depending on the context. In a regular statement line, you could use <code>default</code> like so:</p>

<pre><code>default.SomeValue = 3;  // sets the "default" class property to 3
</code></pre>

<p>There is also, of course, the <code>default</code> case label for <code>switch</code> statements:</p>

<pre><code>switch (i) {
    case 0:
        break;
    default:
        break;
}
</code></pre>

<p>There is an ambiguity in the parsing when it encounters the <code>default</code> label within what it thinks is the <code>case</code>'s statement block. Here is an example file that runs into a parsing error:</p>

<h1>Input</h1>

<pre><code>class Example extends Object;

function Test() {
    switch (A) {
        case 0:
            default.SomeValue = 3;    // OK
        default:                      // ERROR: Expected "default.IDENTIFIER"
            break;
    }
}
</code></pre>

<h1>Parsing Rules</h1>

<p>Here are the rules that are in conflict:</p>

<p>All of the rules can be seen in their entirety <a href="https://github.com/cmbasnett/ulex/blob/master/yucc.py" rel="nofollow">on GitHub</a>.</p>

<h2><code>default</code></h2>

<pre><code>def p_default(p):
    'default : DEFAULT PERIOD identifier'
    p[0] = ('default', p[3])
</code></pre>

<h2><code>switch</code></h2>

<pre><code>def p_switch_statement(p):
    'switch_statement : SWITCH LPAREN expression RPAREN LCURLY switch_cases RCURLY'
    p[0] = ('switch_statement', p[3], p[6])


def p_switch_case_1(p):
    'switch_case : CASE primary COLON statements_or_empty'
    p[0] = ('switch_case', p[2], p[4])


def p_switch_case_2(p):
    'switch_case : DEFAULT COLON statements_or_empty'
    p[0] = ('default_case', p[3])


def p_switch_cases_1(p):
    'switch_cases : switch_cases switch_case'
    p[0] = p[1] + [p[2]]


def p_switch_cases_2(p):
    'switch_cases : switch_case'
    p[0] = [p[1]]


def p_switch_cases_or_empty(p):
    '''switch_cases_or_empty : switch_cases
                             | empty'''
    p[0] = p[1]
</code></pre>

<p>Any help or guidance on how to resolve this conflict will be greatly appreciated! Thank you in advance.</p>

<p>What you have here is a simple shift/reduce conflict (with the token <code>default</code> as lookahead) being resolved as a shift.</p>

<p>Let's reduce this all to a much smaller, if not minimal example. Here's the grammar, partly based on the one in the Github repository pointed to in the OP (but intended to be self-contained):</p>

<pre><code>statements: statements statement |
statement : assign SEMICOLON
          | switch
assign    : lvalue EQUALS expression
switch    : SWITCH LPAREN expression RPAREN LCURLY cases RCURLY
cases     : cases case | 
case      : CASE expression COLON statements
          | DEFAULT COLON statements
expression: ID | INT
lvalue    : ID | DEFAULT
</code></pre>

<p>The key here is that a <code>statement</code> might start with the token <code>DEFAULT</code>, and a <code>case</code> might also start with the token <code>DEFAULT</code>. Now, suppose we've reached the following point in the parse:</p>

<pre><code>switch ( &lt;expression&gt; ) { &lt;cases&gt; case &lt;expression&gt; : &lt;statements&gt;
</code></pre>

<p>so we're in the middle of a <code>switch</code> compound statement; we've seen <code>case 0:</code> and we're working on a list of statements. The current state includes the items (there are a few more; I only include the relevant ones):</p>

<pre><code>1. statements: statements Â· statement
2. case      : CASE expression COLON statements Â·
3. statement : Â· assign SEMICOLON
4. assign    : Â· lvalue EQUALS expression
5. lvalue    : Â· DEFAULT
</code></pre>

<p>The lookahead set for item 2 is <code>[ RCURLY, DEFAULT, ID ]</code>.</p>

<p>Now suppose the next token is <kbd>default</kbd>. We could be looking at the start of a statement, if the <kbd>default</kbd> is followed by  <kbd>=</kbd>. Or we could be looking at a new case clause, if the <kbd>default</kbd> is followed by <kbd>:</kbd>. But we can't see two tokens into the future, only one; the next token is <kbd>default</kbd> and that is all we know.</p>

<p>But we need to make a decision:</p>

<ul>
<li><p>If the <kbd>default</kbd> is the beginning of a statement, we can just shift it (item 5). Then when we see the <kbd>=</kbd>, we'll reduce <kbd>default</kbd> to <code>lvalue</code> and continue to parse the <code>assign</code>.</p></li>
<li><p>If the <kbd>default</kbd> is the beginning of a case, we need to reduce <code>CASE expression COLON statements</code> to <code>case</code> (item 2). We will then reduce <code>cases case</code> to <code>cases</code> before we finally shift the <kbd>default</kbd>. We will then shift the <kbd>:</kbd> and continue with <code>DEFAULT COLON statements</code>.</p></li>
</ul>

<p>Like most LR parser generators, PLY resolves shift/reduce conflicts in favour of the shift, so it will always take the first of the two options above. If it then sees <kbd>:</kbd> instead of <kbd>=</kbd>, it will report a syntax error.</p>

<p>So what we have is just another example of an LR(2) grammar. LR(2) grammars can always be rewritten as LR(1) grammars, but the rewritten grammar is often ugly and bloated. Here is one possible solution, which is possibly less ugly than most. </p>

<p>The body of a switch, using EBNF operators <code>|</code>, <code>*</code> and <code>+</code> (alternation, optional repetition, and repetition) is:</p>

<pre><code>switch-body -&gt; (("case" expression | "default") ":" statement*)+
</code></pre>

<p>Or, to make it a little less cumbersome:</p>

<pre><code>case-header -&gt; ("case" expression | "default") ":"
switch-body -&gt; (case-header statement*)+
</code></pre>

<p>From the perspective of accepted strings, that's exactly the same as</p>

<pre><code>switch-body -&gt; case-header (case-header | statement)*
</code></pre>

<p>In other words, a sequence of things which are either <code>case-header</code>s or <code>statement</code>s, where the first one is a <code>case-header</code>.</p>

<p>This way of writing the rule does not generate the correct parse tree; it simplifies the structure of a switch statement into a soup of statements and case labels. But it does recognise exactly the same language.</p>

<p>On the plus side, it has the virtue of not forcing the parser to decide when a case cause has terminated. (The grammar no longer has case clauses.) So it is a simple LR(1) grammar:</p>

<pre><code>switch       : SWITCH LPAREN expression RPAREN LCURLY switch_body RCURLY
switch_body  : case_header
             | switch_body statement
             | switch_body case_header
case_header  : CASE expr COLON
             | DEFAULT COLON
</code></pre>

<p>Now, we could make the argument that the resulting parse tree is, in fact, accurate. Unrealscript shares the same design decision about <code>switch</code> statements as C, in which a <code>case</code> clause does not actually define a block in any real sense of the word. It is simply a label which can be jumped to, and a conditional jump to the next label.</p>

<p>But it is actually not particularly complicated to fix the parse tree as we go, because each reduction to <code>switch_body</code> clearly indicates what we're adding. If we're adding a case-header, we can append a new list to the accumulating list of case clauses; if it's a statement, we append the statement to the end of the last case clause.</p>

<p>So we could write the above rules in PLY roughly as follows:</p>

<pre><code>def p_switch_body_1(p):
    ''' switch_body  : case_header '''
    p[0] = [p[1]]

def p_switch_body_2(p):
    ''' switch_body  : switch_body statement '''
    # Append the statement to the list which is the last element of
    # the tuple which is the last element of the list which is the
    # semantic value of symbol 1, the switch_body.
    p[1][-1][-1].append(p[2])
    p[0] = p[1]

def p_switch_body_3(p):
    ''' switch_body  : switch_body case_header '''
    # Add the new case header (symbol 2), whose statement list
    # is initially empty, to the list of switch clauses.
    p[1].append(p[2])
    p[0] = p[1]

def p_case_header_1(p):
    ''' case_header  : CASE expr COLON '''
    p[0] = ('switch_case', p[2], [])

def p_case_header_2(p):
    ''' case_header  : DEFAULT COLON '''
    p[0] = ('default_case', [])
</code></pre>

python ply lalr unrealscript