Correct way to derive parse trees, for a given input, to show ambiguity.

NevemTeve · 08-26-2023, 11:28 AM

This is a variadic function, it forwards its argument-list to vfprintf.
https://en.wikipedia.org/wiki/Variadic_function

ajiten · 08-26-2023, 12:15 PM

Also the struct LexData is having no members in line #38, while later on line #434, it has been redefined.
So, why multiple definitions, and which definition would be picked up, by the different references to it.

Line #38:

Code:

typedef struct LexData LexData; /* this type is opaque */

Line #434:

Code:

struct LexData {
    char *from;
    char *lim;
    char *ptr;    /* parsing position as pointer */
    LexPos pos;   /* parsing position as line+offset */
    int eof;      /* flag */
};

NevemTeve · 08-26-2023, 12:29 PM

Answered in post #74
The make it clear:
First we declare a struct and in the same line define a type. The type is incomplete, so only its pointers can be used.
Then, later in the source we actually define the struct, so that we could implement the type's operation.

See also: https://yosefk.com/c++fqa/class.html#fqa-7.5

ajiten · 08-27-2023, 04:27 AM

Hence, such opaque definitions of struct are not for all definitions, say these exist for: LexData, LexPos, LexToken, ParseData; while others are not, say for: ParsTempElem.
Please state why the function: 'sizeof()', & its parameter are not specified in parenthesis.

Code:

memset (&p, 0, sizeof p);

on line #159, inside function: static Exp *NaiveParser(const char *from), on line #155.

NevemTeve · 08-27-2023, 04:37 AM

Becasue `sizeof` isn't a function, it is an operator; it is evaluated compile-time (except for VLAs -- that's another can of worms).
`sizeof` has two formats: `sizeof(type)` and `sizeof expression`. The latter doesn't require parentheses (but you can use still them, if you wish).

Some objects (e.g. functions, data structures) are used internally only, they have only 'local significance', as they aren't part the specification, only the implementation. They can be changed or omitted without notification. Such is ParsTempElem.

On the other hand, some data-stuctures are necessarily public, such is LexToken.

ajiten · 08-27-2023, 01:05 PM

You stated on line #287:

Code:

/* NP_Mul and NP_Add are almost identical,
   they should be wrappers calling a common implementation
 */

Tried my attempt on creating a common implementation with below, though am confused on creating wrapper for NP_Add(ParseData *p), NP_Mul(ParseData *p) :

Code:

static Exp *NP_Op(ParseData *p, int Op) {
    Exp *first= NULL;   Stack *stk= NULL;   ParsTempElem pte;
    int err= 0;

    if (p->token.type==LT_EOF) { return NULL;}
    else if (p->token.type==LT_NUM || p->token.type=='(') {
        first= NP_Pow (p);
        if (first==NULL) return NULL;
    } else {  NP_PrintErr(p); return NULL; }

    stk= Stk_New (sizeof (ParsTempElem));
    pte.op= 0;  pte.exp= first;  Stk_Add(stk, &pte);

    while (err==0 && (p->token.type=='*' || p->token.type=='/' || p->token.type=='+' || p->token.type=='-')){
        int op= p->token.type;
        Exp *next;

        LexGet (p->ld, &p->token);
        if(op == '*' || op == '/')
             next = NP_Mul(p);
        else 
             next = NP_Add(op);
        if (next==NULL) {  err= 1;  continue;  }
        pte.op= op;
        pte.exp= next;
        Stk_Add(stk, &pte);
    }
    
    if (err) {
        int i, n= Stk_Count(stk);
        for (i= 0; i<n; ++i) {
            Stk_Get(stk, &pte, i);
            Exp_Delete(pte.exp);
        }
        return NULL;
    } else {
        int i, n= Stk_Count(stk); Exp *e= NULL;

        if (n>0) {
            Stk_Get(stk, &pte, 0); e= pte.exp;

            for (i=1; i<n; ++i) {
                Stk_Get(stk, &pte, i);
                e= Exp_New(pte.op, e, pte.exp);
            }
        }
        return e;
    }
}

But, couldn't understand why in your code, the function: static Exp *NP_Add(ParseData *p), has the line #380:

Code:

next= NP_Mul(p);

while the function: static Exp *NP_Mul(ParseData *p), has the line #319:

Code:

next= NP_Pow(p);

====================================================================
Also, couldn't understand why line #209 has call to NP_Add():

Code:

