logo
down
shadow

Lemon Parser: This rule can not be reduced


Lemon Parser: This rule can not be reduced

By : Scott J
Date : November 21 2020, 03:00 PM
will help you The problem is that your grammar is LR(2), not LR(1).
Many shift/reduce conflicts arise because it is impossible to know what to do until the token following a %{ is seen. For example, consider the partial template (I've deliberately destroyed the indentation):
code :
{% switch username %} {% case "Jim" %} I want to say: {%
{% switch username %} {% case "Jim" %} I want to say: {% endcase
{% switch username %} {% case "Jim" %} I want to say: {% case
{% switch username %} {% case "Jim" %} I want to say: {% switch
program ::= template_language(Q) . {
    status->ret = Q;
}

template_language(R) ::= statement_list(L) . {
    R = L;
}

statement_list(R) ::= statement_list(L) statement(S) . {
    R = my_list(L, S);
}

statement_list(R) ::= statement(S) . {
    R = my_list(NULL, S);
}

statement(R) ::= switch_statement(E) . {
    R = E;
}

// empty {% switch expr %} {% endswitch %}
switch_statement(R) ::= OPEN_SWITCH expr(E) CLOSE OPEN_ENDSWITCH CLOSE . {
    R = my_switch_statement(E, NULL, status->scanner_state);
}

switch_statement(R) ::= OPEN_SWITCH expr(E) CLOSE case_clauses(C) OPEN_ENDSWITCH CLOSE . {
    R = my_switch_statement(E, C, status->scanner_state);
}

case_clauses(R) ::= case_clauses(C) case_clause(K) . {
    R = my_list(C, K);
}

case_clauses(R) ::= case_clause(K) . {
    R = my_list(NULL, K);
}

// empty {% case expr %} {% endcase %}
case_clause(R) ::= OPEN_CASE expr(E) CLOSE OPEN_ENDCASE CLOSE . {
    R = case_clause(E, NULL, status->scanner_state);
}

case_clause(R) ::= OPEN_CASE expr(E) CLOSE statement_list(T) OPEN_ENDCASE CLOSE . {
    R = case_clause(E, T, status->scanner_state);
}

case_clause(R) ::= OPEN_CASE expr(E) CLOSE statement_list(T) . {
    R = case_clause(E, T, status->scanner_state);
}


case_clause(R) ::= OPEN_DEFAULT CLOSE statement_list(T) . {
    R = case_clause(E, T, status->scanner_state);
}
program ::= template_language(Q) . {
    status->ret = Q;
}

template_language(R) ::= statement_list(L) . {
    R = L;
}

statement_list(R) ::= statement_list(L) statement(S) . {
    R = my_list(L, S);
}

statement_list(R) ::= . {
    R = NULL;
}

statement(R) ::= switch_statement(E) . {
    R = E;
}

switch_statement(R) ::= OPEN_SWITCH expr(E) CLOSE case_clauses(C) OPEN_ENDSWITCH CLOSE . {
    R = my_switch_statement(E, C, status->scanner_state);
}

case_clauses(R) ::= case_clauses(C) case_clause(K) . {
    R = my_list(C, K);
}

case_clauses(R) ::= . {
    R = NULL;
}

case_clause(R) ::= OPEN_CASE expr(E) CLOSE statement_list(T) OPEN_ENDCASE CLOSE . {
    R = case_clause(E, T, status->scanner_state);
}

case_clause(R) ::= OPEN_CASE expr(E) CLOSE statement_list(T) . {
    R = case_clause(E, T, status->scanner_state);
}

case_clause(R) ::= OPEN_DEFAULT CLOSE statement_list(T) . {
    R = case_clause(E, T, status->scanner_state);
}


Share : facebook icon twitter icon
Is the lemon parser LALR(1) or SLR(1)?

Is the lemon parser LALR(1) or SLR(1)?


By : Sylvio Albernaz
Date : March 29 2020, 07:55 AM
This might help you If it were pure SLR, there wouldn't be any lookahead symbols ($this->symbol[$j]) used to control a reduction. So I conclude it is LALR(1).
EDIT: yoyo is right SLR(1) does use next-input symbols to control reductions (I misread the question as [LALR(1) vs] SLR(0), which simply doesn't care); I stand corrected. In checking, SLR(1) uses the (production rule context-free) FOLLOW set to control reductions; LALR(1) uses the (left-context dependent) LOOKAHEAD set. So, both have a "lookahead" set on each reduction. That means you can't tell from this code fragment which kind it is; at best we hope the coder is really computing "a" lookahead set. You'd have to see the rest of the code to know what kind it is.
lemon parser parsing 0 token

lemon parser parsing 0 token


By : Sidar Surer
Date : March 29 2020, 07:55 AM
Does that help Okay, I figured it out. The reason is that there is a particularly nasty (and poorly documented) interaction going on between flex and lemon.
In an attempt to save memory, lemon will hold onto a token without copying, and push it on to an internal token stack. However, flex also tries to save memory by changing the value that yyget_text points to as it lexes the input. The offending line in my example is:
code :
// in the do loop of main.c...
Parse(parser, token, yyget_text(lexer));
Parse(parser, token, strdup(yyget_text(lexer)));
Getting lemon parser conflict

Getting lemon parser conflict


By : Amer Jaradeh
Date : March 29 2020, 07:55 AM
I think the issue was by ths following , The heart of the problem is that you want to execute enterScope() after the brace which initiates a statement block. However, if the brace is followed by the two tokens VAR and :, then it starts an object literal, not a block. So it is impossible to know whether or not to execute the enterScope action without two-token lookahead, and lemon does not produce LR(2) grammars. To that extent, you are correct that the problem is unsolvable. But of course there are solutions.
Probably the worst solution from any perspective (readability, complexity, verificability) is to create an LR(1) grammar using the usual LR(2)→LR(1) transformation, which will allow you to call the enterScope(); action at the point where it is clear that a scope has been entered. This means delaying the reduction by one token. That in turn means dividing expr into two disjoint non-terminals: those expr which can start with a VAR and those which cannot. For those expr which can start with a VAR, you also need to provide a mechanism which essentially allows you to glue together a VAR and the rest of the expr; in the case of expressions, that is particularly ugly (but still possible). The goal is to be able to write:
code :
block(A)       ::= blockPrefix(B) RCURLY .                 { closeScope(); A = B;} 
blockPrefix(A) ::= lcurlyOpen exprNotStartingVAR(E) .      { A = E; }
blockPrefix(A) ::= lcurlyVAR(V) restOfExprStartingVar(R) . { A = makeExpr(V, R); }
blockPrefix(A) ::= blockPrefix(B) SEMI expr(E) .           { A = appendExpr(B, E); }
lcurlyOpen     ::= LCURLY .                                { openScope(); }
lcurlyVAR(A)   ::= LCURLY VAR(V) .                         { openScope(); A = V; }
stmt       ::= expr SEMI | block .
stmtList   ::= stmt .
stmtList   ::= stmtList stmt .
block(A)   ::= LCURLY stmtList(B) RCURLY . { A = applyScope(newScope(), B); }
objLiteral ::= LCURLY itemList RCURLY .
objLiteral ::= LCURLY RCURLY .
itemList   ::= item .
itemList   ::= itemList COMMA item .
item       ::= VAR COLON expr .
expr       ::= VAR .
expr       ::= objLiteral .
...
lemon parser reduce error

lemon parser reduce error


By : ammar siddiqui
Date : March 29 2020, 07:55 AM
fixed the issue. Will look into that further There isn't actually quite enough information here to diagnose the complete problem, but I think I can fill in the blanks.
What's indicated is that the problem is a state where the parser has recognized tens (that would be "twenty", "thirty", ..., "ninety", right?) and it now needs a separator (which might be optional). If the lookahead token is an actual separator, it has to decide whether to reduce tens immediately to one_to_99 (as a prelude to completing one_to_999 without a trailing digit) or shift the WHITESPACE or HYPHEN character in order to extend tens with a separator and a single digit (one_to_9).
code :
one_to_99 ::= tens
            | tens one_to_9
            | tens HYPHEN one_to_9
            ;
Lemon Parser REPL

Lemon Parser REPL


By : Garry Baybayan
Date : March 29 2020, 07:55 AM
may help you . Your grammar has parsing conflicts. These must be resolved if you have a hope of getting the grammar to work correctly.
(The grammar also has an undefined non-terminal, keyword_signature, and an unused non-terminal message. To get it to compile without warnings, I simply removed them. I don't think it makes any difference to the analysis below.)
code :
file ::= statement_list .
file ::= statement .
 statement_list ::= statements statement .
 statements ::= .
statement_list ::= statements .
statement_list ::= statements statement .
statements     ::= statements statement STOP .
statements     ::= .
statement_list ::= statements .
statement_list ::= statements STOP .
statements ::= statement .
statements ::= statements STOP statement .
%include { #include <assert.h> }
file ::= method.
file ::= statement_list.
file ::= .
method ::= signature OBRAC statement_list CBRAC .
signature ::= WORD .
statement_list ::= statements STOP .
statement_list ::= statements .
statements ::= statements STOP statement .
statements ::= statement .
statement ::= expression .
expression ::= simple_expression .
simple_expression ::= WORD simple_message .
simple_message ::= WORD .
%extra_argument { int* status }
%syntax_error { *status = 1; }
%parse_failure { fprintf(stderr, "Parse failed.\n"); }
%parse_accept { fprintf(stderr, "Parse succeeded.\n"); }
%{
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include "parser.h"
void* ParseAlloc(void* (*allocProc)(size_t));
void* Parse(void*, int, int, int*);
void* ParseFree(void*, void(*freeProc)(void*));

void synerr(const char* token) {
  fprintf(stderr, "Syntax error handling '%s'\n", token);
}
%}
%option noinput nounput noyywrap nodefault
%x FLUSH
%%
    void* parser = ParseAlloc(malloc);
    int status = 0;
    #define SEND(typ, val) do {                        \
       if (Parse(parser, typ, val, &status), status) { \
         synerr(yytext); BEGIN(FLUSH);                 \
       }                                               \
    } while(0)
[[:space:]]+ ;
[[:alnum:]]+ { SEND(WORD, 0); }
"["          { SEND(OBRAC, 0); }
"]"          { SEND(CBRAC, 0); }
"."          { SEND(STOP, 0); }
.            { synerr(yytext); BEGIN(FLUSH); }
<FLUSH>.+    ;
<FLUSH>\n    { status = 0; BEGIN(INITIAL); }
<<EOF>>      { if (status == 0) {
                 Parse(parser, 0, 0, &status);
                 if (status) synerr("EOF");
               }
               ParseFree(parser, free );
               return 0;
             }
%%

int main(int argc, char** argv) {
   return yylex();
}
$ lemon parser.y
$ flex -o main.c main.l
$ gcc -std=c11 -Wall -Wno-unused-variable -o catlan -D_XOPEN_SOURCE=800 main.c parser.c
$ ./catlan <<< 'NSObject'
Parse failed.
Syntax error handling 'EOF'
$ ./catlan <<< 'NSObject description'
Parse succeeded.
$ ./catlan <<< 'NSObject description.'
Parse succeeded.
$ ./catlan <<< 'NSObject description. OtherObject'
Parse failed.
Syntax error handling 'EOF'
$ ./catlan <<< 'NSObject description. OtherObject otherDesc'
Parse succeeded.
$ ./catlan <<< 'NSObject description. OtherObject otherDesc.'
Parse succeeded.
$ ./catlan <<< 'NSObject description. OtherObject otherDesc extra words'
Syntax error handling 'extra'
Parse succeeded.
$ ./catlan <<< 'method [ NSObject desc]'
Parse succeeded.
$ ./catlan <<< 'method [ NSObject desc.]'
Parse succeeded.
$ ./catlan <<< 'method [ NSObject desc extra words]'
Syntax error handling 'extra'
Parse failed.
$ ./catlan <<< 'method [ NSObject desc. Second]'
Syntax error handling ']'
Parse failed.
$ ./catlan <<< 'method [ NSObject desc. Second desc]'
Parse succeeded.
shadow
Privacy Policy - Terms - Contact Us © voile276.org