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

ajiten · 08-21-2023, 10:26 AM

Quote:

Originally Posted by NevemTeve

Whenever `malloc` returns something, it is an array. Whenever `strcpy` or `memcpy` is called, it is is a copy between arrays. To tell the truth, C doesn't have string type, it uses character-arrays instead.

Wished (& could see also) if could show by some simple means (like, printf()) the way in which the malloc() returns memory space, and all these are connected in one array; for some given input, say 'ABCD'.

NevemTeve · 08-21-2023, 11:12 AM

https://onlinegdb.com/NClPkNgSH

Added debug-prints into stmt_list,
now here I idendeted the debug lines to show to recursion:

Code:

stmt_list: input='ABCD'
  stmt_list: input='BCD'
    stmt_list: input='CD'
      stmt_list: input='D'
      stmt_list: input='D', first='D' rest=''(array of 0 characters)
      now I'll merge them into another array of 1 characters
      the result is 'D'
    stmt_list: input='CD', first='C' rest='D'(array of 1 characters)
    now I'll merge them into another array of 2 characters
    the result is 'CD'
  stmt_list: input='BCD', first='B' rest='CD'(array of 2 characters)
  now I'll merge them into another array of 3 characters
  the result is 'BCD'
stmt_list: input='ABCD', first='A' rest='BCD'(array of 3 characters)
now I'll merge them into another array of 4 characters
the result is 'ABCD'

ABCD interpreted as left associative: (((A).B).C).D
ABCD interpreted as right associative: A.(B.(C.(D)))

Also remember the terminating zero: is marks the end of the characters. That's why we allocate one more byte every time.

ajiten · 08-21-2023, 03:49 PM

Quote:

Originally Posted by NevemTeve

Infinite loop is very easy to produce, you could have found out it by now:

Code:

/* subexp -> NUMBER | subexp - NUMBER */
int parse_subexp() {
    int left= parse_subexp();
    if (token=='-') {
          token= nextToken();
          int right= parse_number();
          return left-right;
    } else {
          return left;
    }
}

Wanted to build code, on the similar grounds as given by @astrogeek here.

But, could not understand the line #22 (and the initial condition of the for-loop at line #70), in the given code.

Have some skeleton till now, as here.

ajiten · 08-21-2023, 10:08 PM

Quote:

Originally Posted by astrogeek

Indeed, it is universally explained in parsing literature. Have you read those and tried to understand what they are telling you? How would another example from myself be any different? See post #41, from which:

But this problem, like so many in the parsing realm, is inherent in the concept of top-down parsing, not just an implementation detail. As such, it is best understood conceptually rather than as a code example.

Top-down parsing begins with the input string and the start symbol, then performs predictions by replacing the leading non-terminal in each alternative until the left-most symbol in each prediction is a terminal. At that point it matches those terminals with the left-most end of the (remaining) input string, removes those that match into the parse tree and discards the rest of the predictions, then continues with the next leading non-terminals until it reaches the end of the input string.

The problem with left-recursion in this scenario is that you can never reach a set of predictions in which all left-most symbols are terminals. For example (adapted from Dick Grune):

Code:

Grammar:        S -> Sb | a
Input string:   ab

Deriving predictions...

        Parse Tree | Prediction
    _______________|________________
                   |  S
                  ...
                 S |  Sb
                 S |  a
                  ...
                SS |  Sbb
                SS |  ab
                 S |  a
                  ...
               SSS |  Sbbb
                SS |  ab
                 S |  a
                  ...
ad infinitum...

You can never get rid of the leading non-terminal in all predictions, so you can never move to the match phase.

The infinite progression is present in the concept of a top-down parser, not only recursive implementations where it manifests as infinite recursion.

Trying to see it as code alone will not lead to understanding.

Please tell how to interpret the line #22:

Code:

   if((parseptr-parse)>=(MAXPARSE - 1))

and the initialization condition, in the for loop, on line #70:

Code:

     for(char *indx = parse + strlen(parse); indx>=parse; indx--)

The code is on onlinegdb.com, here.

astrogeek · 08-21-2023, 10:50 PM

Quote:

Originally Posted by ajiten

Please tell how to interpret the line #22:

Code:

   if((parseptr-parse)>=(MAXPARSE - 1))

That prevents overwriting the final NULL in the parse buffer, creating an unterminated string.

Quote:

Originally Posted by ajiten

and the initialization condition, in the for loop, on line #70:

Code:

     for(char *indx = parse + strlen(parse); indx>=parse; indx--)

The code is on onlinegdb.com, here.

That initializes the pointer to the end of the parse string. Should be one less actually, but writing the NULL terminator has null effect so no harm done, and is safe for zero length string (indx was originally an int index into array, modified for posting here, oops).

ajiten · 08-21-2023, 11:14 PM

Please see your post on 08-19-23, at 10:19

Quote:

Originally Posted by NevemTeve

Naive top-down recursive parser cannot handle left recursion ( e.g. A -> A - B ), because if it tried, the recursion would never end.
A real-life program can work on modified rules ( e.g. A -> B - A ), create some data-structure (typically a tree) as a temporay result, then transform the data-structure to get the correct representation, e.g:

Input: 2-3-4
Temporary result: 2-(3-4)
Fixed result: (2-3)-4

