In computer science, parsing reveals the grammatical structure of linear input text, as a first step in working out its meaning. Bottom-up parsing recognizes the text's lowest-level small details first, before its mid-level structures, and leaving the highest-level overall structure to last. The bottom-up name comes from the concept of a parse tree, in which the most detailed parts are at the bottom of the upside-down tree, and larger structures composed from them are in successively higher layers, until at the top or "root" of the tree a single unit describes the entire input stream. A bottom-up parse discovers and processes that tree starting from the bottom left end, and incrementally works its way upwards and rightwards. A parser may act on the structure hierarchy's low, mid, and highest levels without ever creating an actual data tree; the tree is then merely implicit in the parser's actions. Bottom-up parsing patiently waits until it has scanned and parsed all parts of some construct before committing to what the combined construct is. The opposite of this is top-down parsing, in which the input's overall structure is decided (or guessed at) first, before dealing with mid-level parts, leaving completion of all lowest-level details to last. A top-down parser discovers and processes the hierarchical tree starting from the top, and incrementally works its way first downwards and then rightwards. Top-down parsing eagerly decides what a construct is much earlier, when it has only scanned the leftmost symbol of that construct and has not yet parsed any of its parts. Left corner parsing is a hybrid method that works bottom-up along the left edges of each subtree, and top-down on the rest of the parse tree. If a language grammar has multiple rules that may start with the same leftmost symbols but have different endings, then that grammar can be efficiently handled by a deterministic bottom-up parse but cannot be handled top-down without guesswork and backtracking.

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 courses (1)
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
Related lectures (13)
CYK Parsing Algorithm for General Grammars
Introduces the CYK parsing algorithm for context-free grammars, explaining its handling of ambiguity and importance in parsing general grammars.
Object-Oriented Parser Combinators
Covers object-oriented parser combinators in Scala for building parsers, including JSON parsing and testing.
Syntax Trees: Parse vs AST
Explains syntax trees, parse vs AST, while language syntax, AST classes, and grammar ambiguities.
Show more
Related publications (7)

From thin plates to Ahmed bodies: linear and weakly nonlinear stability of rectangular prisms

Edouard Boujo, Giuseppe Antonio Zampogna

We study the stability of laminar wakes past three-dimensional rectangular prisms. The width-to-height ratio is set to W/H = 1.2, while the length-to-height ratio 1/6 < L/H < 3 covers a wide range of geometries from thin plates to elongated Ahmed bodies. F ...
CAMBRIDGE UNIV PRESS2023

Efficient Parsing with Derivatives and Zippers

Romain Edelmann

Parsing is the process that enables a computer system to make sense of raw data. Parsing is common to almost all computer systems: It is involved every time sequential data is read and elaborated into structured data. The theory of parsing usually focuses ...
EPFL2021

Harmonic Syntax in Time: Rhythm Improves Grammatical Models of Harmony

Martin Alois Rohrmeier, Daniel Harasim

Music is hierarchically structured, both in how it is perceived by listeners and how it is composed. Such structure can be elegantly captured using probabilistic grammatical models similar to those used to study natural language. They address the complexit ...
ISMIR2019
Show more
Related concepts (6)
Left recursion
In the formal language theory of computer science, left recursion is a special case of recursion where a string is recognized as part of a language by the fact that it decomposes into a string from that same language (on the left) and a suffix (on the right). For instance, can be recognized as a sum because it can be broken into , also a sum, and , a suitable suffix. In terms of context-free grammar, a nonterminal is left-recursive if the leftmost symbol in one of its productions is itself (in the case of direct left recursion) or can be made itself by some sequence of substitutions (in the case of indirect left recursion).
Shift-reduce parser
A shift-reduce parser is a class of efficient, table-driven bottom-up parsing methods for computer languages and other notations formally defined by a grammar. The parsing methods most commonly used for parsing programming languages, LR parsing and its variations, are shift-reduce methods. The precedence parsers used before the invention of LR parsing are also shift-reduce methods. All shift-reduce parsers have similar outward effects, in the incremental order in which they build a parse tree or call specific output actions.
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.
Show more

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.