# Tag Info

Accepted

### Difference between syntax and semantic error in programming languages

In the strictest sense, there is no real difference between syntax errors and semantics errors, at least as far as language theory is concerned: the only salient difference is the complexity of the ...
• 13.3k
Accepted

### Does Standard ML validate (CBV) eta equivalence?

@xuq01's guess is (extremely surprisingly!) wrong. The CBV eta rule described in the question is sound in Standard ML: the value v is contextually equivalent to <...
• 31.8k

### Has anyone used Pottier and Gauthier's polymorphic defunctionalization in a modular compiler?

One approach is described by Georgios Fourtounis and Nikolaos S. Papaspyrou. 2013. Supporting Separate Compilation in a Defunctionalizing Compiler. SLATE 2013. As @gasche mentions: A different ...
• 2,019

### Commutative operation benefits

One example where commutativity helps is in computing the determinant. Nisan showed that any non-commutative algebraic formula that computes the $n \times n$ determinant must have size $2^{\Omega(n)}$....
Accepted

### Computing the DAG of a program given source code or AST

I assume you're looking for ways to compute the Control Flow Graph of a given program. This graph depends (obviously) on the actual operational semantics of the language you are interested in, and so ...
• 13.3k
Accepted

### Why can a Predictive Parser contain E' -> TE' | ε

... is not valid since we have "left recursion" (a variable that calls itself). That's not what a left recursion is. That's simply recursion. Direct left recursion is when a rule $A \to A\alpha$ ...
• 690

### Does Standard ML validate (CBV) eta equivalence?

SML compilers do perform eta-reduction (at least SML/NJ does), but I expect most functional programming language compilers do, even those for which the eta-law does not always hold. E.g. the pointer ...
• 382

### Difference between syntax and semantic error in programming languages

It is hard to say. The boundary between "syntactic errors" and "static semantic errors" can be really blurred. One appropriate example would be Curry-style (extrinsic typing) and Church-style (...
• 1,125
Accepted

### Name a set of program variables

This new version of the answer tries to take into account the changes in the question, and the information exchanged in the comments. This answer assumes that $S$ should be the set of variables that ...
• 1,512
In Knuth Vol II Theorem E on page 494 he presents an algorithm that can evaluate a polynomial using $\frac{n}{2} + 2$ multiplications. The theoretical minimum is $\frac{n}{2}$, assuming generic ...