Hot answers tagged

63 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 ...
user avatar
  • 11k
23 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: ...
user avatar
  • 597
12 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 ...
user avatar
  • 11k
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 ...
user avatar
  • 9,325
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 ...
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 ...
user avatar
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 ...
user avatar
7 votes
Accepted

Are syntax and semantic just 2 structures such that one is a model of the other?

I am afraid the phrasing of the question misled me (though I did know better) in first seeing model theory as applying to any two arbitrary mathematical structures, and being the study of ...
user avatar
  • 19.1k
7 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"...
user avatar
  • 11k
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 ...
user avatar
  • 11k
5 votes
Accepted

Why are syntax trees used in genetic programming?

In short: AST representations of programs are more easily analyzed, manipulated, and transformed, while preserving and enforcing the existence of a formally defined program meaning through the ...
user avatar
  • 19.1k
4 votes

Are syntax and semantic just 2 structures such that one is a model of the other?

It all very much depends on how you model these concepts where syntax end and semantics start. When the syntax is described using a context free grammar, then there are aspects of the language not ...
user avatar
4 votes
Accepted

How to read BNF syntax of C?

Backus Normal Form does not define special syntax for %token. So that would be a special syntax custom-added by a particular person or web page or tool. Tool ...
user avatar
  • 140k
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, ...
user avatar
  • 28.1k
4 votes

Programming Thompson's algorithm: How to represent a NFA?

If you look closely, Thompson's R.E. to NFA algorithm is carefully tuned to be able to use a simple linked structure: a state is a node, it has one leaving transition on a symbol, or two on $\epsilon$ ...
user avatar
  • 13.6k
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 ...
user avatar
  • 14.1k
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 ...
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 ...
user avatar
  • 4,611
4 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 &...
user avatar
4 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 ...
user avatar
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 ...
user avatar
  • 1,389
4 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)....
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 ...
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. ...
user avatar
  • 4,611
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 ...
user avatar
3 votes
Accepted

Differences in Postfix Syntax

There are no "rules", you make the rules yourself. The rule used in class has the property that the numbers appear in the same order in both expressions. The rule is also pretty natural: $$ T(\alpha \...
user avatar
3 votes

Why are syntax trees used in genetic programming?

Syntax trees provide an abstract representation of a program with a certain kind of type information at each vertex. This allows, when attempting to evolve a program, the swapping/changing of subtrees ...
user avatar
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, ...
user avatar
  • 28.1k
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 ...
user avatar
3 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 ...
user avatar
  • 24.9k

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