Difference between revisions of "Bottom-Up Parsing System"

Jump to: navigation, search
(Tag: continuous replacement)
Line 3: Line 3:
* <B>AKA:</B> [[Bottom-Up Parser]].
* <B>AKA:</B> [[Bottom-Up Parser]].
* <B>Context:</B>
* <B>Context:</B>
** It can solve a [[Bottom-Up Parsing Task]] by implementing [[Bottom-Up Parsing Algorithm]].
** It can range from being a [[LR Parsing System]] to being a [[Recursive Ascent Parsing System]].
** It can range from being a [[LR Parsing System]] to being a [[Recursive Ascent Parsing System]].
* <B>Example(s):</B>
* <B>Example(s):</B>

Revision as of 04:17, 15 August 2019

A Bottom-Up Parsing System is a Parsing System that can recognize the text's lowest-level structure.



  • (Wikipedia, 2019) ⇒ https://en.wikipedia.org/wiki/Parsing#Types_of_parsers Retrieved:2019-7-7.
    • The task of the parser is essentially to determine if and how the input can be derived from the start symbol of the grammar. This can be done in essentially two ways:
      • Top-down parsing - Top-down parsing can be viewed as an attempt to find left-most derivations of an input-stream by searching for parse trees using a top-down expansion of the given formal grammar rules. Tokens are consumed from left to right. Inclusive choice is used to accommodate ambiguity by expanding all alternative right-hand-sides of grammar rules.[1]
      • Bottom-up parsing - A parser can start with the input and attempt to rewrite it to the start symbol. Intuitively, the parser attempts to locate the most basic elements, then the elements containing these, and so on. LR parsers are examples of bottom-up parsers. Another term used for this type of parser is Shift-Reduce parsing.
    • LL parsers and recursive-descent parser are examples of top-down parsers which cannot accommodate left recursive production rules. Although it has been believed that simple implementations of top-down parsing cannot accommodate direct and indirect left-recursion and may require exponential time and space complexity while parsing ambiguous context-free grammars, more sophisticated algorithms for top-down parsing have been created by Frost, Hafiz, and Callaghan[2] [3] which accommodate ambiguity and left recursion in polynomial time and which generate polynomial-size representations of the potentially exponential number of parse trees. Their algorithm is able to produce both left-most and right-most derivations of an input with regard to a given context-free grammar.

      An important distinction with regard to parsers is whether a parser generates a leftmost derivation or a rightmost derivation (see context-free grammar). LL parsers will generate a leftmost derivation and LR parsers will generate a rightmost derivation (although usually in reverse).[1]

      Some graphical parsing algorithms have been designed for visual programming languages. [4] [5] Parsers for visual languages are sometimes based on graph grammars. [6] Adaptive parsing algorithms have been used to construct "self-extending" natural language user interfaces.[7]

  1. 1.0 1.1 Aho, A.V., Sethi, R. and Ullman ,J.D. (1986) " Compilers: principles, techniques, and tools." Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA.
  2. Frost, R., Hafiz, R. and Callaghan, P. (2007) " Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars ." 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE , Pages: 109 - 120, June 2007, Prague.
  3. Frost, R., Hafiz, R. and Callaghan, P. (2008) " Parser Combinators for Ambiguous Left-Recursive Grammars." 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN , Volume 4902/2008, Pages: 167 - 181, January 2008, San Francisco.
  4. Rekers, Jan, and Andy Schürr. "Defining and parsing visual languages with layered graph grammars." Journal of Visual Languages & Computing 8.1 (1997): 27-55.
  5. Rekers, Jan, and A. Schurr. "A graph grammar approach to graphical parsing." Visual Languages, Proceedings., 11th IEEE International Symposium on. IEEE, 1995.
  6. Zhang, Da-Qian, Kang Zhang, and Jiannong Cao. "A context-sensitive graph grammar formalism for the specification of visual languages." The Computer Journal 44.3 (2001): 186-200.
  7. Jill Fain Lehman (6 December 2012). Adaptive Parsing: Self-Extending Natural Language Interfaces. Springer Science & Business Media. ISBN 978-1-4615-3622-2.


  • (Wikipedia, 2019) ⇒ https://en.wikipedia.org/wiki/Bottom-up_parsing Retrieved:2019-7-7.
    • 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.