else if (p->token.type=='(') {
        LexGet(p->ld, &p->token);
        e= NP_Add(p);    //line #209

in function: static Exp *NP_Elem (ParseData *p), on line #197.
===================================================================
Also, your code gives no error / warnings on onlinegdb.com, as at: https://onlinegdb.com/Q3zaKcvhU.
But, on Visual studio installation, on Windows 10, gives the trivial type conversion errors, with choosing cygwin's installed gdb as the debugger:

Code:

*  Executing task: C/C++: gcc.exe build active file 

Starting build...
C:\cygwin64\bin\gcc.exe -fdiagnostics-color=always -g C:\Users\User\.vscode\nevem3.cpp -o C:\Users\User\.vscode\nevem3.exe
C:\Users\User\.vscode\nevem3.cpp: In function 'Exp* NP_Elem(ParseData*)':
C:\Users\User\.vscode\nevem3.cpp:214:33: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
  214 |                 NP_PrintErrF(p, "*** Missing right parentheses near ");
      |                                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
C:\Users\User\.vscode\nevem3.cpp: In function 'LexData* LexInit(const char*)':
C:\Users\User\.vscode\nevem3.cpp:443:24: error: invalid conversion from 'void*' to 'LexData*' [-fpermissive]
  443 |     LexData *ld= calloc(1, sizeof *ld);
      |                  ~~~~~~^~~~~~~~~~~~~~~
      |                        |
      |                        void*
C:\Users\User\.vscode\nevem3.cpp: In function 'Exp* Exp_NewNum(double)':
C:\Users\User\.vscode\nevem3.cpp:524:19: error: invalid conversion from 'void*' to 'Exp*' [-fpermissive]
  524 |     Exp *e= calloc(1, sizeof *e);
      |             ~~~~~~^~~~~~~~~~~~~~
      |                   |
      |                   void*
C:\Users\User\.vscode\nevem3.cpp: In function 'Exp* Exp_New(char, Exp*, Exp*)':
C:\Users\User\.vscode\nevem3.cpp:531:19: error: invalid conversion from 'void*' to 'Exp*' [-fpermissive]
  531 |     Exp *e= calloc(1, sizeof *e);
      |             ~~~~~~^~~~~~~~~~~~~~
      |                   |
      |                   void*
C:\Users\User\.vscode\nevem3.cpp: In function 'Stack* Stk_New(size_t)':
C:\Users\User\.vscode\nevem3.cpp:620:21: error: invalid conversion from 'void*' to 'Stack*' [-fpermissive]
  620 |     Stack *s= calloc(1, sizeof *s);
      |               ~~~~~~^~~~~~~~~~~~~~
      |                     |
      |                     void*

Build finished with error(s).

 *  The terminal process terminated with exit code: -1. 
 *  Terminal will be reused by tasks, press any key to close it.

Also, please tell where are you running your code, seems on github itself, but am not clear how.

NevemTeve · 08-27-2023, 03:39 PM

Why on earth did you switch to C++? Before you try C++ you should learn this by heart:
https://yosefk.com/c++fqa/

ajiten · 08-27-2023, 11:19 PM

Quote:

Originally Posted by NevemTeve

Why on earth did you switch to C++? Before you try C++ you should learn this by heart:
https://yosefk.com/c++fqa/

Sorry for that mistake, but have other queries too, which are needed to understand your code (in reverse order, from the second last one repeated below):
-----------------------------------------------------------------
Also, couldn't understand why line #209 has call to NP_Add():

Code:

else if (p->token.type=='(') {
        LexGet(p->ld, &p->token);
        e= NP_Add(p);    //line #209

in function: static Exp *NP_Elem (ParseData *p), on line #197.
------------------------------------------------------------------

=====
and the queries above the given one above, in my last post.

==============================================================

For showing the infinite recursion problem, though quite trivial at least theoretically; can be shown by making the grammar of your code, again left-recursive, i.e. make code without the struct ParsTempElem, stated below in line #188 or line#192 onwards:

Code:

/* to solve the left associativity problem, we had to improve
   NP_Add and NP_Mul, i.e. they aren't recursive any more,
   instead they use a stack of 'ParsTempElem'
 */
typedef struct ParsTempElem {
    int op; /* opetator as character: + - * / (pow is not relevant here) */
    Exp *exp;
} ParsTempElem;

Your code has left-recursive grammar, as shown in lines #138-153:

Code:

/* original grammar:
   start -> add
   add   -> mul    | mul  '+' add | mul '-' add
   mul   -> pow    | pow  '*' mul | pow '/' mul
   pow   -> elem   | elem '^' pow
   elem  -> NUMBER | '(' add ')'

   non-recursive grammar:
   start -> add
   add   -> mul    [ {'+'|'-'} mul ] ...
   mul   -> pow    [ {'*'|'/'} pow ] ...
   pow   -> elem   [ '^' elem ] ...
   elem  -> NUMBER | '(' add ')'

   NB negative/positive sign is not handled
 */

NevemTeve · 08-27-2023, 11:44 PM

I've just fixed the C++ specific problems, and added some comments, including the three versions of the grammar: right recursive, left recursive, non-recursive.

Edit: also added functions emalloc/ecalloc/erealloc: they exit on 'Out of memory' error.
Edit2: also added Exp_Delete and Stk_Delete calls not to leak memory

Now I'll admit I've lost track of your questions, please ask them one-by-one.

ajiten · 08-28-2023, 12:54 AM

Quote:

Originally Posted by NevemTeve

I've just fixed the C++ specific problems, and added some comments, including the three versions of the grammar: right recursive, left recursive, non-recursive.

(Edit: also added functions emalloc/ecalloc/erealloc: they exit on 'Out of memory' error.)

Now I'll admit I've lost track of your questions, please ask them one-by-one.

Thanks, will state the issues, one at a time, starting with the most important first (which is the need to show the infinite recursion):

For showing the infinite recursion problem, though quite trivial at least theoretically; can be shown by making the grammar of your code, again left-recursive, i.e. make code without the struct ParsTempElem, stated below in line #188 or line#192 onwards:

Code:

/* to solve the left associativity problem, we had to improve
   NP_Add and NP_Mul, i.e. they aren't recursive any more,
   instead they use a stack of 'ParsTempElem'
 */
typedef struct ParsTempElem {
    int op; /* opetator as character: + - * / (pow is not relevant here) */
    Exp *exp;
} ParsTempElem;

Your code 'now' should have only the left-recursive grammar, as shown in lines #138... (in the new code, i.e. version 4, from line #154-159):

Code:

/* original grammar:
   start -> add
   add   -> mul    | mul  '+' add | mul '-' add
   mul   -> pow    | pow  '*' mul | pow '/' mul
   pow   -> elem   | elem '^' pow
   elem  -> NUMBER | '(' add ')'

   NB negative/positive sign is not handled
 */

Am confused on the working of the code even, so cannot be sure of what to attempt; hence my other questions (in earlier post) were directed towards asking something related to how the code works.
But, re-stating those questions again, would mean that am asking multiple questions at a time.
Hence, you can either ask me to re-state the code working questions, or modify the code.

NevemTeve · 08-28-2023, 01:55 AM

The used grammar is the third one:

Code:

   non-recursive grammar:
   start -> add
   add   -> mul    [ {'+'|'-'} mul ] ...
   mul   -> pow    [ {'*'|'/'} pow ] ...
   pow   -> elem   [ '^' elem ] ...
   elem  -> NUMBER | '(' add ')'

Now it is a bit harder to implement, that's why we use stacks.

ajiten · 08-28-2023, 02:37 AM

Quote:

Originally Posted by NevemTeve

The used grammar is the third one:

Code:

   non-recursive grammar:
   start -> add
   add   -> mul    [ {'+'|'-'} mul ] ...
   mul   -> pow    [ {'*'|'/'} pow ] ...
   pow   -> elem   [ '^' elem ] ...
   elem  -> NUMBER | '(' add ')'

Now it is a bit harder to implement, that's why we use stacks.

Sir, if there is a way to implement instead the left-recursive grammar, and show the infinite recursion error.
I thought that the struct ParsTempElem is the cause, but cannot tell what should be the alternate structure, to instead have a left-recursive grammar.

Edit: Seems my request is premature, as you stated implicitly that recursive call is to be used, hence am thinking on it now. Seems that need not change the given struct ParseTempElem, which is any way not decideing if recursion happens, or explicit stack frames are used.
There should be change in function code instead, ...

NevemTeve · 08-28-2023, 05:19 AM

Oh well, here is a little problem: let's say we wish to implement this rule:

Code:

add -> mul | add '+' mul | add '-' mul

with this function:

Code:

static Exp *NP_Add(ParseData *p) {
   Exp *first;

   /* handle EOF or error */
    if (p->token.type==LT_EOF) {
        return NULL;
    } else if (p->token.type!=LT_NUM && p->token.type!='(') {
        NP_PrintErr(p);
        return NULL;
    }
    /* what's now? should we call NP_Add or NP_Mul?
       Calling NP_Add leads to infinite recursion;
       on the other hand, calling NP_Mul will return an expression,
       but what to do with it? */
    first= NP_Add(p);
    ... /* code after recursive NP_Add will never run */
}

Anyways, this is enough to show how to implement neverending recursion.

NevemTeve · 08-28-2023, 06:12 AM

I've refactored it again, and dropped the stack altogether.

ajiten · 08-28-2023, 08:52 PM

On line #159, it is given:

Code:

-2^-3 is -(2^(-3)) or (-2)^(-3) -- those are different

I see both as -1/8, i.e. for: -(2^(-3)) => -1/8; & for (-2)^(-3) as: 1/(-2)^3 = -1/8.
But, the answers here are different, i.e.: 1, 3 respectively.

Cannot understand the answer at all.