[ocean-D] / twod

How to write up two-dimensional parsing?

What does the code do?

- If an indent is ignored the matching undent is ignored
  except to decrement the 'ignored' stack and to turn
  a pending indent into a pending newline.
  or to count the pending undents.

- If a newline is found and cannot be shifted yet then we check
  each production that would close before we shift, and if any still
  have pending undents, we ignore the newline

- when we reduce a production, we 'resolve' indents wich may leave
  something pending. Either an indent or a number of undents?

- productions can be recursive if first body symbol matches head.
  A recursive production may be horizontal if it starts in the middle
  of a line. non-recursive productions are always horizontal.
  A horizontal production must be all on one line or have its body
  indented.
  A vertical production must not be indented.


Maybe I don't want to mention indents in the grammar ?

 if CONDITION : STATEMENTLIST

doesn't have to be indented but we will only reduce it when we
see something that doesn't belong.... which could be an UNDENT

So: when look-ahead is UNDENT we cannot shift so we reduce until
the top state has an indent attached, at which point we consume the
UNDENT.

 if hello :
    foo
    bar
    bar
 UNDENT

the undent will reduce until we just have the ifstatement which
contains an indent.
So any indent is pushed onto the stack and a reduction sums all the
indents.

What about newlines?  A newline will reduce any production that
doesn't contain an indent.  It gets discard when top of stack
was at start of line...

So each 'state' also encodes
   start-of-line or middle-of-line
 and
   count of indents.

When an INDENT is seen the current state increments count of indents.
When an UNDENT is seen we must reduce until tos state has an indent,
which we decrement.
When a NEWLINE is seen, we reduce until tos state has indents or was
at start-of-line.

nononono
UNDENT shouldn't force a reduce.  Only newline should do that.  But as
an undent is always followed by a newline, it still results in a
reduce happening where I want it.

So an undent shifts in line an indent(?).  Reduction nets the indents.
A newline forces the reduction until we find excess indents.

But what does grammar look like?
 statement -> assignment ';'
           | assignment
So a newline will force the reduction to 'statement', but this will
allow
    a = b c = d
which looks bad.  So:
 statement -> assignment ';'
           | assignment NEWLINE
Then the NEWLINE can be shifted normally.
So newline forces reduction until it can be shifted or until ToS
contains an indent or started on a new line.
If we hit an irreducible state that does not accept NEWLINE when we
have to shift in an ERROR instead which might then be reducible.
When popping states we need to collect the indents.


Where do we attach the indent/undent info?  To the state or to the
symbol?  They are kept together but mean different things.
indent/undent are between terminals, just like states.  But they
can be inside non-terminals which make them unlike states.

What "is" a state?  It is a point between two symbols in a sentential
form.  It doesn't carry information.  So I think the indent has to go
with a symbol.
An 'indent' should attach to the symbol *before* it as that is the
thing that is being continued.  An 'undent' should also attach before
itself.  Eventually those two terminals become included in a single
non-terminal and they collapse.
You can never have more undents than indents as a newline will force
reductions until top symbol has no undents.
In fact we reduce until the top symbol has a new indent, or is a
vertical production, or is explicitly allowed.

If we see an INDENT, we attach to symbol at ToS
If we see an UNDENT, we attach to symbol at ToS (possibly canceling indent)
If we see a Newline and current ToS holds +ve indent,
   we ignore it
If look-ahead is expected, we shift it.
If we can reduce, we do so.
Else we trigger error handling:
 pop states until one accepted ERROR - collecting indent
 shift ERROR with those indents
 Discard input, but process indent/undent, until next symbol is
 expected.
 continue.


Does this work?  If I have
  a = b +
      c +
      d

Then the NEWLINE after "c +" cannot be handled, but should not be an
error.
Stack would hold
   var = expr +
where 'expr' contains an indent.
Maybe NEWLINE is ignored unless ToS has negative indent.
  a = b +
      c +
    d
That must be an error.

Problems:
 1/ accepting NL must depend on what it will reduce.
 2/ If UNDENT/INDENT appear together they must be kept separate.

So maybe UNDENT does block shifts and so forces reduction.  If not
reduction can be made, that is an error

if (a) {
  b;
}

The NL UD NL before '}':
  NL will ensure "b;" is reduced.
  UD will reduce to command-list so we will have

  if ( expr ) { commandlist
where '{' holds the indent.  So '}' needs to bring in the undent,
which is after another NL.

So Undent waits for a symbol to collect it when shifted.

What when I have:
   if (a) {
       foo;
   while (b)
       bar;

When we try to reduce "foo;while(b)bar;" to "statementlist" the
negative indent triggers an error.  This a bit late though.  I want it
when I see the 'while'.  I want an error there which can be reduced a
closed statement.
The undent should close the statementlist so that '}' is the only
shiftable symbol.  But after 'statementlist', 'while' is still
permitted.

If we just waited for the 'while' statement to reduce and then noticed
the error, we could still report it against the 'while' token, but
recover would be a lot harder as we have already parsed the 'while'
into the 'wrong' place.

So when I see that token after NL,UD,NL, I need to be able to say
'yes' or 'no'.
Could require help from grammar.
e.g. if a token is allowed to have a lesser indent than previous
token, then there must be a literal UNDENT token.
Or we could require:

 Block -> BlockA }
 BlockA -> { Statementlist

That looks ugly, but the undent would close BlockA and allow the } to
be expected.
Or maybe

 Block -> { Statementlist OptNewline }

so the newline after the indent is shifted and doesn't
reduce-or-error.

Then the UNDENT would ensure that the Statementlist were closed, the
Newline would be shifted, only a '}' would be allowed.

So: each symbol in a production must be in the same line as the
previous, or in an indented line.

No.  OptNewline there wouldn't work as a blank line would take us to
expecting a '}'.

I think I need to go back to what works... only it doesn't?


Indent is attached to previous symbol. I think that is easier that
keeping it at the 'start' of the 'next' symbol as I was doing.

Newline closes any productions that don't include an indent, then can
be shifted if wanted, or ignored.

Undent reduces things until ToS has an indent that can be canceled.
This means that if part of a production can have a negative relative
indent, it must be separate:
Block -> Blockhead }
Blockhead -> { Statementlist

So the Undent before the '}' will reduce Blockhead and can then be
discarded.
We would add
Block -> Blockhead ERROR

It would be nice if that can be auto-handled. e.g.

Block -> { Statementlist $undent }


leads to the above.
That would be messy for the reduce action though.
Could each state "know"

--------------
A state can have different items with different offsets, so how much
of the stack is part of the 'current' production is not well defined.
It is not completely random either.

We can ignore non-kernel items as those are just potential productions
- they haven't started yet.
Of the remainder, many states have only one length.
Many others will have some offset and '1' for recursive
 productions: A -> A . X
These can be called "potential" as well as we have no commitment.
What is left?
  Funcall -> Factor . ( ExprList )
  Term -> ~ Factor .

  Funcall -> Factor . ( ExprList )
  Term -> Term * Factor .
etc

i.e. just the bits that make the grammar distinctively LR.
In my case one is always reducible, is that important?

So when we see an Undent we find the max-index of the current state
and determine if there is a matching indent within that distance.
If there isn't then we must reduce or trigger an error.

Alternately:  Each 'goto' from this state has a max-history.
We exclude any that don't have enough history to include balanced
indents.
If the next symbol would trigger one of those, it is an error.

So:
 For early error detection we record Indents against the previous
 symbol, ignore newlines, and when we see an undent the next shift
 must lead from a core item with enough history to keep balance.

If that is well defined it might catch early undents, but what about
unneeded indents?
   a = b + c;
       c = d + e;

I expect that is less likely, but still an error.
When we see the first ';' we will reduce to a statement and then a
statementlist.  The second 'c' would lead us from
  statementlist -> statementlist . statement
which is recursive and so doesn't allow indents (unless it started in
the middle of a line).

Intends are allowed anywhere except after the first symbol of a
left-recursive production which started at beginning-of-line.

a = b +
    c
      * d;

is not allowed as 'Term->Term*Factor' is left-recursive.  But why not?

So maybe an indent has to be allowed anywhere.  Maybe a warning but
there is no real recovery option.

An undent is allowed in a state with a history back to the matching
indent.
If we see an undent, we check if the state can consume it.  If not we
look to the next symbol which is not an undent (or newline) and reduce
until that symbol can be shifted.  At this point the undent must have
been consumed.

Or easier:  We must reduce to the matching indent before we shift,
unless a NEWLINE is explicitly allowed...

Take 1:
 An indent is between two symbols, or within one symbol.
 We hold a pending indent which gets attached to the front of the next
 symbol that we shift.
 Undents and newlines collect until we see a "real" symbol.
 Any reductions that are then indicated happen and if the ToS symbol
 is found to hold an indent, that cancels a pending undent.
 Once we get to a state that can shift the lookahead we examine the
 number of pending undents.  It should be zero. i.e. we shouldn't
 still be in the middle of a non-terminal that started at a greater
 level of indent.

 If it isn't zero we trigger an error because a close-bracket or
 similar is missing.  This might be different to "unrecognised-error"
 The error should lead to reductions which cancel out the remaining
 undent.
 I think the parser needs to incorporate error handling into states.
 Each state knows what symbol to synthesis to get closer to a
 reduction.
 i.e. on 'no close' error, we reduce what we can, and synthesis when
 we cannot.

So that seems to handle early undent.
We also have 'unexpected indent', 'missing indent' and 'late undent'.


A 'missing indent' happens when a production that we expect to be
one-line sees a newline rather than an indent.
i.e.
     a = b
     + c;

The + after the newline only reduces 'b' to Expression which starts
in the middle of the line.  A newline should see a reduction to a
nonterm which started at the beginning of a line, or which contains an
indent.

We trigger a 'no close' error here so that '+' is the start of a new
statement.  Maybe if the next symbol is shiftable, we just report an
error and allow parsing to continue;

An 'unexpected indent' happens when the fully reduced non-terminal
started at the beginning of a line and is a recursive non-terminal.
Or maybe we are in a recursive state.  This triggers an error

A 'late undent' is like an unexpected indent.  The previous
fully-reduced non-terminal is recursive, started at the beginning of a
line, and still contains an indent.

------------------
Each symbol can carry a 'start-of-line' flag and an 'indent' count.
Each state may be flagged as 'recursive' if "A -> A . etc", and
records the symbol to synthesise to resolve a 'missing' error.

Current state includes an undent count, a nothing/newline/indent flag.
When look ahead contains undent, we increment that count
When look ahead contains newline we set newline flag
When look ahead contains indent, we set flag to indent.
When we reduce we combine indent counts in symbols and keep
start-of-line from first symbol.
If the ToS after a reduce contains indents and current state contain
undents, they are reduce so that one becomes zero (min is subtracted
from both).
Before we shift we must test:
- if undents are non-zero, we synthesis the symbol expected by the
  state, we keep synthesising and reducing until the undent count
  reaches zero.  We report that the synthesised symbols were missing.

- If newline flag is set, the ToS symbol should start at SOL or
  contain an indent.  If it doesn't we just report a missing indent
  error.

- If indent flag is set and ToS symbol started at SOL and state is recursive
  we report an unexpected indent.

- If state is recursive and ToS started a SoL and contains an indent,
  we report an extra indent.


