Incorporating newline-as-statement-terminator heuristics into context-free languages

Question

Several block structured languages (Scala, Go, Ruby, Julia, Quorum, ...) use semicolons as statement terminators, but allow newlines instead of semicolons under certain circumstances.

My question is: how can I represent Scala-like optional semicolons in a context free grammar? The specific issue is that some kinds of nesting delimiters "enable newlines" while others "disable newlines," so you need to pay attention to what kind of delimiters you are most immediately inside of.

I'm specifically asking about Scala's heuristic, because Julia and Quorum don't have specs. Ruby has a spec, but handles the problem by scattering "[no line-terminator here]" throughout the formal grammar and I've been unable to find a general rule. Go has a well described heuristic but it's lexical only, which makes it obvious how to specify and implement, but its usability is somewhat disappointing. (Go inserts a semicolon even if you haven't closed the most recent ( token.)

Scala goes well beyond the Go lexical rule with a nesting rule (cf reference, Section 1.2). In addition to lexically ensuring that both the token before and after the newline are consistent with the insertion of a statement terminator, newlines-as-statement-terminators are disabled between matching ( and ) parenthesis and [ and ] brackets, but then re-enabled between matching { and } braces.

I can figure out how to implement a simple pre-processor as a push-down automaton. The automaton starts with enabled on the stack. As you process the token stream, when you see a ( or [ push disabled onto the stack, when you see { push enabled onto the stack, and when you see ), ] or } pop the top of the stack. Then when you see a newline that otherwise satisfies the lexical rules for the insertion of a statement terminator, you insert the terminator if and only if enabled is on the top of the stack. So Scala's newline-to-statement-terminator rule is "context free" in some sense, but I haven't been able to figure out how to incorporate this push-down automaton in with the rest of the language grammar.

Answer 1

I do not know Scala (though I hope it has a good opera-tional semantics). I am answering on the basis of the information you give in the question. I think your problem is using the stack rather than the finite state to remember local behavior. Finite state is for information you are currently using, while the stack is for information that you have to remember for future use, but do not need right now. At least, I see this description as a convenient way of designing pushdown uses - though I am aware of all the equivalence games between various definitions of PDA.

So your automaton should start with nothing on the stack, but with a terminator register containing enabled. As you process the token stream, when you see a ( or [ push the content of the register onto the stack and put disabled in the register, when you see { push the content of the register onto the stack and put enabled in the register, and when you see ), ] or } pop the top of the stack and put it in the register. Then when you see a newline that otherwise satisfies the lexical rules for the insertion of a statement terminator, you insert the terminator if and only if enabled is in the register.

The register may be seen as a simple finite-state control that can be used for a cross-product with the rest of the finite-state control of the PDA parsing your Scala syntax. I expect that by proceding this way, you get a stack policy for terminator insertion rules that can be smoothly merged with the policy for parsing the rest of the syntax, since various types of parenthesis must match for the rest of the language too. And you parser should sing without dissonance.

Doing finite state control cross-prodduct is another technique for designing PDAs (among other devices, most likely). I think it has been extensively analyzed for FA (I think, but it should be checked that this is related to Krohn–Rhodes theory).

Answer 2

The basic problem we have to solve is how to separate sequences of statements

(A)
statement1
statement2

from multi-line statements

(B)
state
ment

Dedicated separators such as semicolons are a time-honored way to do this clearly but some people dislike them. An alternative is to require some kind of syntax for triggering (B) (I think I've seen state \ \nment) which is likely to be rejected for similar reasons.

So, one way to do this is to ensure that the set of statements is prefix-free, that is no statement of the form (B) can parse as (A) ever. Of course, that is rarely possible as you want to allow (improperly parenthesised) statements like

x = 3 - 2 + x

and at the same time blocks like

x = 3
- 2 + x
[returns 1]

Such languages (e.g. Scala) are inherently ambiguous on a syntactic level (without dedicated statement separators). On a semantic level, you may be able to resolve the ambiguity, e.g. you might figure out during name analysis that x is not initialised in reading (B) or during type analysis that the block should return an integer, which reading it as (B) may not do.

Needless to say that many dynamic languages don't even allow for this because all variables may be implicitly initialised or every statement returns something or what not.

In other words, I think this language "feature" is beyond the capabilities of PDAs if you don't want rigid precedences. You need backtracking, look-ahead,
semantic analysis and even guesswork.