28 votes
Accepted

Visual programming tools, why don’t they work with the AST directly?

Many of these tools do work directly with the abstract syntax tree (or rather, a direct one-to-one visualisation of it). That includes Blockly, which you've seen, and the other block-based languages ...
user avatar
10 votes
Accepted

How do I reconstruct the forest of syntax trees from the Earley vector?

I am using terminology and notations from Earley's paper. It is possible that the description you read is different. It seems frequent that general CF parsing algorithms are first presented in the ...
user avatar
  • 19.1k
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
9 votes
Accepted

Is CYK still relevant today?

CYK is still relevant, afaik, as the simplest example of a family of general parsing algorithm based on dynamic programming, ranging over all parsing technique (that I know of) and many syntactic ...
user avatar
  • 19.1k
6 votes

Visual programming tools, why don’t they work with the AST directly?

At least two reasons: Because source code is a much more concise representation. Laying out an AST as a graph would take up a lot more visual real estate. Programmers prize having as much context ...
user avatar
  • 143k
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
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.2k
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
3 votes
Accepted

Code optimization - syntax tree vs. intermediate representation

These days, the trend is to do optimization with the intermediate representation. Check out LLVM for example: The LLVM Core libraries provide a modern source- and target-independent optimizer, along ...
user avatar
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

How do I interpret the wording of this passage about abstract binding trees from the book Practical Foundations of Programming Languages

Just to clear something up that may not have been obvious, $\chi$ is a set and the notation $B[\chi, x]$ is meant to be ABTs under free variables that are either $x$ or are in $\chi$. In this notation ...
user avatar
3 votes

Visual programming tools, why don’t they work with the AST directly?

The typical AST by compilers is rather complex and verbose. The directed graph representation would quickly become quite hard to follow. But there are two large areas of CS where ASTs are used. ...
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
2 votes
Accepted

Min-Max number of shifts and reductions in bottom-up parser

I first assume that you are considering deterministic parsing. Other tpes of parser can mimic shift-reduce in a non-derterministic context. Assuming the there is no unit production, and no $\epsilon$-...
user avatar
  • 19.1k
2 votes

Min-Max number of shifts and reductions in bottom-up parser

The number of shifts is always precisely the number of symbols in the input stream, since every symbol is shifted exactly once. The number of reductions depends on the grammar; it is impossible to ...
user avatar
  • 11.3k
2 votes
Accepted

Where does LL parser belong in the top-down parsers classification

First let's make some general remarks about nomenclature. They are not all relevant here, but they may help you in the future. not all authors are using the same precise definition. Sometimes the ...
user avatar
  • 3,004
2 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 ...
user avatar
  • 121
1 vote

Textbook on formal syntax (and semantics) of programming languages

The book Practical Foundations for Programming Languages might have what you're looking for. An older version of the book can be read here.
user avatar
1 vote

Textbook on formal syntax (and semantics) of programming languages

Maybe you will like to book Concrete Semantics (which is freely available as a PDF). It defines the syntax and semantics of an imperative programming language using the proof assistant Isabelle/HOL. ...
user avatar
  • 131
1 vote

How many syntax trees can be made by a BNF

The answer is given by the Catalan numbers; if you have $n$ operators, the number of syntax trees is $\frac{1}{n+1}{2n \choose n}$. The problem is equivalent to finding all ways of inserting $n$ ...
user avatar
1 vote

The origin and the meaning of "Abstract Syntax Tree"

You are asking three questions. I will answer one. I don't think "abstract syntax tree" is a misnomer. It aims to represent the syntax of the expression. It is not claimed to represent all of the ...
user avatar
  • 143k
1 vote
Accepted

Neither Left nor Rightmost Derivations

The main reason is that context-free grammars, once introduced, were quickly adapted to provide a theoretical basis for program language compilation. For this usage, the goal is to parse as quickly ...
user avatar
  • 26
1 vote

How to generate (Java) source code in academically acceptable way - using abstract syntax tree?

It highly depends on what is the domain you are working on, i.e. why do you need to generate Java Source code anyway?. Can you explain better what knowledge do you have stored in your knowledge base?....
user avatar
1 vote
Accepted

Converting Regular expression to DFA by building syntax tree

No, using complementation yields an exponential blow-up in the size of the DFA.
user avatar
  • 5,944
1 vote
Accepted

Evaluating Statements Using a Parse Tree

An expression is composed usually of an operator (or function) applied to some arguments, or in the simplest case, just a constant (aka literal) or a variable. For evaluation: The value of a constant ...
user avatar
  • 19.1k

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