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 {