Questions tagged [syntax-trees]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
19 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
0answers
32 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; } ...
0
votes
0answers
17 views

Formal definition for strong equivalence of grammars/parse trees

The Wikipedia article on equivalence of formal grammars defines weak and strong equivalence as follows: In formal language theory, weak equivalence of two grammars means they generate the same set ...
1
vote
0answers
21 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 ...
0
votes
0answers
22 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 ...
1
vote
1answer
18 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. ...
2
votes
1answer
77 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 ...
0
votes
0answers
291 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$ ...
0
votes
1answer
189 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 ...
3
votes
1answer
421 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 ...
0
votes
1answer
221 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 ...
1
vote
2answers
385 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/ ...
2
votes
1answer
97 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. ...
5
votes
1answer
245 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 ...
25
votes
3answers
3k 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 ...
-1
votes
2answers
694 views

I'm having trouble with Parse Trees

I am doing homework and I have the following problem: Consider the grammar: ...
1
vote
1answer
1k 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 ...
1
vote
2answers
838 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 ...
1
vote
2answers
124 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?
0
votes
0answers
403 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 ...
0
votes
1answer
889 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, ...
5
votes
1answer
956 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 ...
9
votes
1answer
784 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 ...
1
vote
1answer
1k 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 ...
2
votes
0answers
66 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. ...
0
votes
2answers
10k 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] ...