Editing Parsing (section)

== Types of parsers ==
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 tree]]s 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.<ref name=" AhoSethiUllman 1986">Aho, A.V., Sethi, R. and Ullman, J.D.  (1986) " Compilers: principles, techniques, and tools." '' [[Addison-Wesley Longman]] Publishing Co., Inc. Boston, MA, USA. ''</ref> This is known as the primordial soup approach. Very similar to sentence diagramming, primordial soup breaks down the constituencies of sentences.<ref>{{Cite book|title=Parsing schemata : a framework for specification and analysis of parsing algorithms|last=Sikkel, Klaas, 1954-|date=1997|publisher=Springer|isbn=9783642605413|location=Berlin|oclc=606012644}}</ref>
;[[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 parser]]s are examples of bottom-up parsers. Another term used for this type of parser is [[Shift-reduce parser|Shift-Reduce]] parsing.

[[LL parser]]s and [[recursive-descent parser]]  are examples of top-down parsers that cannot accommodate [[left recursion|left recursive]] [[Formal grammar#The syntax of grammars|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 grammar|ambiguous context-free grammars]], more sophisticated algorithms for top-down parsing have been created by Frost, Hafiz, and Callaghan<ref name="FrostHafizCallaghan 2007">Frost, R., Hafiz, R. and Callaghan, P. (2007) " [https://aclanthology.info/pdf/W/W07/W07-2215.pdf Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars] {{Webarchive|url=https://web.archive.org/web/20180822014649/https://aclanthology.info/pdf/W/W07/W07-2215.pdf |date=2018-08-22 }} ." ''10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE '', Pages: 109 - 120, June 2007, Prague.</ref><ref name="FrostHafizCallaghan 2008">Frost, R., Hafiz, R. and Callaghan, P. (2008) " [http://scholar.uwindsor.ca/cgi/viewcontent.cgi?article=1411&context=etd#page=61 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.</ref> 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 [[Parse tree|derivation]] and LR parsers will generate a rightmost derivation (although usually in reverse).<ref name=" AhoSethiUllman 1986" />

Some ''{{visible anchor|graphical parsing}}'' algorithms have been designed for [[visual programming languages]].<ref>Rekers, Jan, and Andy Schürr. "[https://scholar.google.com/scholar?hl=en&as_sdt=0%2C47&q=%22graphical+parsing%22&btnG= Defining and parsing visual languages with layered graph grammars]." Journal of Visual Languages & Computing 8.1 (1997): 27-55.</ref><ref>Rekers, Jan, and A. Schurr. "[https://www.researchgate.net/profile/Andy_Schuerr/publication/3660769_A_graph_grammar_approach_to_graphical_parsing/links/55e4419708aecb1a7cc9fc62.pdf A graph grammar approach to graphical parsing]." Visual Languages, Proceedings., 11th IEEE International Symposium on. IEEE, 1995.</ref> Parsers for visual languages are sometimes based on [[graph grammar]]s.<ref>Zhang, Da-Qian, Kang Zhang, and Jiannong Cao. "[https://web.archive.org/web/20180323220143/https://pdfs.semanticscholar.org/5d3d/217d73e0f6bbeefa3749c16fbc7b2e00ec0b.pdf A context-sensitive graph grammar formalism for the specification of visual languages]." The Computer Journal 44.3 (2001): 186-200.</ref>

[[Adaptive parsing]] algorithms have been used to construct "self-extending" [[natural language user interface]]s.<ref name="Lehman2012">{{cite book|author=Jill Fain Lehman|title=Adaptive Parsing: Self-Extending Natural Language Interfaces|url=https://books.google.com/books?id=tU_tBwAAQBAJ&q=%22language+acquisition%22|date=6 December 2012|publisher=Springer Science & Business Media|isbn=978-1-4615-3622-2}}</ref>

=== Implementation ===

A simple parser implementation reads the entire input file, performs an intermediate computation or translation, and then writes the entire output file,
such as in-memory [[multi-pass compiler]]s.

Alternative parser implementation approaches:

* '''push parsers''' call registered handlers ([[Callback (computer programming)|callbacks]]) as soon as the parser detects relevant tokens in the input stream. A push parser may skip parts of the input that are irrelevant (an example is [[Expat (software)|Expat]]).
* '''pull parsers''', such as parsers that are typically used by [[compilers]] front-ends by "pulling" input text.
* '''incremental parsers''' (such as incremental [[chart parser]]s) that, as the text of the file is edited by a user, does not need to completely re-parse the entire file.
* '''Active''' versus '''passive parsers'''<ref>
Patrick Blackburn and Kristina Striegnitz.
[https://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/ "Natural Language Processing Techniques in Prolog"].
</ref><ref>
Song-Chun Zhu.
[http://www.stat.ucla.edu/~sczhu/Courses/UCLA/Stat_232B/Handouts/Ch4_chart_parsing.pdf "Classic Parsing Algorithms"].
</ref>