Questions tagged [syntax-trees]
The syntax-trees tag has no usage guidance.
36
questions
1
vote
1
answer
66
views
Is there a good way to hash abstract binding trees?
The hash function should be invariant under alpha-renaming. Using de Bruijn notation seems to be possible, but it requires alpha-converting the whole tree when a binding is created, and has the ...
CommunityBot
- 1
5
votes
2
answers
464
views
How do I interpret the wording of this passage about abstract binding trees from the book Practical Foundations of Programming Languages
On page 7/8, section 1.2, of Practical Foundations of Programming Languages, 2nd edition, Robert Harper gives this initial definition of abstract binding trees:
The smallest family of sets closed ...
- 131
0
votes
1
answer
40
views
find maximum in arbitrary expression tree
Originally posted on SO.
I have a very simple language that gets compiled to an Expression tree, and then evaluated. Users can define mathematical operations, use variables and control flow. Moreover, ...
CommunityBot
- 1
1
vote
0
answers
72
views
How does one parse a string into an AST (Abstract Syntax Tree) directly instead of to a CST (Concrete Syntax Tree)?
I wanted to parse strings to AST data structures instead of CSTs - which introduce a lot of intermediate nodes like terminal that might not be needed. I am not sure if one first creates a CST and then ...
- 3,040
1
vote
0
answers
81
views
Shallow Binding with static scope, is it possible?
I'm new in programming, I'm currently studying programming languages.
I'm trying to implement Shallow Binding with static scope, starting from an abstract syntax (producing a programming language ...
0
votes
1
answer
27
views
Do identical algorithm end up having the same abstract syntax tree?
More often than not, most programming problem can be solved in more than 1 way. You see this in website for practicing solving coding challenges where you often have myriad of solutions to the same ...
- 11.6k
1
vote
1
answer
202
views
How many syntax trees can be made by a BNF
An example of this would be:
1+2*3+4
Expression = Expression Arithmetic Expression | number
Arithmetic = + | - | * | /
Through just breaking down 1+2*3+4, it was easy to find that the answer was 5 ...
CommunityBot
- 1
2
votes
2
answers
110
views
Textbook on formal syntax (and semantics) of programming languages
I'd like to learn about formal syntax of programming languages: how do we describe the syntax of a programming language and how it should be parsed? How do we assign formal semantics to a parsed ...
- 131
3
votes
2
answers
2k
views
What are the modern alternatives to Backus–Naur form and what are their advantages?
I am very new to the whole concept of context-free grammars to represent the syntax tree of formal languages (i.e., programming languages). It seems that the Backus–Naur form (BNF) is the oldest of ...
- 131
2
votes
1
answer
167
views
Code optimization - syntax tree vs. intermediate representation
I'm working on a compiler for my own custom language. As I was reading an article on code optimization, I noticed that it assumed that the intermediate representation of the code had already been ...
- 264
2
votes
1
answer
2k
views
What are the known ambiguities in C language grammar?
I have found this reference for the C syntax Backus-Naur Form (BNF). I was wondering if there are any other ambiguities in this grammar other than the infamous "dangling else"? Also how we ...
- 792
0
votes
0
answers
226
views
Counting the number of unique syntax trees of a grammar
Lets say we have some arbitrary grammar for which we would like to know how many different syntax trees does it generate. For example the following:
S -> A1|1B
A -> 10|C
B -> C1 | $\varepsilon$
C -...
- 3
1
vote
0
answers
241
views
Algorithm for drawing AST-es?
One of the features the compiler for my programming language is supposed to have is the ability to draw AST-es, to make it easier to detect when syntax doesn't mean exactly what the programmer meant. ...
- 141
0
votes
0
answers
2k
views
Syntax Directed Translation Scheme for Postfix to Infix Notation
I'm reading Compilers Principles, Techniques and Tools textbook and I encountered a problem from exercise 2.3
We have to construct a syntax-directed translation scheme that translates arithmetic ...
0
votes
0
answers
56
views
Why is empty in this Abstract Syntax Tree?
I given the following code to write as AST:
{
a = 4;
while (a<10)
if (a<5)
a = a+5;
else
a = a+3;
}
...
- 251
0
votes
0
answers
23
views
Prooving equations are non derivable in Sigma algebra
Let Σ be the signature made up from the following symbols.
e: 0 arguments function (constant symbol)
f: 2 arguments function
g: 1 argument function
Variable set Var is made up from x,y,z
Let E be ...
- 51
1
vote
1
answer
45
views
defining a programming language grammar for doing arithmetic
I'm studying programming language design, and I've been taught the grammar below which lets you write basic math expressions.
...
- 5,017
0
votes
1
answer
333
views
The origin and the meaning of "Abstract Syntax Tree"
This question is closely related to Does an abstract syntax tree have to be a tree? and is partially answered there, but I would like to be more precise and to have more concise answers.
What is the ...
- 251
3
votes
1
answer
190
views
Simple example for Higher Order Abstract Syntax (λ-tree syntax)
I am reading https://www.cs.cmu.edu/~fp/papers/pldi88.pdf and https://en.wikipedia.org/wiki/Higher-order_abstract_syntax for trying to understand encoding of linear logic using HOAS into Coq. But I ...
- 14.6k
1
vote
0
answers
498
views
How do we evaluate semantic actions in L attributed SDT?
I came across following problem:
$S→ER$
$R→∗E\{print(′∗′);\}R∣ε$
$E→F+E\{print(′+′);\}∣F$
$F→(S)∣id\{print(id.value);\}$
Here $id$ is a token that represents an integer and $id.value$ ...
3
votes
1
answer
628
views
Where does LL parser belong in the top-down parsers classification
There are four types of top-down parsers according to this answer:
recursive descent backtracking
recursive descent predictive
table-driven with backtracking
table-driven predictive.
Also the author ...
- 3,069
0
votes
1
answer
599
views
Neither Left nor Rightmost Derivations
Consider a simple grammar and its derivations. The derivations could be done in leftmost or rightmost patterns and can also be done in no particular order as the derivation order has no effect on the ...
CommunityBot
- 1
1
vote
2
answers
668
views
How to generate (Java) source code in academically acceptable way - using abstract syntax tree?
I am trying to do automated programming research: business software generation from the knowledge base that is implemented as Scheme (Lisp dialect) code (in the framework of http://opencog.org/ ...
- 263
3
votes
1
answer
130
views
Is there a correspondence between the syntaxes and the type systems of programming languages?
I was reading the first chapter of Robert Harper's Practical Foundations for Programming Languages in which it introduced abstract binding trees, aka abt. It seems pretty like typed lambda calculus.
...
- 934
25
votes
3
answers
4k
views
Visual programming tools, why don’t they work with the AST directly?
I've found several open source visual programing tools like Blockly and friends, and other projects hosted at Github, but could't find any that work directly with the abstract syntax tree.
Why is ...
CommunityBot
- 1
-1
votes
2
answers
981
views
I'm having trouble with Parse Trees
I am doing homework and I have the following problem:
Consider the grammar:
...
- 1,388
1
vote
1
answer
2k
views
Converting Regular expression to DFA by building syntax tree
There is a way to convert regular expression to DFA (deterministic finite automata)
which is to build a syntax tree and then compute first pos, last pos, follow pos, and then use a Transition ...
- 6,159
2
votes
2
answers
1k
views
Why are syntax trees used in genetic programming?
Reading a course on genetic programming, the first chapter describes the syntax tree as the basic representation of programs in genetic programming.
What are the reasons leading to the choice of a ...
CommunityBot
- 1
1
vote
2
answers
182
views
Min-Max number of shifts and reductions in bottom-up parser [closed]
Given the Grammar has no unit or ɛ-productions,
What is minimum & maximum number of shifts and reduce needed by bottom-up parser?
- 19.5k
0
votes
0
answers
461
views
Evaluating Functions Using a Parse Tree
I'm making a compiler/interpreter for a language similar to C. I already have a parse tree. I was able to evaluate expression statements by converting my code to another language and then using an ...
- 72.4k
0
votes
1
answer
1k
views
Evaluating Statements Using a Parse Tree
I'm building a compiler. I already have a parse tree which I built using Bison for a grammar similar to the ANSI C grammar in this link. I see that for multiplicative expression in my parse tree, ...
- 72.4k
6
votes
1
answer
1k
views
Is CYK still relevant today?
I've come across the CYK algorithm and was wondering, as it's quite old, if it is still relevant today.
Is it or an extension of it still being used in compilers (for example), or have other ...
CommunityBot
- 1
10
votes
1
answer
1k
views
How do I reconstruct the forest of syntax trees from the Earley vector?
Using the Earley vector as a recognizer is quite straightforward: when the end of the string is reached, you just have to check for a completed axiomatic production started at position 0. If you have ...
CommunityBot
- 1
1
vote
1
answer
2k
views
Abstract Syntax Tree of Pure Lambda Calculus
I was wondering if anyone had any good references or book recommendations that cover abstract syntax trees (ASTs). Specifically, I am interested in the abstract syntax trees of different evaluation ...
- 3,182
2
votes
0
answers
69
views
What kind of structural features of strings can be described by regular grammars?
Context-free grammars, as well as other types of grammars, can naturally
associate structure with the strings of the defined language, for
example tree structures in the case of context-free language.
...
CommunityBot
- 1
0
votes
2
answers
18k
views
Drawing Annotated Parse Tree for Syntax Directed Definition [closed]
Im trying to draw an annotated parse tree for 3*5+4n, the text book shows the following:
[Compilers - Principles, techniques and tools (Dragon Book) by Aho, p308]
...
- 14k