---------------------
(I think I'm getting there).
Hypothesis:
  An indent is allowed in a non-recursive that started on a newline,
  or in a recursive (at the recursion point) that didn't.

  The matching undent must be at the end of the production.

  A newline is only allowed in a production that started at the start
  of a line, but not always. - only if recursive or annotated.

  An undent is required at the end of a production that contains an
  indent.


  An indent or newline found where not "allowed" generates an error
  but no recovery.
  An undent not found where required generates an error and emergency
  reductions.


If we have an ambiguous grammar then the undent could simply
force a reduction. i.e. if the 'emergency reduction' just involves
choosing REDUCE of SHIFT, then it isn't an error or even a warning.


But where exactly is an indent or newline allowed - I don't think I
have this right.
 - a newline is definitely allowed in a list that started at the
   beginning of a line.  We need to structure the production right
   so we don't end up with a separator at the start of a line.
      LIST -> LIST SEP ELEMENT
           -> ELEMENT
   would need to allow the newline before ELEMENT.  The logic there
   would be that if the first ELEMENT can be at start-of-line, other
   ELEMENTS can too.
      LIST -> LIST ELEMENT
           -> empty
   Is appropriate if no separate is needed, and an empty list is OK.
   Here ... does the indent go after the LIST or before the ELEMENT?
   i.e. if there are more symbols, how do we know.

   If the list already has an indent, then from there on it "started
   at the beginning of a line"
   This is treating it a lot like LL(1) which would be:
      LIST -> ELEMENT LIST
            | empty

      LIST -> ELEMENT SEP LIST
            | ELEMENT

 - a newline is definitely allowed in a non-list which has already
   been indented.
      for (i=0;
           i<10;
           i++)

      a = b +
          c +
          d;

   So: whatever holds the indent can also hold a newline.

   i.e. a production can have a newline between symbols if an earlier
   symbol has an indent before it.
   This would allow
    a = [ b
        , c
        , d ]
    which is probably OK.

    What about indents?  Can I have two indents in the one production?
    No, I don't think so.

    If an indent occurs *inside* a production, newlines can appear
    later.
    If an indent occurs *in front* of a list production, newlines can
    appear later.



So (again!)
  a symbol (on stack) can have an indent at the start, and can have a
  number of indents within.
  When we shift the first symbol after an indent, it gets an indent at
  the start.
  When we reduce the result inherit and indent at the start, and other
  indents (within and at start) become within.
  The indent at the start of a list can be treated as being within.
  i.e. as list has an empty symbol at the from before the indent.

  A newline is permitted if the max history for the current state
  contains an indent.  Indent at start of non-list doesn't count.  At
  start of list it does.
  An indent is permitted if the max history does not contain an
  indent.

  An undent cancels indents within, or possibly before, the
  immediately preceeding symbol.


Can I do all lists with empty start?

  // simple list
  LIST -> LIST ELEMENT
        | empty

  // non-empty list
  LIST -> LIST0 ELEMENT
  LIST0 -> LIST
        |

  // non-empty with separator
  LIST -> LIST0 ELEMENT
  LIST0 -> LIST SEP
         |

  // can be empty, sep is needed
  LIST ->
       | LIST1
  LIST1 -> ELEMENT
       | LIST1 SEP ELEMENT

  Just stick "IsList -> " in front of anything that is a list.


For newline to be allowed, do indent have to be between symbols in
same production, or is within symbol ok?

if ( a =
     b )   // now I need another indent.. or an undent?
  x = x + 2;

The undent resets, then only an indent is allowed.
if ( a =
     b )
        x = x + 2;

No reset, so extra indent.  Anything is probably OK except newline.
So the indent cannot be inside a previous symbol.
But for lists, the indent will be exactly inside LIST.
So maybe inside first symbol is OK ??
 x[a+
   b] =
   c

 x = [ a, b, c,
   d, e, f
 ]


I think I might be trying too hard.  I should allow newlines
and indents anywhere, and give a clear interpretation for undents.
However my real goal is to know exactly what newlines and undents mean
and how to parse them.
i.e. does the grammar need to mention all of the, some of them, or
just be ambiguous and allow line break to disambiguate?

That last options doesn't really work as we cannot allow a separator
to be dropped anywhere by at end-of-line or before-close.
So grammar needs newlines.  Various separators can be "sep or newline".
However I don't think indents need to be mentioned.
  if condition : statementlist
needs undents to disambiguate I don't need to say that.

So:
 - indents get shifted with token
 - indents are grouped by reduce
 - and undent reduces until a matching indent in the top
   state can be cancelled.
 - newlines are messy.
   We look ahead through possible reductions until we
   either shift the newline or find an indent or cannot reduce.
   If the shifted newline would not contain a newline in the production,
   we choose that path.  If we find an indent, we discard the newline.
   If we cannot reduce we again ignore the newline
   We could also discard a newline early if not in LA set.


But then:
   if x :
     a = b +
     c = d

Looks to the compiler like an addition and to the human like two assignments.
     a =
         b +
         c +
         d +
?? Only allow newline if production started with indent.
So:
   If not expected and current production contains indent, discard.
   If not expected and current production has no indent - error, recover.
   If expected, test-reduce and discard if indent found else accept.
Not quite.

What if we just test-recover until we hit an indent or want to shift the newline?

Difference between statements and expressions is that a statement can
be terminated by a newline.
So if we find a newline and test-recover would use it, that is an
error.
If we find a newline and test-recover would not use it before an
indent, it isn't an error.

So each state which cannot reduce has a link to the best state to shift to.
When we want to recovery we follow these links until they run
out. Then we can reduce which leads to a new state.

If we find a newline, we do this until we find a state which will take
a newline, or we cross an indent.
If we crossed an indent, we discard the newline.
If not and we has to take any shift steps, we call an error.
This requires that newlines aren't buried to deep.

If we find an undent, we do this until we have cancelled the undent
against an indent.  If anything was shifted, we report an error.

No - using indent just to disambiguate an ambiguous grammar doesn't
work as it still allows confusing constructs.
   if foo:
     bar
     else: baz
Should be wrong as the 'else' looks to be part of the statement but
cannot be.  It should be "unexpected".  That really means that
"INDENT" "UNDENT" must be part of the grammar.
So:
   if COND : INDENT STATEMENTLIST UNDENT
which is where I started.

So an indent which is not expected protects all newlines and
indent/undent pairs until the matching undent.... not quite.

Indents can be expected in a state (if we compute lookahead).
If an indent is not expected we simply discard it and keep count.
When we shift an expected indent we push the count with it.  When we
push the matching undent, we restore the count.
When we get an undent, we discard it if indent count is non-zero.

When we get a newline we look ahead to see if it would reduce across
an indent.  If so we discard the newline.  If not we keep it.

But an undent still needs to force reductions doesn't it?

i.e. if an undent doesn't cancel against top of stack we count it.
If we every try to shift while an undent is present, we throw an error
and shift other stuff until the undent is gone.


Indents must affect error handling.  We no longer just discard tokens
left and right.  The 'error' state for any indented token is the
matching undent.  So we discard stack tokens until we get an error
state or an indented state.
If error, we shift the error and discard input until a token
  matches.  While discarding input we track indent/undent and
  if we come to an unmatched undent we discard stack tokens again

If we hit an indented state we discard input until the matching undent
arrives.

But do we really want to discard tokens, or can we synthesise tokens?

Discarding is standard.  It gets to a known position.  It allows any
location in a production to accept errors.
However discarding does discard data that cannot get further analysis.
If we use very fine grained error productions we might not miss much.

Come back to this later.  For now just discard.

If we find an Indent on stack, an error "must" be expected.
i.e.
  block -> : INDENT Statementlist UNDENT
  Statementlist -> ERROR

So:
  if we can shift ERROR, we do,
  else if



Indents and newlines.

Indents and newlines can be taken as strong syntactic marker, useful
both for regular parsing and error recovery.
Unlike other bracketing markers such as parentheses or paired key
words (BEGIN and END or DO and OD) indents cannot be lost.  Every line
displays what the current indent level is and for every indent there
is precisely one location where the matching undent is (though
of course one location can have undents for multiple indents).

Similarly start-of-line and end-of-line can be strong bracketing
markers which cannot be missed.

The two can complement each other to provide a very effective
indication of the grouping that the programmer intends.  Often the
programmer will want more explicit marking as well (e.g. "{" and "}" )
which is perfectly fine as redundancy of expression is an important
part of effective communication and this is equally true in writing a
compute program.

The connection between the two is simply that indentation effects a
continuation of the previous line. For example in

   A B C
      D E

Any bracketing implied by sol/eol should  not be imposed around "A B
C" but only around "A ... E" - the indent effectively hides the line
break.
So this could be tokenised as
  sol A B C indent sol D E eol undent eol

Note that every SOL has a matching EOL and every INDENT a matching
UNDENT.

As these markers are strongly paired they can be useful for error
detection and recovery.  This is particularly true for indents.

It seems universally true that any syntactic unit (such a declaration,
statement, or expression) which starts indented will finish while
still indented. That means it will complete before the undent which
matches the most recent indent when it was started.

This fact is helpful but not quite as strong as we might like
For example, in

  A B C
     D E
  F G
 H

"F G" could be in the same syntactic unit as "A..E".  however if "D"
started a new subunit, "F G" certainly aren't part of that.
Assuming that "A" started a syntactic unit, "H" is the first symbol
that is clearly not part of it.
This isn't really a problem for
   if condition :
          foo;
          bar;
   baz;

as the statementlist is the last part of the if-statement, so
there is no room in it for baz - baz must be separate.
However in

    a = b + c
        + d + e
        + f
    + g + h;

This looks wrong but cannot be ruled out on the grounds of
indentation.
Here the expression of
     statement -> var "=" expression ";"

starts on the same line as the statement so there is no indent.

We could argue that a syntactic element (expression) that stated other
that at the start of a line may only continue to the end of that line
(when adjusted for indents).  This can hit problems with:

  if condition {
      foo;
      bar;
  }

Here the "block" of
   block -> "{" statementlist "}"
starts other than at the beginning of a line, but continues on the
next line.

There are a few different ways we could try to deal with this:

a/ some special-case marking in the grammar to say that a newline is
   permitted before the '}'
b/ Don't make a separate syntax element for "block":
     ifstatement -> if condition { statementlist }
    would mean that the '}' is at the same indent as the 'if'
    which starts the element.
c/ decide that the last terminal of a production is a special
   case and can go on a new line.

The last is almost certainly a bad ideas it would encourage
    a = b
    ;
and discourage
    if foo then
       stuff
    end if

Another construct that is often used is:

  if condition
  {
       foo;
       bar;
  }

where the "block" is allowed to start on a new line.
This potentially encourages 'block' to be a separate syntactic unit,
so 'b' above doesn't seem encouraging.  That leave 'a' and marking
both the '{' and the '}' as being allowed to start a new line


If we assume these markings, then an undent can close any syntactic
unit that started at a greater indent, or at the same indent but not
at start of line.
We can use this:
 - to detect errors by reducing early and then ensuring the next
   token is expected.
   e.g. the indent after 'bar;' would close the statementlist after
   which only a '}' is expected.  If it isn't there, that is an error.
 - to handle ambiguous grammars.  In the classic
        statement -> if ( expression ) statement
                   | if ( expression ) statement else statement
   the normal default is to treat 'else' as right-associative.
   Using indents:
      if (x)
         if (y)
            foo();
      else
         bar();

   can be parsed with the 'else' applying to the 'if(x)' as you would
   visually expect.


Now we turn to line markings - sol and eol.
The above suggested that any unit should be "on one line" (allowing
for indents) unless specially marked.  This is bit excessive.
For example
   a =
       b + c
       + d;

"b + c + d" is all one expression, but appear on two lines.  Might
seem unlikely, but
   a[some_long_expression_with_function_call_etc] =
      verylongling + otherverylongthing
      + moreofthesame;

might not seem so unlikely.  This could easily be made correct by
moving the '=' to the start of the second line, or indenting the third
line slightly.  It isn't certain that we want to do that, and
annotating that a newline is allowed before the 'plus' seems clumsy.

An alternate approach involves noting that 'statements' are rather
special.  Not uniquely special but still special.
That is, statements are normally on one line.  When they are two long
for a line the remainder is indented (make it part of the previous
line).
When a statement appears on multiple lines it is a notable exception.
For example the  Python

   if condition:
      statementlist
   elif condition:
      statementlist
   else:
      statementlist

has three lines in one statement.  This is a one-line statement which
has newlines before the 'elif' and 'else', or maybe 3 one-line objects
which can come together.

While a statement is line-based, and expression probably isn't.  They
tend to appear all on one line, but that is because the statement they
are in does.

In some sense the line-nature of the statement "captures" the
expression.  An expression can only be on multiple lines if they are
all indented with respect to the containing statement.

So rather than marking some things as being allowed to continue to the
next line, we can mark some things as being line-shaped.  These are
sometimes whole units and sometimes parts. e.g.

  if ( condition )

  {  statementlist

Note the missing '}' above - it is not part of the line shape.

  if condition : statementlist

  else: statementlist

  function name(argumentlist)

  lval = expression ;

and so forth.

Being line-shaped just means that it must be "all on one line", but
not that it must be a line by self.  Several line shaped things can
appear on a line

   a = a+1; b= b-2;

However it would be nice to allow a syntax modification when separate
lines are used. i.e.
   a = a + 1
   b = b - 2

The trailing semicolon is not needed.  As the assignment is
line-shaped it must finish at the end of the line.
Declaring the semicolon to be optional would allow
   a = a + 1 b = b - 2
which looks more like an error than a correct construct.  Here the
semicolon is need.

A simple solution is to allow the NEWLINE to be part of the syntax
listed for the grammar:
   OptSemi -> ;
           | NEWLINE

Then
   Assignment -> lvalue = expression OptSemi

as a line-shaped item should work.



1/ If a point is 'newline allowed' then what follows can go
   on a new line
2/ If something is line-shaped then linebreaks may only be intended.

So in a production we can have 'optnewline' or 'optsemi'
anywhere but at the start.  Or maybe 'at the start' means something a
bit different.

  statement -> if condition optnewline block
             | if condition optnewline block optnewline else optnewline block

  block ->  : statementlist
        |  { statementlist optnewline }


If something is line-shaped, then the EOL that ends the line on which
it starts, must end the thing.
If something is not line-shaped, then an EOL can be safely ignored.

An LR state can expect NEWLINE if it has a goto state for it.
And it has an indent.

If we look up the stack and find an indent before a newline-expected
then a newline is ignored.
If we find a newline-expected before an indent, the newline is used.
If a state expects a newline and was indented then the newline
expectation comes last, is seen first when looking back, so newline is
used.

Separately, an undent reduces until it can cancel with an indent.



but what about
   a = 1 + (3 *
            4 + 2)
   b = 1 +
       3 * func(a, b,
                c, d)

This isn't so much about whether an indent is present, as how much of
an indent there should be.  This sort of indent doesn't affect parsing
or help with error recovery so it is probably best left to esthetics.
We could possibly require that everything in the brackets be indented
w.r.t. line on which the brackets started so that

   b = 1 +
       3 * func(a, b,
       c, d)

would not be allowed.  However we would need to ensure that
   b = 1 +
       3 * func(
       a,b,c,d)
were allowed (I think)


I've got the UNDENT reduce a bit wrong.
Anything that started with an indent must be reduced, not just one
thing that started there and everything after.
This is awkward as reducing back to 'statementlist' doesn't stop
adding to that statementlist, but it should.  So we want e.g.
  statementlist -> statements
   statements -> statements statement
              |
Then we reduce back to 'statementlist' which cannot accept another
statement.   The parser generator could insert these extra non-terms
automagically.
No that's not quite it either.  If I have
   a;
   b;
    c;
   d;
then the undent after 'c;' needs to reduce the statement (which
is already reduced) but not the 'statementlist'.  But there is
no extra state there.  We aren't reducing back to a state, but back to
a symbol.  The indent happened after a statementlist

A recursive symbol A is a problem if:
  A -> A B
and
  X -> ?? A Y
for non-empty Y.  This results in a state:
   X -> ?? A . Y
   A -> A . B

If the Y is empty, X will reduce and B becomes unshiftable.
If this pattern is found we can create A'

  X -> ?? A' Y
  A' -> A

Now 'A' only appears at the end of a production so there is no
problem.


Got it wrong again ...

   foo
   bar
    baz
    bat

after 'bat', the recent indent is in Statements which makes it look
like we need to close all of Statements.  But we don't.  As the indent
stated in the middle of Statements we only need to close to it.
So we really do need to know if an indent is at the start or in the
middle.
We can cancel an 'in the middle' as soon as we find it.  We can only
cancel an at-the-start when reduce_size > 1 (as it is now 'in the
middle').



Now back to newlines.  It doesn't work very well to include newlines
in the grammar wherever one is allowed as it conflicts with where they
are required. E.g. for ';' to be optional we sometimes require one at
the end of a statement, but for statements to be line-like we need to
allow one at the start

I think we need to allow NEWLINE in the grammar for EOL markings.
Maybe we want SOL too?

The important cases are:

  a = b *
      c +
      d;

Statement is line-like so return to SOL not allowed, but expression is
not to return is.
  if condition:
     statement
  else:
     statement

Both 'if ..' and 'else..' are line-like
  a = b + c

Newline at end of this line is allowed in place of ';'.

If we have the grammar recognise all newlines that are not protected
we need to support blank lines in lists.
 Statements -> Statements OptNL Statement


No, I don't like that.  EOL should be at the end.

Some things can have an EOL at end, either optionally or required.
Or elsewhere in the production.

When we see an EOL we need to ask "Do I ignore this or use this?".
The answer relates to indents and expected newlines.

If a symbol can derive a sequence with an EOL, then the symbol is
flagged can-eol.
If that symbols after DOT in any item in a state are flagged
'can-eol', then the state is flagged 'can-eol'.
If a 'can-eol' state appear on the stack closer than a 'was indented'
state, the we use the EOL token.
If no states up to the first 'was indented' state are flagged
'can-eol' then we discard the EOL token.


That might work, but have I thought of all the issues?
 - blank lines.  The grammar will need to allow for these explicitly
      in any context where EOL is expected.  Not a big burden I guess.
 - force reductions ?  If EOL closes things, does it close anything
     where not explicit?  Probably not - that is sort of the point.
     If it appears where not expected but in line context, that is an
     error just like an "unexpected" error.

 - is the nesting 1-way?  i.e. can I have line-oriented things in
   noline boxes.  or "vertical stacks in horizontal boxes"?

   A possible example is a function call.  It might be nice to allow
      a = b + func(first
                   second
                   third) * 2

   There are two problem here.
   Firstly there is no EOL after 'first' so that cannot mark the end
   of an argument.
   Secondly it forces an EOL interpretation on surrounding expressions.

   And what about
     a = [1, 2, 3
          4, 5, 6
          ]

   I would like to be able to drop the ',' after the '3' but it isn't
   clear that it is safe.
     a = [1, 2, 3
                +4
                +2
          8, 9]

   Is a bit forced but with clear intent.  I think it could be deemed
   as wrong because the think that wraps is not the first list element
   on that line.  Is that a well defined concept?











   Recording the line structure allows for a number of different options.  As mentioned already, a "NEWLINE" at the end of each line might do it.  However as "IN" and "OUT" already imply a line break, we could just have "SAME" on breaks which don't have "IN" or "OUT".  However this doesn't capture the idea that a line sometimes corresponds to a syntactic unit.

Another approach is to follow the bracketing nature of "IN" and "OUT"
and have "SOL" and "EOL" for start-of-line and  end-of-line.  As we
noted already an indented section implies continuation and so should
delay the end of line.  If we follow this idea, the above structure
could be tokenize as:




Here every "SOL" has a matching "EOL" but it can be delayed until after an indented block. So the  "EOL" that matches the first "SOL" comes after the "OUT". It is worth noting here and a single line break can have multiple "OUT"s and  even an "IN" as well.

A B C
  D E
   F G
 H
I

After the "G" we would have "EOL OUT EOL OUT EOL IN SOL" before the "H".  The three "EOL"s terminate the lines that start "F", "D", and "A" in that order,  and a new "IN" is needed as "H" is indented with respect to "A".

This tokenization captures the structure very effectively and is what
I will be using with one simplification.  The  "SOL" really isn't
needed.  It is easily deduced and doesn't have a strong effect on the
parser.  The "EOL" may for a syntactic element to be closed.  The
"SOL" is simply recorded for reference, and that can be recorded when
"IN" or "EOL" is seen ("OUT" is always followed by "IN" or "EOL", so
"OUT" doesn't need to imply "SOL").

This tokenization captures the structure very effectively and is what I will be using with one simplification.  The  "SOL" really isn't needed.  It is easily deduced and doesn't have a strong effect on the parser.  The "EOL" may for a syntactic element to be closed.  The "SOL" is simply recorded for reference, and that can be recorded when "IN" or "EOL" is seen ("OUT" is always followed by "IN" or "EOL", so "OUT" doesn't need to imply "SOL").

Unsurprisingly, these are exactly the tokens that can be generated by the scanner I previously described though the token names have been changed.



When does an EOL actually mark and END.

Now that we have a good understanding of IN and  OUT we can turn to EOL.  Intuitively EOL should mark the end of something much like OUT does.  But what.  Let's look at some cases:

if a == b:
    print "Hello"
    print "World"

Here there are 3 EOL tokens, one after "Hello", one after "World" and one after the OUT token right at then end.  The first two should close the statement on that line.  The last probably shouldn't as there might be an "else:" still to come.

a = b +
    c * d +
    e

There are 3 EOL token here in the same locations.  Now the first two should not close anything, while the last one should close the statement.

These two examples have very similar structure and are largely indistinguishable to the LR parser, and yet must be handled very differently. This implies that we need to provide the parser with extra information. We need to tell it something about the expected line structure of the language.

To understand what to tell the parse we need to look into our (or my) intuition about why the newlines are or are not wanted in the different locations.

I think the key observation is that statements are generally expected to be one-per-line, while there is no similar expectation for expressions.  The earlier observation that an "else:" might still be expected shows that statements are always one-per-line, however that is a fairly well defined exception. i.e. there are certain placed in a statement where a newline is expected, or at least not a surprise.  The start/end is one place.  Before an "else" or "elif" is another.  In C we might have:

if (a == b)
{
    print "Hello"
    print "World"
}

so an EOL is expected before a '{' or a '}' in that language.

If we define all the places where an EOL is expected then we should be able to work out when an EOL should close a syntactic unit and when it should be ignore.  However it isn't as simple as ignoring an EOL where ever it isn't expected.  We need to include our understanding that indents protect EOL in some sense. In the second EOL example above (a = b + c ...) the first two EOL tokens were ignored in part because they were indent.  If the second they were not ignore because despite being indented, they were expected.  So the interplay between indents and EOL expectations needs to be understood.

If we go back to our very first example:

A B C
   D E
   F
G H

you might remember I suggested that if something started at "B C..." it should finish at "F".  The "OUT" should close that as well.  Our process described ..... not sure ..

 

 

 

Also you need to know how the scanner can report indent information to the parser.  I discuss that in some detail when introducing my lexical scanner but you probably don't need to read that now.  It is sufficient to know that the token stream will have paired "INDENT" and "UNDENT" tokens, and that the "NEWLINE" token that you might expect to come before an "INDENT" is delayed until after the matching "UNDENT".

With this in place, it seems natural to allow the parser to absorb INDENT and UNDENT, but to require that when it reduces and production, the net indent absorbed while shifting the tokens which make up that production is zero.  i.e for every INDENT there must be exactly one UNDENT.  So:

if condition {

It might help to start with some examples.

1. Lorem ipsum dolor sit amet, consectetur adipisicing
2.         elit, sed do eiusmod tempor
3.         incididunt ut labore et dolore
4.            magna aliqua. Ut enim ad minim
5.    veniam, quis nostrud exercitation ullamco
6. laboris nisi ut aliquip ex ea commodo consequat.
7. Duis aute irure dolor in reprehenderit in voluptate
8.      velit esse cillum dolore eu fugiat nulla pariatur.

Here are 8 lines of random text - the line number are just for reference and should not be considered part of the text.   Similarly any punctuation or capitals should be ignored when trying to understand the structure.

Looking at just the newlines and indents it appears that line 1-5, line6, and lines 7-8 form three separate and equal units.  Within the first of these, lines 2 and 3-4 are again to separate and equal units.  Line 5 is not part of whatever 2,3-4 are but is something else that is part of 1-5.

Where that structural analysis is actually correct cannot be determined without knowledge of the meaning, so lets try something more meaningful.

a = [ 1, 2
      3, 4
      5, 6
    ]

Now we can clearly see that the continued lines are all part of what was started on the first line.  The last line is less indented than the others much like line 5 in the first example.  We took that to mean it is not a continuation 2nd and 3rd lines but only of the first, and this example bears that out.  The lack of a comma at the end of the first 3 lines are not lead to any ambiguity.  It is clear from the structure that something is completed.  It cannot be the whole list that is completed as that started on the first line and we are still indented with respect to there, so it must be a "smaller" or more local syntactic unit that has completed.  i.e. the list entry.

Here is a different example using the same structure.

if a = 1 { a =
    b + c;
    d = e;
  }

This looks very wrong.  Breaking the first assignment looks bad, and having the second assignment start with the same indent as the continuation of the first is also wrong.  Yet the list begun, but not finished, of the first line of the first example looks fine.  Maybe it is the amount of indenting that makes a difference.  We can try adjusting that and see:

a = [ 1, 2
   3, 4
   5, 6
  ]
if a = 1 { a =
               b + c;
   d = e;
 }

certainly the amount of indenting helped in the first example, but fixing it doesn't really fix the second example.

hello

30apr2014
 I seem to be stuck here...
 What do I know?

 When I see a newline, I must either IGNORE it or SHIFT it or REDUCE
 The key question is: when to ignore it?

 We ignore newlines when they are protected by an indent.
 What does "protected" mean?  It means there is already an internal indent
 in any symbol which can derive a newline.

 So in the above examples, only newlines are expected at end of
 statement (with or without ';') and after '{'.

 So for all the newlines seen in a = [..] the closest symbol that derives
 newline is 'statement' and it has an internal indent.  So they are ignored.

 In the "if a = 1 { ..."  The first newline is after "+ c;". We are in
 statement (or statementlist) which derives newline and that has internal
 indent so newline is ignored.  But I don't want it ignored.

 How about:
   When we see a newline, we find the closest reducible thing that
   can contain a newline.  If it started at the start of a line and
   contains an internal indent, then we can ignore the newline.

 That has potential: a line-like thing can only be broken if it
 starts at the beginning of a line.

 But can we implement this in an LR grammar?  We don't know what context
 we are in until we reduce into that context.  So how do we determine if
 we are in a line-like thing?

 Each symbol has a 'can_eol' flag.  EOL gets that flag, and  any
 non-terminal which can produce an 'can_eol' symbol gets the flag too.
 So 'statement' has it but 'expression' does not.

 Each state has an 'expect_eol' flag.  If is set if the 'next' symbol of
 any item in the state has can_eol set.
 OR : It is set if any the head of any production in the state has can_eol set.

 Now recall that the state stack is conceptually:
   STATE1 SYM1 STATE2 SYM2 STATE3 SYM3
 Each STATEn is expecting all the following syms to eventually be reduce
 to something which can then advance that state.
 So if STATEn has 'expect_eol', then everything following is part of
 something that maybe could have a newline in it.

 So if STATEk has expect_eol then we ignore newline precisely if
 SYMk was at start-of-line and somewhere from SYMk on there is an
 internal indent.  So we need a new start-of-line flag in the frame.

 Is expect_eol precise enough?  I'm wondering about a production
 that has a newline in the middle.  What happens then?
 After the newline has been shifted the whole won't be reduced so that
 expect_eol state will still be there so we can still be ignoring
 newlines.

 I think we declare that a production which can contain a newline but
 cannot end with a newline is an oddity which we don't support.

 Similarly if any production from a symbol can contain a newline,
 then every production is assumed to be line-like and so require an
 indent for newlines to be ignored.


 "Newlines are ignored only inside line-like symbols which started at
  the beginning of a line and  have since had an indent"

 Possibly good, but a grammar with no newlines would not allow
 newlines.  Maybe that doesn't matter - the lexer can ignore them.
 Can we turn it around  though

 "Newlines are only shifted if the nearest line-like thing does not
  have an internal indent."
 so "They are ignored if there is no linelike thing, or it holds an indent

 Also "An internal indent in a linelike thing that started midline is
  not permitted.


 That didn't work - 'expect_eol' definition doesn't make sense in that way.

 New attempt:
  expect_eol is set if *all* of the *next* symbols in core item
  have cal-eol set.
  When a core item does not have a 'next' symbol we ignore that item.

 Looks good, but now a new issue appears.
 If a production is reduced by an OUT indent, the following NEWLINE
 doesn't have a home.  If expect an optional newline there it might
 use the newline before the outdent (which could have been ignored
 otherwise??). and worse, it can create a reduce-reduce conflict
 because the optional newline could terminate inner or outer statement.

 This is particularly a problem with
    Block -> : Statementlist
    Statement -> if Expression Block else Block

 After an OUT reduces ": Statementlist" to Block there is a NEWLINE
 but we need to see the "else".  If we indent the 'else' it works nicely.
 I want to tell that a NEWLINE is needed there.  That means I must put one
 after "Statement -> if Expression Block" to avoid a reduce/reduce conflict.
 Each.

 After trying to describe this I need to refine it again.
 - A symbol is "can_eol" if any symbol in any production from this symbol
   is followed only by nullable symbols.
 - A state is "starts_line" if the previous symbol in any item "can_eol",)
   or is nullable and previous to that "can_eol", etc.
 - The start state is "starts_line" if the start symbol "can_eol".

19may2019 - in Texas!
I hit a problem.

Because anything that ends at a NEWLINE is considered LineLike, an
Expression is LineLike.  I didn't want that.
So if I have

   print
     a + b
     + c

The NEWLINE after b is not Ignored in the expression,
 only once it has reduced the simplestatement because....

 A NEWLINE is discarded when the tos is NOT newline_permitted.
 A frame gets newline_permitted when the state "starts_line"
  which happens if a starting sym is "line_like", meaning it
   can usefully be followed by a newline.


25may2019
 I've re-read most of my notes about NEWLINE parsing and I'm not sure....
 I originally wanted "linelike" to be anything containing a newline.  I apparently
 found problems and now it is anything followed by a new line.
 But that seems weird, because in
   assignment -> name = expression
   statement -> assignment NEWLINE
 expression is followed by a newline, so is linelike.  I think.

 Can I return to my original idea?
 Any symbol containing a newline is lineline, and newlines shouldn't be ignored.
 If the symbol started since an indent.  If it started before an indent, then it
 doesn't affect newlines.

 During parsing, we don't know which symbol we are working on (yet),
 only which states we have, which can be working on multiple symbols.
 The decision we need to make when we see a newline is which of these to choose:
  - ignore - if states since an indent don't start a line
  - reduce - if there is start-of-line state since start of line.
  - shift  - if we can, and not ignored
  - reduce - if we can
  - error  - if nothing else

 Maybe every item in an itemset must be followed by a newline if any are.
 That cannot work as we always add prefixed of 'next' symbol.


 if expr { NEWLINE
 if expr NEWLINE {

 Should the NEWLINE be ignored?  No!  It isn't indented.
 So if I want NEWLINEs to be allowed, they need to be explicit.
 This makes the state startsline.

 So: we mark can_eol on any symbol that can derive NEWLINE
  we mark a state as starts_line if any item with dot-at-start can derive a can_eol.

 Then if the most recent starts_line is further back than an indent, we ignore newlines.
 So I don't need the lineline flag.

03jun2019
 I'm making progress with newlines...
 Newlines *are* shifted if there is only one symbol since the start of the line..
 The current conundrum is what happens to several blank lines after:
   if cond:
      action

 The next thing could be
   - an else:
   - a new complex statement
   - the end of the block

 The first two are currently handle with newlines before things, so we stack up
 several newlines, then when we see a thing, we reduce the newlines out from under it.
 But that doesn't work for the end of the block.
 A Newlines symbol cannot insert an optional linebreak, but can absorb blank lines.
 So places where a line break is optional, we have
    Open -> {
         | Newline {
 Where we want to allow blank lines, we have
    Newlines ->
                NEWLINE Newlines

    Then if we see a newline, not at start of line, we shift if it is optional
    When we see a newline at start of line, we shift if blank lines are allowed.
    So if grammar allows
           Newlines Open
    Then .... that doesn't work.  Newlines won't get any lines.
    Maybe we want:
        Open -> {
             | NEWLINE Newlines {


 I have a problem.
 I want

    else: a := b

 to parse the same as

    else:
          a := b

 and for the last newline to close the elsepart.
 But the latter has 2 newlines while the former only has one
 and I don't have any obvious justification for ignoring either.
 I think it is in the Newline before the OUT that is extra.

 I could drop the newline before the OUT, assuming the newline
 separate things, and the OUT will force any reductions needed.
 But then we have fewer newlines reported than actual.
 (Same imbalance happens with multiline comments and strings, so maybe
  that is OK).
 Another way to look at it is that the newline following an IN is discarded
 (or always ignored) and not moved to after the OUT.
 So (maybe) the newline at an IN or OUT is reported *after* the IN or OUT.
 so
  A
    B
    C
   D

 Would be A IN NL B NL C OUT IN NL D OUT NL

 The parser always ignores the NL after an IN but uses other
 NL to reduce to a single symbol (if possible)
 OR maybe it doesn't ignore (unless not line-like context) and
 lines are preceeded by NL, not followed by them...
 No, followed is usually good.. though separated is better... so preceed!!

 Ok, this isn't working.
 A construct
   if cond:
      pass

 cannot be reduced to a Statement until we know what comes next, and it
 might be separated by several newlines.
 So the newlines need to be part of the Statement.
 But that means we cannot have newlines at the front of a statement.
 But that was the point...

 Maybe a Statementlist is a series of StatementNL followed by a Statement

 We allow
   StatementNL -> Statement Newlines
 as a general catch-all, but when we have something like if, or anything
 with an optional tail "else:" or "case:"
 We say:
   StatementNL -> if Expression Block Newlines
 But that would produce a conflict with
   Statement -> if Expression Block
 As a newline could either trigger a reduce to Statement, or a shift.
 Obviously we shift, but maybe we use precedence to force the point.

 Can we handle 'else if' ...
 IfStatementNL -> if Expression Block Newlines
             | if Expression Block else IfStatementNL

 ... I'm contemplating having the parser duplicate NL as necessary, so
 that
    if test: action
 can appear to be followed by 2 NL, one to terminate the 'action' statement
 and one to terminate the whole 'if'.
 This might mean I need to extend when NL are discarded - to ensure they
 don't get duplicated too much.
 1/ if state does not permit newlines, discard
 2/ else if I can reduce symbols all since start of line do that.
 3/ else if can shift, do that
 4/ else if only one symbol since newline, discard.
 5/ else ERROR

 This means that we cannot recognise multiple newlines
 or does it.
 If we shift a Newline, that is since_newline=0;
 If we reduce that to Newlines, that is still since_newline=0
 If 4/discard only applies when since_newline==1 -- we win.

 Currently since_newline essentially means the symbol contains a newline.
 So 'statements' usually does, but 'statement' doesn't.
 When we shift the newline and reduce, it all becomes since_newline=0.
 That is when we want to ignore newlines.

 15jun2019 - still working this through..

 Normally the parser does
   shift or else reduce or else error
 exceptions are TK_in which is simply recorded and
   TK_out: reduce until there is a TK_in in scope, then cancel, else error
   TK_newline:
       if not newline_permitted (indent since last starts_line state)
                 Discard
       if can Reduce to at most start-of-line, reduce
       if can Shift, duplicate and Shift
       if can Reduce, do so
       if 0 since newline, Discard

  since_newline needs to be changed a bit.
   A TK_newline token *isn't* zero, it is N+1.  The token *after*
   the NEWLINE is zero - so that

 Arg.  I'm struggle with that fact that having shifted a newline,
 we are both at the end of a line, and at the start of the next.
 When I see a newline, I want to reduce until the end of line
 is in the same state as the start of that line.

 Maybe I do want newline to be a separator.
 What if I don't actually include the newline in the grammar, just like in/out.
 Instead we mark select productions as lines.  This is like marking
  for precedence.
 A marked production is reduced when a newline is seen providing it won't
 contain any indents.
 So: if the reducable item in a state is marked, the start gets marked.
 When we see a newline, if the state is marked and the reduce size does not
 exceed since_indent, we reduce.  Otherwise we discard.
 No... I need an error condition too.
 So I need the state to have a starts_line marking, when a new item is marked.

 So:
   productions can be marked $$NEWlINE which flags the production as line-like
   a state with an item with DOT at start of a line-like production is starts_line
   a state with an item with DOT at the end of a line-line product is ends_line
   We track indents as before.
   When we process an indent or newline, we set since_newline to 0
   When we see a newline we do one of:
     if not newline_permitted, we discard
     if top state starts line, we discard
     else reduce or else error

No.....
 A production -> { statements }
 needs to ignore newlines either side of statements.
 It is a multi-line production - newlines don't matter.
 Maybe there are several sorts of symbols:
  - in-line:  must be broken across lines unless indented
  - line-like: is terminated (reduced) by a newline
  - multi-line: newlines are ignored

 We tag symbols which are line-like.
   Any symbol which can derive a line-like symbol is multi-line
   Any other symbol is in-line.

 So SimpleStatements, ifhead, elsepart, casepart etc are linelike

$line SimpleStatements IfHead ....

 A state that is at the start of a linelike symbol starts_line
 Any state in a multi-line production starts_line

 if tos starts_line, newlines are ignored.
 else if there is an indent since the starts_line, newlines are ignored.
 But if there are symbols since starts_line, we have to reduce until are
 are in a starts_line start (or can see an indent).

No....
    Block -> : Statementlist
is none of thse.  It must be reduced by a newline, but isn't entirely line-like.
    Block -> { Statementlist }
is multi-line

but maybe Block here is neither.  It only becomes linelike when it
terminates a Statement, which is linelike.  Or terminates an ifHead

Should this be legal?
  a:=b;pass if something
probably not. I want to require at least ';' or NEWLINE.
That means I need to include NEWLINE in the grammar.
 Statements -> SimpleStatements ; Statement
      | Statements  Statement
      | Statement

 if cond: if cond: a:=b
NEWLINE reduces this down to IfHead
IfHead -> IfHead NEWLINE
Statement -> IfHead
   | IfHead ElsePart

ElsePart -> else BLOCK
  | else IfHead
  | else IfHead ElsePart
  | ElsePart NEWLINE


Statements -> Statements Statement
       | Statement


if cond { statments } else { statements}
but not
if cond: statements else: statements

so :statements must expect a NEWLINE but then
  if cond: if cond: statement
expects 2 NEWLINEs.
Maybe
   Block -> : IN statments NEWLINE
if there is no indent, we synth one which triggers an OUT NEWLINE pair.
This could be automatic.
 If a linelike is followed by a newline, we synthesis an IN before it.

That requires a hack to the scanner: Synth Indent

What if

 Block -> { Statements }
   | : Statements NEWLINE
   | : SimpleStatements

Then
   if Expr Block

might not end in a NEWLINE so else could come immediately. Is that OK?
   if expr: a:=0 if expr
must be forbidden.  That requires a newline.

 Block -> : IN statements OUT NEWLINE

In marks state as 'needs_indent'  If an indent arrives, fine.
If something else, we record that next newline (After balanced in/out)
must synth extra out/newline.

 Block -> { Statements }
     | : statementblock

 statementblock -> Statements $$line

$$line means it must be reduced by a newline.  If something else tries,
it is an error and we skip to newline.
It also strips everything but NEWLINE from the (effective) lookahead
to avoid reporting conficts, as those things will never be shifted.

 IfHead -> if Expr Block
    | IFHead NEWLINE
 Block -> { statements }
     | : statements $$line

 IfStatement -> IfHead
      | IfHead IfTail
      | IfHead else IfStatement
 IfTail -> else Block
      | IfTail NEWLINE


------
20jun2019  Happy 87th birthday Dad.

I'm not convinced about $$NEWLINE

   else: simplestatementlist

should be able to parse simplestatementlist without a newline, and
use the newline to close the if/else.
where as
   else:
      statementlist

has a newline to close the statementlist and another to close the if/else.
But can the LR parser tell the difference?
It only sees that newlines don't forcibly reduce the else:
So when it sees the newline at the end of simplestatementlist,
it cannto shift because there is a sub-line thing that can be reduced.
So this becomes elsepart before the newline is absorbed.
Whereas in statementlist, the newline can be shifted creating simplestatementline.

What about
   if cond: if cond: statement

Again, the newline cannot be shifted while we can reduce

But.... how does conflict analysis know that an 'if', for example, is not
permitted after simplestatementlist?

Ahh.. This is exactly what $$NEWLINE is for. Maybe it should be $$OUT.
Either way, the grammar is ambiguous and relies on newlines or indentation to
close the production, and this fact needs to be explicit.
Requiring OUT is probably best as it means
  if cond:
       statements
    else:
       statements

works even though there is no newline after the first statements.
Here I want the 'statements' to be closed by OUT, but the whole to
be closed by NEWLINE.
So maybe I need both $$NEWLINE and $$OUT ??


$$OUT makes lots of sense.  It is exactly how we expect :statements to
be closed - where we allow NEWLINE to have the same effect.

$$NEWLINE is good for closing an complex if or for etc.  It means that
nothing else can be on the same line - allowing for indents.
How do we implement that?
Any production in the grammar that represents a full line but doesn't
end with a newline should be marked $$NEWLINE
This head of that production should recursively absorb NEWLINEs.

I'm not yet clear on exactly the difference bwetween $$OUT and $$NEWLINE.
I would put $$OUT after
   block -> : Statements $$OUT
and $$NEWLINE at the end of a statement that must end a line
   condstatement -> Ifpart IfSuffix $$NEWLINE
         | constatement NEWLINE

Maybe I need a worked example.
   while conda:
       if condb: if condc: action
   pass

So after action there is NL OUT NL pass
The NL sees that it can reduce, and the if allows the NL to reduce it so
      while COND : IN if COND : statement   [ NL OUT NL ]
again the NL can reduce.  Note that we *don'* absorb the NL in the statement
      while COND : in statement [ NL OUT NL ]
Now we can shift the NL
      while COND : IN statment [ OUT NL ]
Now the OUT forces a reduction
      while COND BLOCK(in)  [ OUT NL ]
Now the out is cancelled
      while COND BLOCK [NL]
and the while is reduced.

So the $$NEWLINE must always see a newline (or $$EOF)
An $$OUT must see an OUT or a NEWLINE (if there was no IN)

$$OUT causes the LA set for items with the production to be empty.
It is never credible that anything will be shifted so any apparent LA
contents can be ignored.
The state when a $$OUT is reducible has a recedence higher than any terminal, so
nothing can be shifted and no completion should be possible.
The state when a $$NEWLINE is reducible is much the same.

Maybe I don't want NEWLINE in the grammar, only $$NEWLINE??
How would we recognize a blank line?
  command -> $$NEWLINE
??
We would need a new rule for discarding newlines.
e.g. when the top-but-one state is start-of-line we discard and mark the top
state s-o-l.  That stops us discarding a newline until it reduces something that is at the start of a line....

1/ if there is an indent since the last start-of-line state, discard NEWLINEs
2/ if ....

Q: When is a NEWLINE an error?
A: when it isn't ignored and we cannot reduce and
   top or  top-but-one state isn't starts_line.??

So we need extra state info and extra frame info.

State has:
  - starts-line - is at start of a $$NEWLINE production
  - ends-line - is at end of unreduced $NEWLINE production
  - ends-indent - is at the end of a $$OUT production
  - min-prefix - how far back a 'in' can be and still cancel

Frame has:
  - indents - count in or after that sym
  - line_start - is the was a line start (IN or NEWLINE) immediately after
      the symbol
  - newline_permitted: no indent since start-line
  - since_indent: number of frames where indents==0
  - since_newline: number of frames where line_start==0

If we see a NEWLINE then:
  if ! newline_permitted, discard
  elseif can reduce and reduce_count <= since_newline - reduce
  elseif since_newline <= 1, and state.starts-line, discard and record line_start
  else error

If we see an IN
  increment indents, set line_start

If we see an OUT
  if reduce_size <= since_indent, reduce
  if min_prefix >= since_indent, cancel
  else error

How does error handling work?
Normally we pop states until we can shift ERROR
Then we discard tokens until we can shift one.

However we need to do something different for IN OUT NEWLINE.
For IN, we simply increment a counter
For OUT we decrement if it is positive.
   If it is zero and the state ends-indent, then we are synced.
   If it doesn't, we need to pop more states until we have an indent to cancel.
For NEWLINE if the state ends-line or ends-indent and ...something... we are synced.
   else we skip it??

... no, that doesn't work because I cannot see a way to describe an optional newline.

Let's try with just $$OUT which requires OUT or NEWLINE...
We put $$OUT on productions that must be closed in a 2-d obvious way.
So they can be at the end of a line or at the end of an indente block.
So
   : statements $OUT
means the next line after the : cannot be indented.
However
  Block -> : statementline | : statementblock | { statements }
  statementblock -> statements $NEWLINE
means I can have else indented, or on same line as single statement

  if cond: a = b; else: b = a
  if cond:
        a = b
     else:
        b = a

The whole 'if' needs a $NEWLINE marking to ensure a following statement isn't
indented.
So implementation is almost exactly what I have:
 - if anything else is lookahead when reducing that production, it is an error.
 - remove non-newlines from lookahead in items

But I don't think $$OUT is quite what I want to call it.
That doesn't quote cover end-of-line possibilities.
Maybe allow $$NEWLINE or $$OUT but with same behaviour.

.... still not there.
Another way to satisfy a $$OUT reduction is for it to already look right.
So: No indents and at start-of-line

But that upsets the modification to look-ahead as we can no longer assume
the next token.
I think this might be more like a precedence thing??
Without look-ahead modification, the first token of a statement can be shifted
 before a newline forces a reduction....

Maybe I do need two sorts productions.
 $$OUT requires an out/newline to reduce it.
 $$NEWLINE follows either $$OUT or NEWLINE and requires start-of-line and no indents.
        or $$OUT or $$NEWLINE

Or does it matter. Over-modification of the look-ahead suppresses warnings, but
doesn't affect the parse.
Will we get warnings anyway?


--------
Are left-recursive symbols in a non-final position always bad?

Left-recursive symbols cannot be closed by forcing a reduction.
So if one starts in an indented region (in which newlines are ignored)
it could continue afterwards - unless we make that an explicit error somehow.
If they appear at the end of some other production, that one will (maybe)
be reduced as well so (maybe) no problem...

if cond:
   a()
   b()
 c()

is weird and I want to forbid it.  Al that is between b() and c() is
NL OUT IN.  NL closed b(), so it is just OUT IN
So I do want the statementlist to close.

 a :=
     1 + 2
   * 3 + 4

is very wrong.  How much can I help?
The OUT will reduce "1 + 2" which will then become
    ((1 + 2) * 3) + 4
which would be highly confusing.
So something about this must be disallowed.
Maybe when newlines are ignored, OUT doesn't force a reduce??
I can make it an error by having Expression reduce to something else.

Do I want an error even for
    1 + 2
    * 3 + 4
??

I could achieve that by adding extra checks when we SHIFT at
start of line.
If we could reduce tokens since previous SOL, then we have 2D ambiguity.

   1 + 2 *
   3 + 4

That is just as ambiguous, but we cannot reduce anything.
When we see the second '+', the reduction crosses a line-start but doesn't
result in a line-start.

So: a reduce that doesn't contain an indent, but does contain a start-of-line
must reduce to that start of a line.

This means we need to keep the start-of-line when we "IGNORE" a newline.

Can I use this sort of logic to avoid the need for the extra reduction,
or for the $$OUT markings??

1/ The point of extra reduction is to avoid consuming more after an OUT or
   ignored NL.
    if cond:
         a()
         b()
       c()

    must be an error.  The OUT reduced a()b().  The stack is then
        if cond : statements(n1) . IN Ident
    The first indent is gone. . There is no error until we see all of c() so
     if cond : statements(n1) simplestatement(i) . NL OUT NL

    Is it  problen that the simplestatement is indented?
     if cond : statements(n1) statement(i) . OUT NL

   Q: is it an error to reduce a sequence containing an (uncancelled) indent?

2/ The $$OUT markings guard against exactly a reduction containing an uncancelled IN.

So maybe I have two new rules.

 1/ a reduction must not include any uncancelled indent.  pop() must return 0.
 2/ a reduction the contains an unindented start-of-line must begin with start-of-line.
     So when we cancel an indent, we also cancel line starts since there.

One other value of $$OUT is that is avoided conflicts - most symbols could not
be shifted.  That should have only applied to $$NEWLINE(!) and doesn't apply
at all if I drop the marking and use internal rules instead.
So how do I avoid reporting conflicts?

Really, there shouldn't be any conflict as NEWLINE should be expected.
Let's go back to that idea.

1/ A linelike thing MAY start with Newlines and MUST end with a NEWLINE
2/ A SimpleStatement is not linelike and doesn't include and Newlines
3/    if condition : SimpleStatement
   is a SimpleStatement.

4/ When we see the NEWLINE after "if condition : SimpleStatement" we have a shift/reduce
   conflict as we could SHIFT to make a complex statement, or reduce the whole thing
   to a SimpleStatement.
   Default action is SHIFT but in this case we want REDUCE - due to precedence?

   However when we see the NEWLINE after "if condition :IN Simplestatement"
   we cannot REDUCE as there is an cancelled indent, so we have to shift.

   But when we reduce, we only want to Reduce to IfHead so that an 'else' can appear
   on the next line.

   If we see IN .. just continue.

What do I need to do:

 1/ Change grammer to expect blank-lines before and to have a NEWLINE at the end
    of any line-like thing.
    This requires IfHeadNL and IfHead.  ditto for switch, while, then ...
    This get complex with
      for a:=0; then a += 1; while a < 10:
    which could have several newlines
      for a:=0
      then a+=1 ; while a < 10:

    ForPart -> for simplestatements ;
            | for simplestatements NEWLINE
            | for Block
            | Newlines ForPart

    ThenPart -> then SimpleStatements ;
            | then SimpleStatements NEWLINE
            | then BLOCK
            | Newlines ThenPart

 2/ disallow Reduce when embedded indents - report ERROR
 3/ disallow Reduce when embedded start-of-line.
 4/ TK_newline uses these rules to decide when to force a reduce.

A/ A parser symbol that starts after an IN must end before the OUT
B/ A parser symbol that starts before an IN must end at-or-after the OUT
    only if if the symbol is not line-like ???

C/ A parser symbol that starts after a line-start and before an indent must end
    by the end of line
D/ A parser symbol that starts at a line-start must end before the end-of-line,
    or at a subsequent end-of-line.

A is satisfied by forcing a reduce on OUT and reporting error if IN cannot be cancelled
B is satisfied if we report an error if we try to reduce an uncancelled IN
C is satisfied by forcing a reduce *after* shifting NL and reporting ERROR if
   min_prefix exceeds the line
D is satisfied if we report an error when reducing at eol crosses a NL and doesn't start
   at start-of-line.

C is interesting - do we reduce *after* shifting NL??  I think we do, yes.

So: when can I suppress conflicts, and how do I handle reduce/reduce conflicts?

I need to be sure that a line-like ends with an unindented newline.
I can trigger an error when that doesn't happen, but I want more.
I want to encourage it to happen.  So if the grammar allows a NEWLINE it
will be shifted in, but if we have already seen an OUT, we ignore the NEWLINE
rather than trigger an error.
Also, I need to not report shift/reduce conflicts on whatever comes next.
i.e. if
   a -> b c
and c can end with a, then both c and a can be followed by the same things.
This is a conflict.  If c (and a) end with NEWLINE we declare the conflict
resolved.

An IfHead might not end with a NEWLINE.  So to make a statement we need
to follow it with an optional NEWLINE.  Let's see if we can make that work.

What is a SimpleCondStatement?  It has no blank lines or unindented breaks..

  ForPart ThenPart WhilePart CondSuffix OptNL

We don't need a distinct Simple class!! If it didn't start at SOL,
then unindented NEWLINEs must be terminal  Wooho!!

This requires that "Statements" doesn't insist on following NEWLINE

A SimpleStatement can be followed by a ';', a Statement cannot.  That
different is still needed.
So
   SimpleStatements -> SimpleStatement | SimpleStatements ; SimpleStatement

SimpleStatements can end with a ComplexStatement and no NEWLINE.
ComplexStatements must end with a NEWLINE after each statement except the last

Each Part (including SSlist) end with arbitrary NEWLINEs.  These will
only ever be at the same indent level.
A ComplexStatement must be separated from next by a NEWLINE.
So if the final non-empty Part does not end with NEWLINEs, how do we require one?
Maybe not..

What if a Part doesn't end with NEWLINE ever, but can start with them

CondStatement -> IfPart Newlines
  | IfPart IfTail...

I think I need a CondStatement which doesn't end with a newline and a
CondStatementNL which does.  Then anything that can end a cond statement
must come in two versions.
 IfPart ElsePart CasePart WhilePart  CondSuffix

If we expect the non-NL, we accept the NL but not vice-versa.

------
problem.
in
   if cond:
       cmd1
       cmd2

the 'if' that started before the indent must finish at/after the indent.
But in
   if a = b or
      c = d :
          do something
The Expr that started before the first indent may finish well before the indent finishes.
I think this is because Expr is not linelike but 'if' is.

So I don't want an error when reducing if there is an indent, unless the new top start
starts_line
...

OK, I'm up to the part where I need to hide conflicts that I can automatically resolve.
I have:

  State 7 has 2 (or more) reducible items
    IfHead -> IfHeadNL . [25]
    IfStatementNL -> IfHeadNL . [27] (2Right)
  State 35 has 2 (or more) reducible items
    IfTailNL -> else IfStatementNL . [32] (2Right)
    IfStatement -> IfStatementNL . [30]

I need to clarify the rules that I'm working with.

1/ Statements might not end with a NL but as it is linelike...

2/ IfHeadNL IfStatementNL IfTailNL all end with a NEWLINE
   IfHead IfStatement IfTail might not (but they may)

Why did I want IfHead -> IfHeadNL??
Because I might have
   if cond:
        action


     else: bar

No, that is still an IfStatementNL.  Once there is any NL, we cannot fit it
on a line.

Hmm... the FooNL pattern is getting out of control.
Why do I need this again?

Because when "if cond : statements" is followed by a NEWLINE I need to
hang on to the parser state - not reducing to statement - until I see an 'else' or don't.

If I do see the else, the difference doesn't matter.  If I don't then I need
to know if I have a NEWLINE.

So I could have
  IfHead -> if Expression : Statements
  IfHeadNL -> IfHead Newlines

  IfElse -> IfHead else
          | IfHeadNL else

  Statement -> IfHeadNL

 But I want "if Expr then SimpleStatements"
 where SimpleStatements can end with "IfHead"
So when I see:

 if foo : if bar : baz NEWLINE

That NEWLINE mustn't turn "if bar: baz" into an IfHeadNL
  We need to first turn "if bar: baz" into a SimpleStatement, then
  "if foo : SimpleStatement" into an "IfHead", but NOT into a SimpleStatement.

Arg.  I might not know to reduce something until I've seen an IN.  It is the
'else'

What if an Statement *always* ends with a newline.
So
   if Expr : Statement
also ends with a newline and can be a statement
But if there is an IN after ':' the newline is hidden.
So that doesn't work.

What if a NEWLINE absolutely has to be at the top level.
If a symbol contains a NEWLINE, then it must be at the start of a line,
possibly indented.
So if it isn't indented, it mustn't contain a NEWLINE - no NEWLINE will get shifted in.

 Statement -> if Expr : Statements
            | SimpleStatements

What does Statements look like?  It must end a NEWLINE
  Statements -> Statements Statement NEWLINE
        | Statement NEWLINE
        | Statements NEWLINE
        | SimpleStatements

  SimpleStatements -> SimplePrefix ; Statement
  SimplePrefix -> SimpleStatement
        | SimplePrefix ; SimpleStatement


01July2019
 I think I have a very different approach - it incorporates a lot of
 the ideas so far and is maybe better.

 From the top:

   We have a simplified SLR(1) grammar where each state has at most one
   reducible production.  We don't have an action table, but use the goto table
   to decide if a terminal can be shifted.  If it can, we do.  If it cannot,
   we reduce or trigger an error.

   Onto this we add handling for IN/OUT and NL.  NL can appear int the grammar,
   IN/OUT cannot.

   Any non-terminal which can derive a NL is deemed "line-like".
   Such non-terminals will normally appear at the start of a line - possibly indented.
   These non-terminals can have some productions that have a NL (usually at the end)
   and some that contain no NL.
   If a non-terminal appears other than at the start of a line then no NL will ever
   be shifted into it, so a production without NL will be used.
   If it does appear at the start of a line, then any production can be used, though
   it must end up ending in a NL.

   The above paints an incorrect picture of how LR parsing works.  At any given
   time you don't know what non-terminal is being matched, so we cannot exclude
   NL based on the non-terminal. We only know what parser state(s) we are in.
   So: any parser state which is at the start of a line-like non-terminal is
   flagged as "starts_line".
   Also, in each start we store a "min prefix" which is the minimum non-zero number of
   symbols before "dot" in any item in the set.  This given a sense of where we are
   in the parse.

   If min_prefix if the top state is less than the number of symbols since start-of-line,
   then we will not SHIFT a newline.

   Indents (IN) are recorded after the symbol they follow.  If there is an IN
   since the most recent starts_line state, the any NL is ignored.
   An OUT will cancel the most recent IN, providing is in the top min_prefix symbols.
   If not, we need to reduce something first.

   So when we see an OUT, we reduce until we can cancel.
   When we see a NL, we reduce until the min_prefix reaches at least to the
   start of the line.  Then we can shift the NL.
   After shifting the NL, the whole line should be reduced.

   When a line-like non-terminal produces a sequence that *doesn't*
   end with an explicit NEWLINE, the grammar analysis ensures that
   nothing can be shifted in after the end of the production.  This
   forces it to be reduced into the non-terminal.

   For example
      simplestatement -> var = expr | print expr
      simplestatements -> simplestatement | simplestatements simplestatement
      SSline -> simplestatements NEWLINE | simplestatements ; condstatement NEWLINE

      statement ->..
             | simplestatements NEWLINE
             | simplestatements ; statement
             | if expr then statements NEWLINE
             | if expr then statements Newlines else statements NEWLINE

   When a non-terminal is explicitly followed by a NEWLINE, it is line-like
   also if it contains a NEWLINE or linelike, it is linelike.


 ifhead -> if expr : statements
   | ifhead NEWLINE

 iftail -> else : statements
   | else ifstatement

 ifstatement -> ifhead
   | ifhead iftail

 statement -> simplelist | ifstatement | Newlines simplelist | Newlines ifstatement

 statements -> statement | statements statement

 A line-like that contains newlines must be reduced by OUT or NEWLINE.

 How can I know that a statements can be followed by else in
      if cond : statements else: statements
   or
      IfHead IfTail
 bit not by 'if' in
      statements statement

 Maybe I could have a $sol token.
  If at $sol, and cannot shift then try shifting $sol..
  then
    statements -> statements $sol statement
  or maybe $eol is better, then we can have NEWLINEs start start of statement.
  OR maybe either... $linebreak is shifted if previous or next is NEWLINE
  An IN doesn't allow a LINEBREAK.

Just to repeat myself:
  Arg.  I might not know to reduce something until I've seen an IN.  It is the
 'else'

After above, new approach:  IfHead and Statement have NL versions, nothing else does.
MAybe fixed the above...

So

  StatementNL -> Statement NEWLINE | IfHeadNL
  Statements -> StatmentNL | Statements StatementNL
  StatementList -> Statement | Statements

  Block -> : Statements | Open Statements Close

  IfStatement -> IfHead | IfHead IfTail | IfHeadNL IfTail
  IfHead -> if Expr Block
  IfHeadNL -> IfHead NEWLINE | IfHeadNL NEWLINE
  IfTail -> else Block | else IfStatement

Close, but the IfHeadNL in "else IfStatement" cannot accept newlines.
What if
   IfHead -> if Expr Block | IfHeadNL else IfHead | IfHead else IfHead

No, I think I have to take a totally different approach.

IfPart elsepart switchpart whilepart etc are all syntactically valid
as stand-alone statements in the base grammar.
We use the code to fail a stand-alone elsepart the isn't preceeded by an ifpart, whilepart or casepart.

So statements never contain newlines, only the statement-list does.
If puts a NEWLINE at the end of each statement
 statementlist -> statement | statementlist NEWLINE statement
statement can be empty string, thus allowing blank lines and a NEWLINE at the end,
which the parser will require.


[[ thought experiment - interestibg, but gets unwieldy with
   more complex statements
statements -> simpleline NL statements
 | ifhead NL iftail NL statements
 | ifhead NL statements
 | ifstatement NL statements

iftail -> else block
 | else ifhead iftail
 | NL iftail

ifhead -> Newlines if expr block
ifstatement -> ifhead iftail
]]


13oct2020 - much later.

 Maybe a different approach to newlines.  Never shift them, only use
 them like indent to guide parsing.

 IN is just recorded
 OUT must reduce until top symbol contains an IN, which is cancelled.

 Some productions are flagged as $$NEWLINE (or similar) meaning that they can
 only be reduced as a whole number of lines.
 When we see a newline, we record that until a non-newline is seen.
 If we cannot shift and so choose to reduce:
    if the production doesn't require a newline - we just reduce.
    If it does, and we have recently seen a newline, again we reduce.
    Otherwise, we signal an error and (maybe) shift until we see a newline.
    NOTE the newline only counts if there are no indents.

 This means that
    a = b
    + c

 would be parsed as a statement, which I don't want.
 But I do want
   if foo: bar
   else: baz

 to be a single statement.
 So a new line in some context must force a reduction, like OUT.
 When exactly does a newline force?
 An OUT forces a reduction until the top symbol has the matching indent.
 A NEWLINE ?? Must depend on the grammar.

 

 Q: Can this be only about resolving ambiguity and reporting errors?
   If the default is to shift if we can, reduce otherwise, then
   2D causing an early reduce can resolve ambiguity.

   If certain productions must end at EOL, and error is thrown if they don't.

   That latter really must be a gramatically need to shift a newline.

 Maybe I'm wrong about reporting errors.  Maybe they should always come from
 a failure to shift or reduce.

 One of my problems was
   if foo: if bar: dostuff
 where the newline at the end needs to reduce everything, so I can
 require at most one newline in the grammar.
 It probably should be required for the first 'if'

  Stmt -> if Cond : StLstNL
  StLstNL -> StLst NL

  StLst -> Stmt
        | StLst ; Stmt
        | SlLst NLs Stmt
        | NLs StLst
 
  IfSt -> IfHead


  NONO.  I don't want some statements that end with NL and some that don't.

  - Record indent with preceding token and line-start with following
  - when reducing all indents are accumulated into the new symbol,
    and the line-start of first symbol is preserved. Other line-starts are dropped
  - When OUT in lookahead, there is an indent within 'min_prefix' of top state,
    decrement closest indent count and discard the OUT
  - When OUT in lookahead and cannot be discarded and top state can be reduced,
    reduce it
  - When OUT canot be discarded or reduce, and error is triggered.
  - No production can be reduced if it contains unmatched indents.  If cannot shift,
    then error.
  - Some productions are marked as $LINE
  - any state that contains an item at the start of a $LINE is marked 'starts line'
  - if there is an indent more recent than a starts-line state, or the top
    state starts_Line, newlines are ignored.
  - if a newline is seen but not ignored, and the top state can be reduced, 
    it is reduced.
  - A $LINE production can only be reduced by a newline, or, if it didn't start
     at start-of-line, by an OUT

  so 
    Block -> : statementlist  $LINE
   
  I want to be sure that
    if cond {
          statements
    } else {
          more
    }

  is OK. Here the "IfHead" doesn't end on a newline, but the state that is
  expecting 'Block' 'starts-line'.  I guess as "Block -> { statementslist }"
  isn't a $LINE, it can be reduced by 'else'.

24oct2020

 Maybe I don't want TK_out to force a reduce (mostly).  Maybe the grammar
 should be in control. So when we see an OUT we record it off-stack.
 If we reduce for some other REASON and the top state contains an indent,
 we cancel.
 When we decide to SHIFT, if the top of stack has -ve indent, that is an
 error.
 So with C,
  if (cond) {
        s1;
        s2;
  s2;

 would show an error when s2 was shifted.
  if (cond)
        s1;
        s2;
 needs to show an error too.  The "if(Cond)s1;" statement would have an
 internal indent.

 So maybe the requirement is that no symbol has unbalanced internal
 indents.
 When we shift we require that top balances first.
 So we count up outs and ins.  There can be several OUTs and at most on
 IN before a terminal.
 If the terminal can be shifted, the top symbol must have no internal
 indents after cancelling with out, and there must be no outstanding
 TK_outs
 If the terminal cannot be shifted we reduce and we must have enough
 outs to balance anything within the reduction.

 So indents on the stack are always between symbols. Each frame has
 a symbol, the indent after it etc.  

 If we don't have enough outs to complete a reduction we raise an error
 and need to discard (or shift/reduce) until we find an 'out'.
 If there are too many outs to shift we again need an error which will
 hopefully let us reduce and cancel some outs - just discarding states
 will help with that.

 So: outs must cancel, following token must envourage reductions

 Some productions end with newline, their start state is 'starts-line',
 and if there is an indent since a starts-line, we ignore newlines.

 If we don't ignore newlines, then there is a starts-line state that we
 should reduce to.  If we don't have enough symbols yet, we error.
 So if we see a newline, we reduce until the newline would be ignored.

 If that state expects a newline and we don't have one, we error.
 Except..  I sometimes want OUT to work like a newline.
 If I need a newline and reduction isn't to start of line

 If state expects newline and we don't have one but do have OUTs
 we reduce as long as there are enough outs and raise an error if
 we end up at start of line.


 Do I want to require that a newline be shifted?  We can synthesize
 one when minprefix is less than since newline and we have an out.


 Summary of stuff.
  A shift requires there be no pending OUT ??
  A reduce requires there be no pending indent, i.e that
       indents within the reduction don't exceed outs.
    NO this doesn't work.
  A IN increments the indent on the top frame - never causes error
  An OUT decrements indent in a frame within min_prefix, or error
  A NEWLINE is either ignored or shifted, but is duplicated when
  shifted.
  After an OUT is handled, if a NEWLINE is expected but will only
  reduce a partial line, it is provided.

  if foo: if bar:
             stuff
          bazz

  This effectively pretends there was a IN at the start of the "line",
  and we are not doing two OUTs with a NEWLINE between.
   if foo:
       if bar:
          stuff
       baz


  Do I really want to shift newlines:
    yes: simpler grammer
    no: don't need to record min-prefix.

 I think 'yes'.

 So discard $NEWLINE
 Place NEWLINE in the grammar
 When completing a state, if any production contains NEWLINE, record as
   StartsLine


 ---
 My idea of ignoring newline when the top state is a starts_line state isn't
 working.
   The idea was that reducing
        statement -> assignment NEWLINE
   would leave at a starts_line start, so NEWLINEs would be ignored.
   But this leaves us at a  ' ... statement . ' state
    e.g. " Statementlist -> Statement . "
  which reduces to "Statementlist -> Statementlist . Statement"



30oct2020

  Review: because it isn't working (as usual).

  Indenting have 2 effects:
        - it triggers errors when something looks wrong
        - it causes newlines to be sometimes ignored.

  Specifically:
    - A symbol that starts indented must finish while still indented.
      So an OUT cannot cancel an IN except in the top phrase, and an attempt to
      shift while there are pending OUTs is an error.
    - A symbol that begins at the start of line and contains an indent may only
      be the top symbol - shifting before an OUT cancels the indent is an error.
    
    - Newlines are ignored when there is an indent since a starts-line state

  Procedurally:
    - There can be one IN and several OUTs pending - we update the counters
      as they are seen.
    - If there are pending OUTs and their is an indent in the top phrase,
      we can cancel an indent.
    - a SHIFT becomes an error if the top symbol has an indent and started
      at beginning of line
    - a SHIFT becomes an error if there are pending OUTs
    - a SHIFT that is not an error first imposes the IN on the top of stack
    - REDUCE may happen at any time.

   Newlines, when not ignored, are repeating terminals. An indefinite series
   is generated until a state is reached where they are ignored.
   The expectation is that they will be shifted (possibly after some reductions)
   and then a reduction will happen which changes the state appropriately.

   It is vital that no recursive production keeps consuming newlines
     foo -> foo NEWLINE
   as that will be fed indefinitely, or if newlines are ignored, will never reduce.

   NEWLINEs are recognized if there is a starts_line state since the most recent
   indent, but not when the current state is starts_line.  So once we reach
   starts_line, we ignore newlines until something else is shifted.
   Or maybe only a starts_line state at the start of a line?

   A starts_line state has an item "head -> . stuff NEWLINE"
   So if were just reduce 'foo -> foo NEWLINE' then we are at the end of foo,
   so an earlier state with have ".foo" and so "foo -> . foo NEWLINE" and so will
   be starts_line.  So we will always accept a NEWLINE. So these must be disallowed.

   How does "if cond : if cond : print NEWLINE" parse?
    "block -> : slist NEWLINE"
    "slist -> statment | slist statement"
    "statement -> print NEWLINE | if cond block NEWLINE"

   so starts_line are before statement or ':' - I don't want that as it would allow a newline
   before ':' to be ignored.
   Maybe I want starts AFTER a NEWLINE??  Did I do that before?
   So after block, after statement, after slist.. but we expect NEWLINE there.

   Maybe the important states are "foo -> baz . stuff NEWLINE".
   Once we've entered a path to a NEWLINE, we need to be ready for it.
   So: after :, after print after if and cond and block
   
   The repeating newlines are hurting now.  The rule to start ignoring them
   isn't working.
    ifhead else if expr : statementlist [NEWLINE]
   the NEWLINE should be ignored.
   There is an indent after ':' but final state is startsline because this could
   be the end of a block -> : statementlist NEWLINE
   But I want that newline to be ignored because of the indent.

   if (A)
        b;
        c;
   why is that bad?  How can we know?  Because we reduce to start-of-line
   and still have an indent.

    a =
      b + c
        + d
        *

  I need some good examples to remind myself.
   Why do I want min_prefix? I allow indents to be cancels within min_prefix
    cmd -> { statements }


01nov2020
 ARRRGGHHH  I keep going down rabbit holes.  I need to take a more mathematical
 approach and present clearly what I have and what I need.
 The big issue, for the moment at least, is when to ignore newlines.
 I REALLY like the idea of newlines being repeating until they are ignored.
 I definitely like that they are ignored after an indent unless they are explicitly
 expected.  I need to ensure they are not expected at awkward places, like the
 start of a line.

 I want to be careful of making LL assumptions about the LR grammar. i.e. I cannot
 assume the end from the beginning - that is was LL does.  I want the appearance
 of a newline to only make a difference once it appears.  But at the point that
 it appears we need to know if it is to be ignored. In
   a = b + NEWLINE
 it isn't ignored event though it isn't expected exactly here. In
   a = b + (IN)
       c + NEWLINE
 it is ignored and the difference is that no state since the IN expects a
 newline.

 To acknowledge LR approach we need to take the latest state.  The start of 
 line, before the 'a' is tempting but we hardly know anything there.  After the 'a'
 is tempting, but that would mean after a[b+c].thing(foo) as well which seems to
 miss the point.
 Maybe something earlier sets the expectation?
  if cond :
 The ':' says newline-separated things are coming. So it is the state
 after the ':' which says 'newlines matter'.  This will be after the indent.
 So if we saw
   if cond {
 then maybe newlines don't matter (depending on grammar)

 But a newline is ignored *at* that state, so that blank lines can be skipped.
 I think there is a 'statementlist' symbol and at the start or end of that symbol
 newlines are ignored.  Within that symbol unindented newlines are significant.
  statementlist -> statement NEWLINE
                | statementlist statement NEWLINE

 
02nov2020
 Can I drop the 'min-prefix' concept?
 The means that OUT can only cancel against an indent 'in' or immediately before
 the top symbol.  This means we go back to keeping a 'starts_indented' flag and
 storing each indent with the following symbol.

 Then the 'ignore newline' test is since_starts_line > since_indent
 but since_indent is 0 fir there are internal indents and 1 if there is only a
 starts_indented indent.

 So a TK_in simply sets starts_indented for next
   TK_out is recorded
  Whenever top symbol has indents and outs are recorded, we cancel.
  If we want to shift with pending outs, that causes an error
  
  I need a reason to signal an error for
       if (a)
             b=1;
             c=1;
  based on indents.  equally for
       if (c)
             b=1;c=1;
  If indent is a continuation, then  'c=1;' but be part of 'if...' before
  it is part of what comes before?
  This means the OUT will not be able to see the IN ... unless the whole
  statement list ends here....
  In  "a = IN b + c ; " the ';' causes a reduction to Assignment with indent
  so I must be happy for the 'c=' to reduce to 'ifstatement' with an indent,
  but reducing to the recursive 'statementlist' seems wrong.  Maybe these
  left-recursive productions really are special.
  But what about 'expr -> expr + expr' ??

  The rule I'm depending on is that I cannot shift with a pending OUT.
  So everything since the IN needs to compress to a single symbol.
  If the code is
   {
       if (a)
          b=1;c=1;
   }
  then the '}' will reduce to "{ statementlist" before shifting, so the OUT will be 
  cancelled.  The question is: how can we prevent that in the grammar?
  There are 2 OUTs (in this case) does that help?
  A comparable case is
   {
      foo;
      if (a)
        b=1;c=1;
   }
  In that case the two OUTs will be cancelled at clearly different times, but not real
  difference.

  {
    foo;
    if (a)
      b=1;c=1;
    bar;
  }

  Now the 'bar' will be blocked from shifting.... no it won't.

  I need a new rule - this *must* be wrong, even when we ignore newlines.
  But why?  Because "b=1;c=1;" looks like a statementlist, but isn't.  
  It isn't because a statementlist doesn't belong here, ony a block or a statement.
  How do I know that indent is continuing the 'if', not the statementlist.
  I need some marking on statementlist to say "Cannot be continued by indent"
  I guess that is what NEWLINE is for. 

  So the rules would be "a suitably marked production cannot be reduced with
  outstanding indents.  If nothing can be shifted, an error must be raised.
  These will typically be productions that end in a NEWLINE, but maybe any
  production from a symbol that can produce a NEWLINE, or that is marked $$something

 Back to TK_newline.  These are duplicated on shift, but discarded when not wanted.
 They are not wanted unless there is a starts-line start below the current state,
 and more recent than the most recent indent.
 A starts-line state is any state which contains an item with a NEWLINE and dot
 at the start.

  statementlist -> statement NEWLINE
                | statementlist statement NEWLINE


 Q: how do nested 'if's resolve?
     if cond:
        if cond2:
            print
      else:
         die

   statement -> if cond block
              | if cond block else block
   
   The tokenization would be 
     if cond : IN if cond2 : IN print NL OUT NL OUT IN else : IN die NL OUT NL OUT NL
                1             2       A   2  B   1   3         4     C   4  D   3  E
   so NLs:
      A  makes 'print' a statment,
      B  makes 'if cond2' a statment,
      C  makes 'die' a statement
      D  is protected by IN/3 and is ignored.
      E  makes if cond .. else.. a statement

  What if I also had

              | if cond block NEWLINE else block

  Then on seeing the NEWLINE I wouldn't know whether to shift it,
  or reduce to a statement.
  To fix that I would need:
   statementlist -> statement | statementlist statement
   statement -> simplestatements NEWLINE
      | if cond block NEWLINE
      | if cond block else block NEWLINE
      | if cond block else statement
      | if cond block NEWLINE else block
      | if cond block NEWLINE else statement

  But wait.... Allowing NEWLINE before 'else' confuses the parse of 'if cond:...' above.
  NL-B makes "if cond block NEWLINE" and then the else can be shifted, but that is illegal
  because of the negative indent.  That means the negative indent must prevent SHIFT.


 Do I still need to know which symbols are 'line-like' ??
    Yes, to make it easier to detect line-line productions which must contain unmatched indents.
 Do I need recursive line-like detection?
   For no-indent productions, it probably makes sense.
   For starts-line detection?  I don't think so. 'block' isn't the start of a line.
   And not really needed for no-indent


 Do I need to worry about left-recursive symbols?
   I don't think so.  There should always be some terminal - often NEWLINE -
   which will ensure the symbol isn't extended??.. or if it did we would get
   a parse error due to uncancelled OUT

 Do I need to split indents?
 A stack frame holds "symbol state".  Indents are within or before the symbol.
 For cancelling with OUT, indents within and before the top state are equivalent.
 For hiding newlines the indent before the symbol is too distant.                       f->next_indented ? "/" : "",

 So: yes.
 Should I store them in the stack?
     "symbol+indents  indent  state"
 So when we see an indent, we mini-push that
 Any indent since state protects newline
 Out can be cancelled if top state has indents, or previous has trailing indent.

 Rather than an ignore_newline flag we need a outs_needed flag.  This is how
 many outs are needed before we process newlines.
 If state is startsline, then outs_needed == infinity.
 Else it is a count of indents since a starts-line state.
 So maybe it is an indents_since_starts_line and we test state and indents.

 So:
  1/ rearrange frame to include 'indented' in the top frame
  2/ replace ignore_newline with indents_on_line

14nov2020
 I'm getting close...
 Problem is correctly ignoring of newlines.
 I ignore them after an indent - that bit is easy.
 But I also ignore them at a start-line symbol - sometimes.

  INDENT statementlist  NEWLINE     should ignore the newline
 but
  INDENT statementlist if  expr : stl if expr : stl NEWLINE should not

 (/0s) Statementlist (11s) IfHead (5) else (22) if (3) Expression (19) : (29s) Statementlist (40s) [NEWLINE:22:0] - Ignore

  This shouldn't Ignore.  Is that because there is a non-'s' since the '/' ??

  i.e Ignore newlines if all states since indent are startsline, or if none are.
   Don't count current state if it is startsline
   indents_on_line > outs || all_startsline(...)

 No - better, but no banana.  if expr { statement; newline
 need to ignore even without the indent.
 So I need a new type of state - one that is at the start of Statementlist but
 not at the end.  State 29 in the above, but not 40

(/0s) Statementlist (11s) if (3) Expression (19) { (30s) Statementlist (39s) [NEWLINE:34:0] - ERROR

18nov2020
 So:
   I introduce "startsline" and "endsline" states.
   A state before a linelike symbol is startsline, a state after such a 
   symbol is endsline.  A state can be both, in which case we consider it 'endsline'.
   So 11 endsline, 30 startsline 39 endsline

   If there is an indent since the last startsline or endsline state, we ignore NEWLINE.
   If there are only start/end line states since indent, ignore newline
   if there are only endsline states since startsline, ignore newline - NO.

   
 I wonder if maybe I should have IN and OUT in the grammar.
 The tokens can still appear anywhere, but the production can only be reduced of there is an IN there.
  Block -> : IN Statementlist OUT | : SimpleStatements
 might get messy.  But it already is messy.

20jan2021 
 Where am I?
 The big questions seems to be: when can/must I ignore NEWLINEs?
 Conversely when do they REDUCE or get SHIFTed?
 The answer must lie in what appears between the most recent INDENT and the NEWLINE.
 - if there are no startsline states, we can ignore.

 It seems that I need to be able to see the start of a block, either an indent, or a {..
 But if there is a statementlist, surely a block started?  No, that misses a point.
 INDENT ignores newlines because there will be a matching OUT
 Maybe { causes NEWLINEs to be ignored because there is a matching } expected?

 If a startesline state is at the end of a productions, it plays no role in NEWLINEs,
 but if it is followed by something

23jan2021
 review/summary.
 We track indents and newlines.  The goal is resolve ambiguities and detect errors.
 Ambiguities are resolved by forcing a REDUCE in some circumstances when an OUT or NEWLINE is seen.
 Errors happen when an there are too many OUTs.
 NEWLINEs are a normal part of a grammar, except that they get ignored sometimes when they are not relevant. 
 and are protected.

 1/ a production from a lineline symbol cannot be reduced while it contains an unbalanced indent,
  and so must be reduced before an excess OUT token is processed.
 2/ NEWLINES are ignored if there is an IN since a start-of-line state

 Otherwise NEWLINEs must be in the grammar.  This can be awkward where they are optional
 such as before an 'else'.  To handle the fact that a structured statement can be multiple lines
 or few we need to build it up from the possible line-like parts.
 Maybe this means that ifpart, elsepart, whilepart, casepart etc need to be statements which
 are combined above the grammar level??
 The reason has something to do with reducing to Statement when the newline is shifted.  
 I wonder if that is really needed. 
 if we have "ifpart -> if cond block" then that can be followed by elsepart, but we 
 need a separate "ifpartNL -> ifpart NEWLINE | ifpartNL NEWLINE" which can also be followed
 by an elsepart, or can reduce to a statement
 ..but no.  That isn't sufficient if NEWLINEs are indefinitely duplicated.
 So if we don't ignore newlines where they aren't needed, we cannot duplicate them.

 The need for duplicating was constructs like
   if cond : if cond2 : action
 which needed 2 NEWLINEs, one for each statement.
 Maybe the "if cond2 : action" needs to be a simplestatement.
 When we see the NEWLINE we can (must?) reduce anything that started since
 a start-of-line, which creates the simplestatement.

 So let's try dropping the infinite repeat and require newlines in the grammar

 Extra rules:
 - a production from lineline symbol cannot be reduced while it contains unbalanced
   indent
 - a NEWLINE is ignored if no startsline state since indent
 - a NEWLINE cannot be shifted unless top startsline is at start of line.

 So a NEWLINE is:
   - ignored if not startsline since indent
   - forces REDUCE if top startsline is not at start of line !!!!. i.e. don't shift
   - else can be SHIFTed.

26jan2021 - happy australia/invasion day
 I want ": simplestatements" to be a valid block, but not when there is an
 indent in the middle
 Previously this was resolved by having an SSLine -> simplestatements NEWLINE
 and the SHIFT of the NEWLINE outweights the reduction to block.
 And I have that now with Statement -> SimpleStatements NEWLINE...
 Ahh.. it is because I put Newlines before Statementlist.  I guess a NEWLINE
 needs to be a Statement

 I currently suppress shift unless "outs == 0".  That means
   if cond:
       statement
    else:
 doesn't shift the 'else' because the "out" isn't resolved.
 Without the leading space, the NEWLINE reduces to ifstatement, and I sort-of know
 that is an issue.
 So: why suppress SHIFT when there is an outstanding OUT... or better Question,
  why is this OUT still outstanding?
 Ahhh.. I misunderstood.  I DO want to reduce that 'if' because it is nested.
  I have an IfStatement what needs to reduce to a Statement and merge with a
  Statementlist, so the OUT can be cancelled and then the 'else' shifted.
  BUT as 'else' is the lookahead.... I need NEWLINE to reduce IfStatement to
  Statement.  But even with a NEWLINE we don't SHIFT that because we still have
  that OUT to clear.  So how do I clear an OUT ??  It can only be cancelled when
  the matching IN reaches TOS, which requires the NEWLINE to be shifted.
  We cannot shift the newline early, partly because that would be wrong, and
  partly because it gets reduced to a statement and disappears.

 Hmmm.  After blocking SHIFT(NL) when we don't have a line I see
 progress but not there yet.
   if false {
       print = OK
   } else {

 After the OK is NL OUT NL
 The first  NL is shifted and reduces down to Statementlist and the OUT cancels.
 But now the NL doesn't belong.  Can I explicitly allow NL before } ??
 No, because it doesn't even SHIFT.  It cannot because the Statementlist doesn't
 appear to be sol - the OUT hide that and it now looks like
   if expr { statementlist

 Arggh.  I think I need to hide the starts-line state in this context.
 More thinking needed.

 I introduced the shift-block to make sure the NEWLINE paired with the right line.
 Here the NEWLINE should probably be ignored.  But why?  It isn't indented, but it
 is inside a multiline thingy.
 Might be better to explicitly allow it and find some way to let it be SHIFTed.
 Problem is that the Statementlist is linelike, but I don't want that here.
 Hard to avoid when the statements are and must be linelike.
 Maybe I need a way to hide linelike-ness.  

 Maybe a state should only be startline if the core item has dot followed by
 a single symbol (which can derive a newline) ??