bison and lex string vs char

Question

I'm trying to evaluate and expression of the form

#SomeFunc[expr][expr]expr

expr can be either a string composed from certain characters or a function as above. So this could look something like

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

The problem is that if I brake into tokens in the form of

"#"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;}

I have issues building a grammar if I have something like

#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 }

and I'm not quite sure if the grammar is wrong or my implementation of an AST.

I find my logic flawed because in the case of nm expr will be expr expr which will return the the value of n*m which is still nm. will this cause an infinite loop? How should i parse such an expression.

Don't throw stones. Bison newbie

Later edit I managed to clean up and test the code behind the AST and some linked lists. The only problem remains the grammar.

%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);};

This grammar fails for an expr like Frac[m^2][m^4] node / node K m^4 node K m^4

Answer 1

I simplified the grammar to express just the fundamental forms, and not necessarily the ways they might be combined. (I also eliminated the generated lexer for simplicity of experimentation, so in mine all functions are called 'f' and you can have any digit you want as long as it is '2'.)

This seems to work well for me on various test cases: Note that all my rules except calc are left recursive, which is what you want with 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"); }

It seems to work:

$ ./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
$

I couldn't quite figure out what you didn't like about your first grammar, but I'm hoping this gives you some ideas. Something more like this is certainly what I would start with. The fact that your grammar features adjacent expressions unconnected by an operator is a little odd. It's more common with terminal symbols, like the way strings are concatenated in some languages. Some people would invent an operator to eliminate this case.

Answer 2

From your description, you expect "^2" to be a valid expr, but your lex rule returns FUNC for '^' and NUMBER for '2', but in your grammar, FUNC must be followed by '[' in the only rule you have for it, and you have no rule for NUMBER. You probably want a rule "expr : NUMBER", but then you'll also need a rule "expr: FUNC expr" to then match "^2", so it seems like you might instead want to have '^' return some other token.