Please tell how your code does the fixing of the result, in order to avoid the infinite-recursion problem, in left-recursive grammars.

ajiten · 08-22-2023, 12:36 AM

Quote:

Originally Posted by astrogeek

Code:

     for(char *indx = parse + strlen(parse); indx>=parse; indx--)

That initializes the pointer to the end of the parse string. Should be one less actually, but writing the NULL terminator has null effect so no harm done, and is safe for zero length string (indx was originally an int index into array, modified for posting here, oops).

Okay, the variable: parse, would give the start location of the character array. Would need to add just: len(parse)-1.
Though am unclear, what you mean by : writing the NULL terminator has null effect...

NevemTeve · 08-22-2023, 03:54 AM

> Please tell how your code does the fixing of the result, in order to avoid the infinite-recursion problem, in left-recursive grammars.

The program in question is way too simple to show the problem, let alone the solution.
I might come up with an actual example, but it is not trivial.

As a prerequisite, you have to know binary expression trees. Sample:

https://github.com/lzsiga/hello-worl...naive_parser.c

Then move on to lexical parsing (same program).

ajiten · 08-22-2023, 08:37 AM

Quote:

Originally Posted by NevemTeve

> Please tell how your code does the fixing of the result, in order to avoid the infinite-recursion problem, in left-recursive grammars.

The program in question is way too simple to show the problem, let alone the solution.
I might come up with an actual example, but it is not trivial.

As a prerequisite, you have to know binary expression trees. Sample:

https://github.com/lzsiga/hello-worl...naive_parser.c

Then move on to lexical parsing (same program).

Request some details on your statement regarding the insufficient complexity of the program, in order to show the infinite loop problem, for left-recursive grammar.
This can be used by me to elaborate to class as well, the need for the given program.
Am in process of understanding code, so if you feel that would acquire the knowledge on understanding the program, then no issues; though see no hope for that.

Also, why the function prototype declaration on line #32, 33, 34 is repeated on line #44, 45, 46; is unclear.

Code:

static LexData *LexInit(const char *from);
static int LexGet(LexData *ld, LexToken *into); /* returns into->type */
static void LexTerm(LexData *ld);

NevemTeve · 08-22-2023, 08:44 AM

You're late, by now it has been improved, it has a naive parser now, here is an example showing the problem:

Code:

NaiveParsTest: input="96 / 2 / 3 / 4"
Result: (96/(2/(3/4)))

It should be (((96/2)/3)/4)

Now back to your perpetual request: I most certainly won't add infinite recursion into the program, do that yourself. You have been given examples, e.g. in post #45

Please learn the current state of the program by heart.

astrogeek · 08-22-2023, 11:04 AM

Updated example in blog post renames loop pointer and corrects offset.

Quote:

Originally Posted by ajiten

Okay, the variable: parse, would give the start location of the character array. Would need to add just: len(parse)-1.
Though am unclear, what you mean by : writing the NULL terminator has null effect...

It means what it says, how do you interpret it?

NevemTeve · 08-23-2023, 04:14 AM

I'll admit, my first idea to fix the associativity problem failed. The second one uses stacks, and I think it sort of works.

Code:

$ ./naive_parser "2+3-4+5-6" "2*3^3*4^4^5"

NaiveParsTest: input="2+3-4+5-6"
Result: ((((2+3)-4)+5)-6)
Result: 0

NaiveParsTest: input="2*3^3*4^4^5"
Result: ((2*(3^3))*(4^(4^5)))
Result: inf

It doesn't support signs yet (+3, -5), which might also be interesting, e.g wether -3^2 is (-3)^2 or -(3^2) (I support the latter, but have heard arguments about it.)

ajiten · 08-24-2023, 08:04 PM

Quote:

Originally Posted by NevemTeve

You're late, by now it has been improved, it has a naive parser now, here is an example showing the problem:

Code:

NaiveParsTest: input="96 / 2 / 3 / 4"
Result: (96/(2/(3/4)))

It should be (((96/2)/3)/4)

Now back to your perpetual request: I most certainly won't add infinite recursion into the program, do that yourself. You have been given examples, e.g. in post #45

Please learn the current state of the program by heart.

Sorry, due to internal examn. was too busy for few days, as couldn't adjust to different tt.
Please tell why the struct LexData, is empty, as how an empty datatype can be a parameter, as well as a return data type, as on the lines #40-42.
Have read here, but couldn't find something relevant. Any hint will work, in kicking in the right direction.

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

This is called `opaque type`. It's not important in this little program, but in multi-file projects it is useful: implementation can be separated from the specification.

Line 38 declares 'struct LexData' then the definition is in lines 434-440

In a bigger project, lines 415-501 would be in a separated file called `lex.c`

Also here: https://c-faq.com/struct/sd1.html

ajiten · 08-26-2023, 09:12 AM

Quote:

Originally Posted by NevemTeve

This is called `opaque type`. It's not important in this little program, but in multi-file projects it is useful: implementation can be separated from the specification.

Line 38 declares 'struct LexData' then the definition is in lines 434-440

In a bigger project, lines 415-501 would be in a separated file called `lex.c`

Also here: https://c-faq.com/struct/sd1.html

Please state why on line #172, the function has ... in the parameter list?

Code:

static void NP_PrintErrF(ParseData *p, char *fmt, ...) {