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.
Incorporating newline-as-statement-terminator heuristics into context-free languages
context free;programming languages;pushdown automata
I do not know Scala (though I hope it has a good opera-tionalsemantics). I am answering on the basis of the information you give inthe question. I think your problem is using the stack rather than thefinite state to remember local behavior. Finite state is forinformation you are currently using, while the stack is forinformation that you have to remember for future use, but do notneed right now. At least, I see this description as a convenient wayof designing pushdown uses - though I am aware of all the equivalencegames between various definitions of PDA.So your automaton should start with nothing on the stack, but with aterminator register containing enabled. As you process the tokenstream, when you see a ( or [ push the content of the registeronto the stack and put disabled in the register, when you see {push the content of the register onto the stack and put enabled inthe register, and when you see ), ] or } pop the top of thestack and put it in the register.  Then when you see a newline thatotherwise satisfies the lexical rules for the insertion of a statementterminator, you insert the terminator if and only if enabled is inthe register.The register may be seen as a simple finite-state control that can beused for a cross-product with the rest of the finite-state control ofthe PDA parsing your Scala syntax. I expect that by proceding thisway, you get a stack policy for terminator insertion rules that can besmoothly merged with the policy for parsing the rest of the syntax,since various types of parenthesis must match for the rest of thelanguage 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 KrohnRhodes theory).