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.

  • $\begingroup$ So you don't want to allow lookahead or backtracking? Modern compilers are not tied to a linear scan with a stack so it may be possible that some features are hard or impossible to parse with a regular PDA. $\endgroup$
    – Raphael
    Jul 25 '14 at 9:35
  • $\begingroup$ @Raphael In what way do you expect lookahead or backtracking would help in this case. Actually, neither gets you out of the CF realm, but backtracking does get you out of the deterministic CF realm, which is not really a major issue today. $\endgroup$
    – babou
    Jul 25 '14 at 9:50
  • $\begingroup$ Backtracking may be CF (I'm not sure) but I'm fairly certain that arbitrary lookahead is not. What either gives you is checking the alternatives; I hope my answer is clearer? $\endgroup$
    – Raphael
    Jul 25 '14 at 10:01
  • 1
    $\begingroup$ @Raphael I agree that unlimited lookahead is out of CF. But given your answer, the question in now unclear. Are we supposed to analyse the Scala definition, or to answer with respect to the features described in the question? $\endgroup$
    – babou
    Jul 25 '14 at 10:27

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).

  • $\begingroup$ Ah, I think I get it. Sure it's not a context-free language, but so what? I have a simple way of parsing strings in the language (preprocessor followed by "normal" parser), so I should be pleased. Indeed, when you put it that way, I am pleased. Thank you! $\endgroup$ Sep 30 '14 at 12:38
  • 1
    $\begingroup$ Actually, I meant it as part of the normal CF parsing process with a PDA. I was only telling how to merge the terminator control with a PDA designed for the rest of the syntax, where all newlines are replaced by semicolons where needed. Then you add the enabling register mechanism, and actually interpret newlines as if semicolons when the register is enabled. The only difficulty is that the enabled/disabled pushed on the stack can hide the stack top which may be necessary for for the parse. But that can be handled with minor state/symbol juggling. $\endgroup$
    – babou
    Sep 30 '14 at 20:46
  • $\begingroup$ @WanderingLogic I did not try to include the mechanism in the CF grammar for the language. It would most likely make it harder to read and maintain, though it is probably not too hard to do, once you know what to do with the PDA. I find it much simpler to do the design and explanation on the PDA itself. Translating that in CF grammar terms would require duplicating parts of the grammar, so as to carry down the generation tree the enabled/disabled context. $\endgroup$
    – babou
    Sep 30 '14 at 21:16

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


from multi-line statements


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.