# Tag Info

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

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

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

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

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

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)... 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 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 ... 2 The main reason is very mundane. At the time C was designed, and notations for many things, we did not have any form of graphics, or very seldom (like one graphic screen for the whole university, even in major places). Actually, the main output devices were the teletype or the line-printer, with a standardized and limited character set. Even the alphanumeric ... 2 Yes in this case they both happen to equal the same value however yours is technically wrong. Your forgetting the final rule of order of operations which is left-to-right. A + B * C + D (mult. first) A + *bc + D (left addition second) +a *bc + D (finally convert the last addition) ++a*bcd What you posted + A + * B C D corresponds instead to ... 2 What you're missing is the associativity of operators. All operators you mention in your examples are binary. An expression of the form$A + B + C + D$is interpreted by the parser as$(((A+B)+C)+D)$. When converting such a fully parenthesized expression into prefix form, we apply the rule$(\alpha + \beta) \to +\alpha\beta$. Denote this transformation by$T\$...

2

< 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 (just a single digit), and 12 is also a number (a single digit, followed by a number that consists of just the single digit '2'). Similarly 123 is a number that consists of a single digit '1' and a ...

2

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 effects as well. However, note that your encoding looks a bit weird. For instance, (LET a 1 b 2 e) = (λ a . (λ b . e) 1 2) does not bind 1 to a and 2 to b. You ...

2

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: Initialise all the sets to empty. For every production in order, use the rules to add elements into the sets. (As a slight efficiency, rule 2 only needs to ...

2

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. The second line in your query (int /* n; -- assuming that there is no */ in the remaining program text) is covered by a requirement in the description of phases ...

2

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

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