Bison e Lex String vs Char

Question

Estou tentando avaliar e a expressão do formulário

#SomeFunc[expr][expr]expr

O EXPR pode ser uma string composta de certos caracteres ou uma função acima. Então isso pode parecer algo como

#SomeFunc[#SomeFunc[#SomeFunc[nm^2][nn]][nm]][n]...

O problema é que, se eu frear em tokens na forma de

"#"SomeFunc    {yylval.fn=F_some; return FUNC;}
m|n|ms         {return TEXT;}
"^"            {yylval.fn=F_pow;  return FUNC;}
[1-9]+         {yylval=atoi(yytext); return NUMBER;}

Tenho problemas para construir uma gramática se eu tiver algo como

#SomeFunc[#SomeFunc[nm^2][nn]][n]

calc:
      | calc expr EOL { eval($2); }

expr: TEXT {$$= add it to ast-leaf }
      | FUNC '[' expr ']' '[' expr ']' {$$= add ast(func,$3,$6) }
      | expr expr {$$= add to ast('*',$1,$2 }

E não tenho certeza se a gramática está errada ou minha implementação de um AST.

Acho que minha lógica falha porque, no caso de NM, expr será expr, que retornará o valor de n*m, que ainda é NM. Isso causará um loop infinito? Como devo analisar essa expressão.

Não jogue pedras. Bison Newbie

Editar posteriorConsegui limpar e testar o código por trás da AST e algumas listas vinculadas. O único problema continua sendo a gramática.

%union { struct ast *a; char *strval; int ival; } 
%type <a> exp fact 
%token <strval> ISU 
%token <ival> NUMBER 
%token FUNC POW 
%token EOL OP CP 

%% 

calclist: | calclist exp EOL { printf("result >",eval($2));}; 

exp: fact | exp fact {$$ = newast('*', $1,$2);} ; 

fact: FUNC OP exp CP OP exp CP { $$ = newast('/',$3,$6);}
    | ISU POW NUMBER { $$ = newnum($1, $3);}
    | ISU { $$ = newnum($1,1);};  

Esta gramática falha para um expr como frac [m^2] [m^4] nó / nó k m^4 nó k m^4

Answer 1

Simplifiquei a gramática para expressar apenas as formas fundamentais, e não necessariamente as maneiras pelas quais elas poderiam ser combinadas. (Também eliminei o Lexer gerado por simplicidade de experimentação; portanto, na minha, todas as funções são chamadas de 'f' e você pode ter qualquer dígito que quiser, desde que seja '2'.)

Isso parece funcionar bem para mim em vários casos de teste: observe que todas as minhas regras, exceto calc são deixados recursivos, que é o que você deseja com YACC.

cat subcity.y && yacc subcity.y && cc -w y.tab.c -ly 
%%
calc: | calc expr '\n';
expr: | expr form
      | expr operator form;
form: mns | '[' expr ']' | digit | 'f';
mns: 'm' | 'n' | 's';
digit: '2';
operator: '^' | '+' |  '-' | '*' | '/';
%%
int yylex(void) { int c; while ((c = getchar()) == ' ') continue; return c; }
int main(int ac, char **av) { if (yyparse() != 0) printf("parse error\n"); }

Parece funcionar:

$ ./a.out
f[ f[ f[nm^2] [nn]] [nm]] [n]
f[f[2]] [f[f[nm^2]f]]
f[f[nm^2][nn]][n]
f[m^2][m^2] n / n 2 m^2 n 2 n^2
$ 

Eu não conseguia descobrir o que você não gostava na sua primeira gramática, mas espero que isso lhe dê algumas idéias. Algo mais assim é certamente o que EU começaria com. O fato de sua gramática apresentar expressões adjacentes não conectadas por um operador é um pouco estranho. É mais comum com símbolos terminais, como a maneira como as cordas são concatenadas em alguns idiomas. Algumas pessoas inventaram um operador para eliminar este caso.

Answer 2

A partir da sua descrição, você espera que "^2" seja um expr válido, mas sua regra Lex retorna func para '^' e número para '2', mas em sua gramática, func deve ser seguido por '[' na única regra Você tem para isso e não tem nenhuma regra para o número. Você provavelmente deseja uma regra "expr: número", mas também precisará de uma regra "expr: func expr" para depois combinar "^2", então parece que você pode querer ter '^' retornar alguns outros símbolo.