Editing Bottom-up parsing

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 leaves the highest-level overall structure to last.<ref name="Bansal2013">{{cite book|author=Arvind Kumar Bansal|title=Introduction to Programming Languages|url=https://books.google.com/books?id=531cAgAAQBAJ&q=%22bottom-up%22|date=14 December 2013|publisher=CRC Press|isbn=978-1-4665-6514-2}}</ref>

==Bottom-up versus top-down==

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.<ref>
[[Compilers: Principles, Techniques, and Tools]] (2nd Edition), by [[Alfred Aho]], [[Monica Lam]], [[Ravi Sethi]], and [[Jeffrey Ullman]], Prentice Hall 2006.</ref> 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.

{|
| [[File:Parse Tree Example.svg|thumb|x240px|Typical parse tree for<br/>A = B + C*2;&nbsp; D = 1]]
| [[File:Bottom-up Parse Tree Order.svg|thumb|x240px|Bottom-up parse steps]]
| [[File:Top-down Parse Tree Order.svg|thumb|x240px|Top-down parse steps]]
|}

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]].  So bottom-up parsers in practice handle a somewhat larger range of computer language grammars than deterministic top-down parsers do.

Bottom-up parsing is sometimes done by [[backtracking]]. But much more commonly, bottom-up parsing is done by a '''[[shift-reduce parser]]''' such as a [[LALR parser]].

==Examples==

Some of the parsers that use bottom-up parsing include:
* Precedence parser
** [[Simple precedence parser]]
** [[Operator-precedence parser]]
* Bounded-context parser (BC)
* [[LR parser]] ('''L'''eft-to-right, '''R'''ightmost derivation in reverse)
** [[Simple LR parser]] (SLR)
** [[LALR parser]] (Look-Ahead)
** [[Canonical LR parser]] (LR(1))
** [[GLR parser]] (Generalized)<ref name="GruneJacobs2007">{{cite book|author1=Dick Grune|author2=Ceriel J.H. Jacobs|title=Parsing Techniques: A Practical Guide|url=https://books.google.com/books?id=05xA_d5dSwAC&q=%22bottom-up%22|date=29 October 2007|publisher=Springer Science & Business Media|isbn=978-0-387-68954-8}}</ref>
* [[CYK algorithm|CYK parser]] (Cocke–Younger–Kasami)
* [[Recursive ascent parser]]
* [[Shift-reduce parser]]

==References==
{{reflist}}

{{Parsers}}

[[Category:Parsing algorithms]]