Skip to main content Skip to navigation

Parsing and Construing

Draft notes on construals developed by WMB since c. September 2020 

Parsing can be thought as an archetypal example of construing

  • cf. construal and natural language

It involves interpreting a sequence of symbols by identifying their abstract structure

Parsing can be carried out on a complete input string, but more typically is an incremental process carried out as the string is read from left to right (cf. how a computer parser operates, and the principles of e.g. LR-parsing)

Parsing is relative to structural rules that are framed in a grammar.

  • will focus on context-free grammars, where productions take the form V :: ... (LHS has a single grammar variable)
  • a grammar variable is an abstract way of representing a segment of an input string

A string of grammar variable and symbols can be conceived as a construal of a segment of an input string

Such a construal represents a string at different levels of abstraction

  • cf. Kramer's contention that abstraction is the key concern of Computer Science
  • note that the same segment of input can have many different construals

The two most obvious construals of the input string are

  • the raw string of input symbols (the most concrete construal)
  • the entire input string as a well-formed expression over the grammar (the most abstract construal)

(The latter construal is represented by a special grammar variable, viz. the Start symbol in the grammar)

In line with the rich semantics of construal, an input string may also be construed as not a well-formed expression

The process by which a wf expression is derived from a grammar can be either top-down or bottom-up

  • top-down is generation of the concrete string from the abstract concept
  • bottom-up is recognition of the concrete string as an instance of the abstract concept

The product of such a process of connection an input with the grammar Start symbol is a parse-tree.

Both the raw input string and the Start symbol are cuts of the parse-tree

A cut of a tree is a set of nodes in the tree such that

  • any path from root to leaf visits exactly one of the nodes in the cut

As a consequence of this definition

  • there is no hierarchical relationship between any two nodes in a cut
  • both the root and the set of leaves are cuts of a tree