Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
74 votes
Accepted

Are modern programming languages context-free?

Practically no programming language, modern or ancient, is truly context-free, regardless of what people will tell you. But it hardly matters. Every programming language can be parsed; otherwise, it ...
rici's user avatar
  • 12k
24 votes
Accepted

Which other programming languages apart from Python and predecessor are out there using indentation to define code blocks?

Wikipedia has an extensive list of languages that use the off-side rule1: ABC Boo BuddyScript Cobra CoffeeScript Converge Curry Elixir (, do: ...
Bergi's user avatar
  • 608
13 votes
Accepted

Break keyword outside a loop is syntax error or semantic error?

Both work, so how you do it is up to you. But there are a couple of reasons to consider doing it during a post-parse analysis: While it is certainly possible to define two different types of ...
rici's user avatar
  • 12k
10 votes

Which other programming languages apart from Python and predecessor are out there using indentation to define code blocks?

There are: Elm, Haskell, its predecessor Miranda and its predecessor ISWIM, YAML where spaces are crucial for syntax and tabs are forbidden, OCCAM, Coffee script and Cokescript both are language to ...
Evil's user avatar
  • 9,465
9 votes
Accepted

Is there a correspondence between the syntaxes and the type systems of programming languages?

You seem to have a misunderstanding of the purpose of abstract binding trees (ABTs). They are a tool for describing syntax, much like abstract syntax trees (ASTs). They simply allow you to describe ...
Derek Elkins left SE's user avatar
8 votes

Is type-checking "syntactic" or "semantic"?

Although I personally would describe type analysis as semantic, this question seems to start with the assumption that there is a clear, formally-definable dividing line between "syntax" and "semantics"...
rici's user avatar
  • 12k
7 votes

Why is the syntax of some programming languages very much not according to earlier conventions?

Today, most people who learn a programming language know very little mathematical notation and are more familiar with other programming languages, and with symbols that are available on their computer ...
Gilles 'SO- stop being evil''s user avatar
7 votes
Accepted

Relation between "syntax" and "grammar" in CS

Your quote has the following operational meaning for syntax in the context of programming languages: The syntax of a programming language is the set of all syntactically valid programs. The syntax ...
Yuval Filmus's user avatar
6 votes
Accepted

Examples of context sensitive syntactic constructs (statements)

Here are three context-sensitive syntaxes actually found in programming languages. I don't believe I've ever seen a language which has types, names and values distributed as per your example, but it ...
rici's user avatar
  • 12k
5 votes

Is type-checking "syntactic" or "semantic"?

(From my limited experience) I would certainly call type-soundness a semantic property of a program, rather than a syntactic one. In some dynamic languages (e.g., lisp, python sans type annotations &...
D. Ben Knoble's user avatar
5 votes

What are the modern alternatives to Backus–Naur form and what are their advantages?

Answer 1: The question is meaningless as written. You are mixing different kinds of notations here that are intended for different purposes. BNF and ABNF are concrete notations for writing the ...
Aaron Rotenberg's user avatar
5 votes
Accepted

Relation between programming languages requiring declaration of variables before use and using the token class $\text{id}$ while parsing

In order for their example to work, the authors need identifiers to be of unlimited length. This is because the language $$ \{ wcw : w \in \{a,b\}^*, |w| \leq n \} $$ is context-free (indeed, regular)....
Yuval Filmus's user avatar
5 votes

Are modern programming languages context-free?

The boundary between context-free and context-sensitive is only determined by one thing: whether or not it can be decided with a nondeterministic pushdown automata. With respect to grammar ...
Beefster's user avatar
  • 161
4 votes
Accepted

Parser theory: How to systematically compute FOLLOW sets?

The simple way to do it is the same as the simple way to compute FIRST sets, using a least fixed-point algorithm in which a set of inclusion rules are applied repeatedly until a fixed-point is reached:...
rici's user avatar
  • 12k
4 votes
Accepted

Simple example for Higher Order Abstract Syntax (λ-tree syntax)

Well, this is a bit broad but the basic idea is the following. In First-order abstract syntax (FOAS) we model lambda terms following their syntax tree. E.g., in Coq we would write ...
chi's user avatar
  • 14.6k
4 votes
Accepted

Why postfix arithmetic expression is not ambiguous?

With operator precedence infix is not ambiguous. Brackets are a convenience but not necessary to form an expression. However when parsing you have to resolve each precedence level in precedence ...
Craig  Hicks's user avatar
4 votes

Which other programming languages apart from Python and predecessor are out there using indentation to define code blocks?

Make fits your description, even though it probably isn't quite what you have in mind, with its limited syntax and power. It infamously indicates its code blocks (recipes) with a particular form of ...
reinierpost's user avatar
  • 5,664
4 votes
Accepted

What is the relation between syntax and type theory?

The division line between syntax and additional type checking can indeed be blurred, if so desired, but usually we make a distinction as follows: the syntax is described using a formal grammar, ...
Andrej Bauer's user avatar
  • 30.5k
4 votes

How is `y λx.x y` parsed using the standard pure untyped lambda calculus conventions?

The left associativity of applications is only relevant when you have a sequence of applications. If it were correct to interpret y λx.x y as ...
benrg's user avatar
  • 2,147
4 votes
Accepted

What does "lookahead" refer to?

"A good driver drives in three cars. His own car, the car behind him, and the car in front of him". (Bertold Brecht). "Lookahead" is what you do when you drive a car. You look ...
gnasher729's user avatar
  • 30.4k
3 votes

Do the following concepts belong to syntax or semantics?

It's not really a good idea to try to divide everything in PL into "syntax" and "semantics". Often we mix things. Nevertheless, as for your question, we normally divide things up like this: terms, ...
Andrej Bauer's user avatar
  • 30.5k
3 votes

What are the modern alternatives to Backus–Naur form and what are their advantages?

Here are a couple of pertinent references which support the idea "It mostly doesn't matter/write your own": different parsing approaches: https://code.jsoftware.com/wiki/Guides/Parsing a ...
DevonMcC's user avatar
  • 131
3 votes

What are the known ambiguities in C language grammar?

Not sure if this answers your question, but I will contribute two details regarding lexing/parsing ambiguities in C in general. I hope these are still helpful. Consider the expression ...
BearAqua in Agua's user avatar
3 votes

Why is BNF considered an unsatisfactory technique for describing a language?

I do not think that the semantics play a role. Your quote asks for "discover better methods of describing the syntax than BNF." Of course, things like function and variable names form part of the ...
Peter Leupold's user avatar
3 votes
Accepted

Why is BNF considered an unsatisfactory technique for describing a language?

You mention one reason. The other reason is that the syntax of programming languages isn't context-free, unless you define syntax to be that which can be, or is, described by a context-free grammar. ...
reinierpost's user avatar
  • 5,664
3 votes
Accepted

Which part of Go(lang) is in Crystal(lang)?

I simply asked @asterite, one of the developers of Crystal, at IRC #crystal-lang (the log is here). He said the answer is CSP, the concurrency model. For example, both Go and Crystal use channels for ...
nekketsuuu's user avatar
2 votes

Is this DO LET sugar considered pure Lambda calculus and nullipotent / side-effect-free?

Anything that can be encoded in the pure lambda calculus, as you realize in the last paragraph, can not have side effects. Otherwise, the lambda calculus itself would be able to express those side ...
chi's user avatar
  • 14.6k
2 votes
Accepted

Why does the following Backus-Naur form reflect the following syntax diagram?

< number>::=< digit > | < digit >< number > means that a number is either just a digit, or a digit followed by a number. So 1 is a number (...
adrianN's user avatar
  • 5,951
2 votes
Accepted

What kind of error are these?

The C standard does not bother to distinguish between different kinds of errors encountered during parsing, but it is possible to categorise errors according to which clause of the standard applies. ...
rici's user avatar
  • 12k
2 votes

Origin of using ">" to represent child in a tree

It comes from set theory. To see that these ideas were around before computers and that they were explicitly called trees consider the following famous tree. The convention set theorist sometimes use (...
Pedro Juan Soto's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible