28

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 and editors like it (Scratch, Pencil Code/Droplet, Snap!, GP, Tiled Grace, and so on). Those systems don't show a traditional vertex-and-edge graph ...


10

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 form of a recognizer, and then the information management needed to actually build parse trees and parse forests is sort of added as an afterthought. One reason ...


9

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 formalisms. There is a simpler general parsing algorithm (below), but where the dynamic programming (DP) aspect is no longer visible. as things are defined more ...


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


6

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 as possible -- i.e., having as much code present all at once on the screen at the same time. Context helps them better manage complexity. (That's one reason ...


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

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


3

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 I believe it is implied that $x \notin \chi$ when you write $B[\chi, x]$, which is important. Using the definition of ABT above, you cannot prove for any $\...


3

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. Lisp languages are actually written as AST. The program source code is written as lists and directly used by the compiler and/or interpreter (depending upon which ...


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

I would like to know if/how evaluation strategies affect the structure of ASTs, how order of operation is reflected in the AST of an expression They don't, and it isn't. Evaluation strategies are functions which take ASTs as arguments, and return ASTs (or possibly only normal forms), so you can have different evaluation strategies working on the same AST. ...


3

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 with code generation support for many popular CPUs (as well as some less common ones!) These libraries are built around a well specified code representation ...


3

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


2

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 T ** c;. Since C supports type declarations via typedef, the parser itself cannot decide whether this is multiplication with variables T and *c or a variable declaration of a ...


2

The Dragon book style starts with the parse tree of the expression, i.e., the root (I think the very top is a mistake, the expression is an error as written) is the step $E \Rightarrow E + T$. The tree is then decorated giving the attributes their value (like $E.val = 19$). In an attributed grammar you give the grammar and the attributes, so that the grammar ...


2

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$-production. The maximum number of reduce is precisely the number $k$ of non-leaf (non-terminal) nodes in the parse tree, i.e. the number of productions rules ...


2

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 answer that question without knowing something about the grammar. For example, if the grammar were in Chomsky Normal Form, you could easily count the number of ...


2

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 differences are irrelevant for the current points, sometimes one wonder way such different things are named in the same way by different authors. Sometimes ...


1

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 meaning (semantics) of the expression. The issue with bound variables that you mention relates to semantics rather than syntax. Also, remember that names are ...


1

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 as possible using as little storage as possible. For that the best approach is to scan the input source once from 'left-to-right' [we interpret the source as a ...


1

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?. The most "formal" method I can think of is by using the Java grammar and generate and abstract syntax tree as you mentioned. But it may or may not be ...


1

No, using complementation yields an exponential blow-up in the size of the DFA.


1

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 is that constant, The value for a variable is the current value stored in that variable, as each variable corresponds to a memory location where values can be ...


1

I would say, yes, you may draw the parse tree as you have presented it. Your presentation is more abstract than the one from the textbook. On one hand, this means that it will be easier to manipulate. But it does also mean that things like generating accurate and useful error messages will be much more difficult, depending of course on what sort of ...


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