[c/lemon] parser reduceert (te snel)

[igmar]

Ik heb een Lemon grammar die er grofweg als volgt uitziet :

code:

start ::= groups.
groups ::= groups group.
groups ::= group.
group(A) ::= IDENTIFIER identparams CURLY_OPEN assignments CURLY_CLOSE SEMICOLON.
group(A) ::= IDENTIFIER CURLY_OPEN assignments CURLY_CLOSE SEMICOLON.
assignments ::= assignments assignment.
assignments ::= assignment.
assignment ::= IDENTIFIER ASSIGNMENT bool_expr SEMICOLON.

en dat parsed zoiets als

code:

name {
     name = "value";
     name2 = "value";
};

Da's een standaard config met aan het eind van de rit een name = value waarde. Wat er gebeurd is dat de name = "value" tokens resulteren in een assignments ::= assignments assignment reduce. Ik dacht dat assignments(X) een constante waarde is, maar dat is niet zo : Een reduce zorgt voor een nieuwe waarde op de parser stack :

code:

P assignment(0x807e778) ::= IDENTIFIER(0x807e728) ASSIGNMENT mvalue SEMICOLON.

P assignments((nil)) ::= assignments((nil)) assignment(0x807e778).
P append 0x807e778 to 0x807e838
P mvalue ::= string.
P assignment(0x807e750) ::= IDENTIFIER(0x807e7c8) ASSIGNMENT mvalue SEMICOLON.
P assignments((nil)) ::= assignments(0x807e838) assignment(0x807e750).
P append 0x807e750 to 0x807e910
P mvalue ::= string.
P assignment(0x807e7f0) ::= IDENTIFIER(0x807e7a0) ASSIGNMENT mvalue SEMICOLON.
P assignments((nil)) ::= assignments(0x807e910) assignment(0x807e7f0).
P append 0x807e7f0 to 0x807e9e8
P group(0x807e7a0) assignments(0x807e9e8) : bind
P groups ::= group(0x807e7a0).

de parser trace staat op pastebin. Het resultaat is dat uiteindelijk de laatste assignment wordt gezien in de tree. Op zich kan ik het wel fixen, maar ik zou dit graag net oplossen.

Iemand een briljante suggestie ?

[ Voor 0% gewijzigd door igmar op 18-05-2013 13:56 . Reden: Kloppende code ]

[Daos]

Bij groups doe je:

code:

groups ::= groups group.
groups ::= group.

Moet je zoiets niet ook bij de assignments doen (zodat de recursie stopt)?

[igmar]

Daos schreef op vrijdag 17 mei 2013 @ 22:54:
Bij groups doe je:

code:

groups ::= groups group.
groups ::= group.

Moet je zoiets niet ook bij de assignments doen (zodat de recursie stopt)?

Ik heb de OP even aangepast. Bovenstaande doe ik ook, maar dat geeft ook het verkeerde resultaat. Ik ga eens kijken in de sqlite parser, eens kijken wat ze daar precies doen. Mogelijk geeft dat wat inzicht :-)

[Daos]

Ik begrijp je probleem niet echt. Kan je het nog een keer op een andere manier uitleggen?

[MLM]

Als ik zo kijk werkt de grammar toch gewoon. De pastebin lijkt mij te kloppen.
Wat is je probleem?

[igmar]

Dat als

code:

assignments(A) ::= assignments assignment(B).

wordt gereduced en ik aan A iets toewijs (een linked list, waaraan B wordt toegevoegd), bij de volgende reduce van die regel A weer null is. Ik had verwacht dat A een constante waarde heeft.
Nu raak ik naar elke reduce m'n state kwijt, en wordt alleen de laatste regel vervolgens toegevoegd aan de lijst die bij

code:

group(A) ::= IDENTIFIER CURLY_OPEN assignments CURLY_CLOSE SEMICOLON.

wordt toegevoegd.

[Daos]

Moet je niet iets met die rechter assignments doen? Bv zoiets: ?
assignments(A) ::= assignments(C) assignment(D) { A = GenerateListFromListAndAssignment(C, D) }

edit:
voorbeeldje grammar.y (met strings kreeg ik het niet aan de praat; wel met char *)

C++:

%token_type {char *}  
   
%include {   
#include <cstring>  
#include <cassert>  
#include <cstdlib>  
#include <iostream>  
#include "example1.h"
}  
   
%syntax_error {  
    std::cout << "Syntax error!" << std::endl;  
}   
   
program ::= list(A).   
{ 
    std::cout << "Result = {" << A << "}" << std::endl; 
    delete[] A;
}  
   
list(A) ::= list(B) STRING(C).   
{ 
    int size = strlen(B) + 2 + strlen(C);
    A = new char[size + 1]; 
    strcpy(A, B);
    strcat(A, ", ");
    strcat(A, C);
    delete[] B;
}  

list(A) ::= STRING(B). 
{
    int size = strlen(B);
    A = new char[size + 1]; 
    strcpy(A, B);
} 

en de main:

C++:

int main()
{
  void* pParser = ParseAlloc(malloc);

  /* Input: 
      1 2 3 4 5
                                */
                                
  Parse(pParser, STRING, (char *)"1");
  Parse(pParser, STRING, (char *)"2");
  Parse(pParser, STRING, (char *)"3");
  Parse(pParser, STRING, (char *)"4");
  Parse(pParser, STRING, (char *)"5");
  Parse(pParser, 0, 0);

  ParseFree(pParser, free);
}

[ Voor 80% gewijzigd door Daos op 20-05-2013 19:06 . Reden: nu met new en delete ]

[igmar]

De oplossing :

code:

assignments(A) ::= assignments(B) assignment(C). {
A = B;
/* rest van de code */

In ieder geval bedankt voor het meedenken !