Syntax Trees: Parse vs AST

This lecture covers the concept of syntax trees, distinguishing between parse trees and abstract syntax trees (AST). It explains how a pretty printer can take an AST and output the leaves of a concrete parse tree. The lecture also delves into the syntax of a while language given by a context-free grammar, detailing the structure of programs, statements, and expressions. Additionally, it explores the creation of AST classes for statements and expressions, providing examples of different grammar rules and AST nodes. The lecture concludes with discussions on ambiguous grammars, expression grammar ambiguities, grammar layering by priorities, left associativity, and left vs. right associativity in expressions.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related lectures (9)

Related concepts (44)

CS-320: Computer language processing

We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language in

Parse tree

A parse tree or parsing tree or derivation tree or concrete syntax tree is an ordered, rooted tree that represents the syntactic structure of a string according to some context-free grammar. The term parse tree itself is used primarily in computational linguistics; in theoretical syntax, the term syntax tree is more common. Concrete syntax trees reflect the syntax of the input language, making them distinct from the abstract syntax trees used in computer programming.

Parsing expression grammar

In computer science, a parsing expression grammar (PEG) is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language. The formalism was introduced by Bryan Ford in 2004 and is closely related to the family of top-down parsing languages introduced in the early 1970s. Syntactically, PEGs also look similar to context-free grammars (CFGs), but they have a different interpretation: the choice operator selects the first match in PEG, while it is ambiguous in CFG.

Probabilistic context-free grammar

Grammar theory to model symbol strings originated from work in computational linguistics aiming to understand the structure of natural languages. Probabilistic context free grammars (PCFGs) have been applied in probabilistic modeling of RNA structures almost 40 years after they were introduced in computational linguistics. PCFGs extend context-free grammars similar to how hidden Markov models extend regular grammars. Each production is assigned a probability.

Ambiguous grammar

In computer science, an ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree. Every non-empty context-free language admits an ambiguous grammar by introducing e.g. a duplicate rule. A language that only admits ambiguous grammars is called an inherently ambiguous language. Deterministic context-free grammars are always unambiguous, and are an important subclass of unambiguous grammars; there are non-deterministic unambiguous grammars, however.

Context-free grammar

In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules can be applied to a nonterminal symbol regardless of its context. In particular, in a context-free grammar, each production rule is of the form with a single nonterminal symbol, and a string of terminals and/or nonterminals ( can be empty). Regardless of which symbols surround it, the single nonterminal on the left hand side can always be replaced by on the right hand side.

Parsing: CYK Algorithm

Explores formal grammars, parsing algorithms, CYK algorithm efficiency, and syntactic correctness in Natural Language Processing.

CYK Parsing Algorithm for General Grammars CS-320: Computer language processing

Introduces the CYK parsing algorithm for context-free grammars, explaining its handling of ambiguity and importance in parsing general grammars.

CYK algorithm

Introduces the CYK algorithm for efficient syntactic analysis using chart parsing and discusses its complexity and bottom-up parsing technique.

Parsing with Combinators CS-210: Functional programming

Explores parsing text into trees using parser combinators in Scala, covering filtering, transforming, sequencing, alternatives, recursion, spaces handling, lexing, monadic nature, and for-notation.

CYK Algorithm for Parsing General Grammars CS-320: Computer language processing

Explores parsing general grammars using the CYK algorithm and Chomsky Normal Form.