12
$\begingroup$

In a lot of older C-family languages, lines of code (statements) must be ended with an explicit character (generally a semicolon). However, newer languages support inferring where statement endings should go. What are good parser rules to use for inferring statement endings?

$\endgroup$
2
  • 1
    $\begingroup$ stackoverflow.com/a/2846298/6333444 $\endgroup$
    – mousetail
    May 17, 2023 at 12:26
  • 1
    $\begingroup$ Note that in terms of having a simple non-ambiguous grammar it is very helpful to have an EOS token. Automatic EOS insertion always come at the price of having some bad corner cases. The trick is to minimize them. $\endgroup$
    – Nuoji
    May 17, 2023 at 13:47

5 Answers 5

6
$\begingroup$

A viable option is simply for every possible expression of the language to be self contained (i.e. with an unambiguous start and end).

Languages that do this is (that I know of) are Lua and Gleam: while at first it may appear as using newlines to end statements, every expression is either explicitly close or inferrably done by the next expression (as it's the case for infix arithmetic operators)

The following Gleam program

import gleam/io
import gleam/int

pub fn main() {
  let x = 8 + 8
  let y = {
    "meaningless"
    24 - 8
  }
  let add1 = fn(n) { n + 1 }
  let z = add1(7)

  io.print(int.to_string(x+y+z))
}

can be compressed and work just as well on a single line:

import gleam/io import gleam/int pub fn main() { let x = 8 + 8 let y = {    "meaningless" 24 - 8 } let add1 = fn(n) { n + 1 } let z = add1(7) io.print(int.to_string(x+y+z))}

This wouldn't be possible with the ML-style open expression syntax (i.e. application by juxtaposition).

$\endgroup$
1
  • 1
    $\begingroup$ Lua also does this. $\endgroup$
    – naffetS
    May 18, 2023 at 1:36
4
$\begingroup$

When the next token in parsing would otherwise make no sense

A rule in some languages including JavaScript. For example:

{ 1
 2 }

In this case 1 2 is not a valid expression so JavaScript automatically inserts a ; in between, turning this into {1; 2}.

$\endgroup$
2
  • $\begingroup$ JS does not insert a semicolon for 1 2, only for 1\n2 $\endgroup$
    – naffetS
    May 18, 2023 at 1:37
  • $\begingroup$ Yea the specifics are either a line break needs to be in between or the offending token is a } $\endgroup$
    – mousetail
    May 18, 2023 at 4:38
4
$\begingroup$

Python's grammar has the following:

simple_stmt: small_stmt (';' small_stmt)* (';')? NEWLINE;

The definition of NEWLINE then has to contend with Python's indentation rules, end-of-file determination, etc. If your language doesn't require white space the same way, then your lexer logic will be a little simpler.

A language I wrote uses the following:

eos : ';' | EOF | {endAhead()}? | {nlAhead()}?;

It still has to look ahead for end-of-file as well as block END tokens, but I didn't need to track indentation.

$\endgroup$
2
$\begingroup$

Infer end-of-statement aggressively at line end

If the end of the physical line could be the end of the statement, then it is. Only if the line ends mid-expression — within a bracketed construct, after an infix or prefix operator, or whatever else is applicable to the language — does it continue.

This rule ensures that lines never continue accidentally, which tends to be confusing and lead to unexpected errors. It is more or less the direct opposite of the JavaScript rule, which stops only if the statement could not continue — leading to situations like

var a = b * 2
// Log to screen or file
(verbose ? screen : file).write(a)

trying to call 2 as a function and complaining that it can't.

On the other hand, people often like to put their infix operator at the start of the continuation line, meaning that if the language both (1) has an overlapping prefix operator (like + or -) and (2) permits unused expressions as statements, this can pass unnoticed too:

x = y
    - z

In this case, the language will silently calculate and discard -z, rather than reporting an error. It's likely something the programmer will acclimatise to with use of the language, but there is a small trap there when the language allows.

A big advantage is that this rule is fully predictable based on the code the programmer is writing at the time, and won't ever inadvertently continue an earlier line that wasn't being edited. Each line "opts in" to being continued.

$\endgroup$
2
  • $\begingroup$ Unless you're okay with the language being newline-sensitive, wouldn't this rule mean you have to parenthesize all subtraction? x=y-z could feasibly parse as x=y;-z; even with no line break. $\endgroup$
    – Bbrk24
    May 17, 2023 at 21:33
  • $\begingroup$ I tweaked the heading to mention line endings to match the body instead of leaving "whenever" open. $\endgroup$
    – Michael Homer
    May 17, 2023 at 21:36
2
$\begingroup$

Indent continuation lines

A logical line continues across multiple physical lines as long as the subsequent lines are indented further than the initial line, and stops at the end of the physical line otherwise. This "hanging indent" matches the typical indentation pattern that people use for multi-line statements, so it virtually always does what the programmer intended. However, it requires including some indentation sensitivity in the parser, which is a complication. Otherwise, the statement ends at the end of the physical line.

The logical line ends as soon as a line at or before the initial indentation level is reached. For example, given this code:

while (condition) do {
    x := x ++ "a very long string with {interpolated - expressions} "
         ++ "spread over multiple lines" ++
         "with varied structure"
    !y or error
    z.update
}

the x := statement spreads across three lines, and stops before the prefix ! operator that matches the original indentation. The next two lines are single-line statements, on the same level.

Even in languages where line continuation works differently, programmers tend to indent the subsequent lines, so this aligns with general practice already, merely formalising it. They also, once they've learned what they're doing, don't tend to indent code at the same nesting level differently from line to line, so there are very few if any false positives in this approach. In the cases where they don't want to continue the statement, they don't need to do anything special.

This continuation is always explicit at the surface level: it doesn't matter what the contents of the lines are, where operators or brackets appear, or what sort of construct is in use, only the raw indentation. It is possible to pre-process the indentation away and mechanically join the logical lines together if desired, without needing to parse or understand the code. In that way the parser itself would not need to understand indentation.


This was the rule we ultimately adopted in Grace, and by and large it went unnoticed — the system always just did what people intended and they never thought about it. However, that language already had enforced indentation for bracketed blocks, so (1) the parser was ready to handle it, and (2) correct indentation was well trained into people before they started trying to split lines.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .