# Tag Info

61

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 wouldn't be very useful. So all the deviations from context freeness have been dealt with. What people usually mean when they tell you that programming languages ...

23

Wikipedia has an extensive list of languages that use the off-side rule1: ABC Boo BuddyScript Cobra CoffeeScript Converge Curry Elixir (, do: blocks) Elm F# (if #light "off" is not specified) Genie Haskell (only for where, let, do, or case ... of clauses when braces are omitted) Inform 7 ISWIM, the abstract language that ...

12

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 block, one in which break is legal and the other one in which it isn't, the result is a lot of duplication in the grammar, and a certain complication because you have ...

10

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 language compilers with JavaScript as target and esoteric Whitespaces. There is also Agda - interactive theorem prover, which is probably not what you had in ...

8

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 syntax that includes binders in a way that generic tooling can be applied. Capture-avoiding substitution, for example, works basically the same way for first-...

7

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 only describes what the valid programs look like; semantics gives them meaning – tells you how to execute them. The set of all valid programs is an example of ...

7

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 keyboard. Of course, this wasn't the case in the 1950s and 1960s when some of the major programming language families that exist today appeared. A lot of ...

7

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 homomorphisms of mathematical structures. Actually this is wrong. Model Theory already contains the idea of syntax and semantics, more or less as I define it below. It ...

7

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". I don't think that is the case; even if most of us would put type-correctness into one category and missing parentheses into the other one, there is a ...

6

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 could certainly exist, and I'm sure there are even less readable syntaxes which are possible. The following are at least somewhat readable: Syntactic whitespace,...

5

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 transformations. I am asssuming that the reader knows already what is an abstract syntax tree (AST), and does not need to be shown examples. The question is an issue ...

4

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 expressed in that model so we say those aspects are the semantics. However, there are many other ways of expressing (or modelling) the syntax of the language. ...

4

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 support is off-topic here, but if search for "%token" on the first link you gave, you'll find a brief explanation that appears to describe what %token means in the context of that particular example. ...

4

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, preferrably one that is not very complex, such as a context-free gramar, or one that is even simpler than that. the typing rules are described using inference rules ...

4

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$ (thus you can reuse the space for the symbol for the second pointer, and distinguish between both cases by a spare bit somewhere). Your partial automata have ...

4

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 (* FOAS *) Definition variable := string . Inductive term: Set := | var: variable -> term | app: term -> term -> term | lam: variable -> term -> term . ...

4

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 order (e.g., $^,[*,/],[+,-]$). A postfix expression is written exactly in computation order: $e0\ e1\ o1\ ... (ek\ ok) ... eN\ oN$ Computation is $r[1] = o1(e0,e1)... 4 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 whitespace: one tab character. Alternative ways are available (e.g. GNU Make supports using an alternative character), but rarely used in practice. Another ... 4 (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 & mypy, etc.), there is no syntax for types (and the semantic verification of type soundness is done at runtime in these languages). In some static languages (... 4 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 abstract concept of a context-free grammar. "Van Wijngaarden grammar" refers either to an abstract type of grammar a la "context-free grammar", or ... 4 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). The syntax of a language like Pascal or Algol is context-free. This accomplished by waiving the requirement that an identifier be declared before its usage; ... 3 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 syntax. With BNF you cannot, for example, distinguish a language where variables must be decalred before usage from one where you can use undeclared variables. ... 3 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. When Strachey's paper was written, the syntax of a new language, Algol 68, was being defined in a new formalism, two-level grammars, that was used to describe ... 3 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 communications. 3 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 \circ \beta) = T(\alpha) T(\beta) \circ$$ Here$\alpha$is an infix expression,$T(\alpha)$is the translation of$\alpha$, and$\circ\$ is a binary operation. ...

3

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 as long as the root vertex of the subtrees have the same type. As long as the program was valid, (and the subtrees are also valid), the result will still be a ...

3

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, values and types are syntactic entities, as each of them is described by grammatical rules, so these are syntax a typing context is syntax in simple cases, when ...

3

"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 ahead and make decisions not just based on things around you, but also based on things ahead of you. A parser with a lookahead of 1 makes decisions based on the ...

3

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 y (λx.x) y, then the left associativity rule would disambiguate it to (y (λx.x)) y. But that interpretation violates the rule that abstractions extend as far right as possible. Normally one never writes y λx.x y ...

3

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 specifically, most practical programming languages are almost context-free if not context-free, but the context-free/context-sensitive distinction isn't nearly as ...

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