Editing Parsing (section)

=== Overview of process ===
[[File:Parser Flowո.gif|right|Flow of data in a typical parser]]
The following example demonstrates the common case of parsing a computer language with two levels of grammar: lexical and syntactic.

The first stage is the token generation, or [[lexical analysis]], by which the input character stream is split into meaningful symbols defined by a grammar of [[regular expression]]s. For example, a calculator program would look at an input such as "<code>12 * (3 + 4)^2</code>" and split it into the tokens <code>12</code>, <code>*</code>, <code>(</code>, <code>3</code>, <code>+</code>, <code>4</code>, <code>)</code>, <code>^</code>, <code>2</code>, each of which is a meaningful symbol in the context of an arithmetic expression. The lexer would contain rules to tell it that the characters <code>*</code>, <code>+</code>, <code>^</code>, <code>(</code> and <code>)</code> mark the start of a new token, so meaningless tokens like "<code>12*</code>" or "<code>(3</code>" will not be generated.

The next stage is parsing or syntactic analysis, which is checking that the tokens form an allowable expression. This is usually done with reference to a [[context-free grammar]] which recursively defines components that can make up an expression and the order in which they must appear. However, not all rules defining programming languages can be expressed by context-free grammars alone, for example type validity and proper declaration of identifiers. These rules can be formally expressed with [[attribute grammar]]s.

The final phase is [[Semantic analysis (computer science)|semantic parsing]] or analysis, which is working out the implications of the expression just validated and taking the appropriate action.<ref>Berant, Jonathan, and Percy Liang. "[https://www.aclweb.org/anthology/P14-1133.pdf Semantic parsing via paraphrasing]." Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2014.</ref> In the case of a calculator or interpreter, the action is to evaluate the expression or program; a compiler, on the other hand, would generate some kind of code. Attribute grammars can also be used to define these actions.