Parsings

Parsings refer to the processes of analyzing sequences of tokens to determine their grammatical structure or to transform them into structured representations. In linguistics, parsing yields a parse tree or other representation of a sentence's syntactic structure. In computing, parsing refers to analyzing the syntax of a sequence of tokens according to a formal grammar, producing a parse tree or an abstract syntax tree used by compilers and interpreters. The two senses overlap when processing natural language.

In linguistics, parsings can be constituency-based or dependency-based. They may be performed by rule-based grammars, statistical models, or neural networks. Common algorithms include chart parsing such as Earley’s algorithm and the CYK parser for context-free grammars, as well as deterministic top-down, left-to-right parsers and shift-reduce parsers. Parsings also address ambiguity, potentially producing a parse forest that encodes multiple possible analyses.

In computing, parsings come after lexical analysis and create representations such as an abstract syntax tree or parse tree. They are used in compilers, interpreters, and data format processors (for example, XML, JSON). Techniques include recursive-descent parsing, shift-reduce parsing, and parser generators like Yacc or ANTLR. Robust parsings handle errors through recovery strategies and can be incremental to support editing and real-time processing.

History of parsings spans language analysis and software design, with early approaches relying on hand-written parsers and, later, automated parser generators. In natural language processing, statistical and neural parsers have improved accuracy and speed, enabling better downstream tasks such as translation and information extraction.